論文の概要: Graph Metric Learning via Gershgorin Disc Alignment
- arxiv url: http://arxiv.org/abs/2001.10485v4
- Date: Mon, 9 Mar 2020 22:42:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-06 02:26:02.805806
- Title: Graph Metric Learning via Gershgorin Disc Alignment
- Title（参考訳）: gershgorinディスクアライメントによるグラフメトリック学習
- Authors: Cheng Yang, Gene Cheung, Wei Hu
- Abstract要約: そこで,MathcalS$ の目的 $min_textbfM は計量行列 $textbfM$ の凸微分可能な関数である。
Gershgorinディスクは、最初のeigenvector $textbfv$ of $textbfM$を使って完全に整列可能であることを証明します。
実験により, グラフ距離行列の計算効率は, 競合手法を用いて学習した指標よりも優れていた。
- 参考スコア（独自算出の注目度）: 46.145969174332485
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a fast general projection-free metric learning framework, where
the minimization objective $\min_{\textbf{M} \in \mathcal{S}} Q(\textbf{M})$ is
a convex differentiable function of the metric matrix $\textbf{M}$, and
$\textbf{M}$ resides in the set $\mathcal{S}$ of generalized graph Laplacian
matrices for connected graphs with positive edge weights and node degrees.
Unlike low-rank metric matrices common in the literature, $\mathcal{S}$
includes the important positive-diagonal-only matrices as a special case in the
limit. The key idea for fast optimization is to rewrite the positive definite
cone constraint in $\mathcal{S}$ as signal-adaptive linear constraints via
Gershgorin disc alignment, so that the alternating optimization of the diagonal
and off-diagonal terms in $\textbf{M}$ can be solved efficiently as linear
programs via Frank-Wolfe iterations. We prove that the Gershgorin discs can be
aligned perfectly using the first eigenvector $\textbf{v}$ of $\textbf{M}$,
which we update iteratively using Locally Optimal Block Preconditioned
Conjugate Gradient (LOBPCG) with warm start as diagonal / off-diagonal terms
are optimized. Experiments show that our efficiently computed graph metric
matrices outperform metrics learned using competing methods in terms of
classification tasks.
- Abstract（参考訳）: 我々は、最小化対象 $\min_{\textbf{M} \in \mathcal{S}} Q(\textbf{M})$ は計量行列 $\textbf{M}$ の凸微分可能関数であり、$\textbf{M}$ は一般化グラフの集合 $\mathcal{S}$ に存在し、正のエッジ重みとノード次数を持つ連結グラフに対するラプラシア行列である。
文献で一般的な低ランク計量行列とは異なり、$\mathcal{S}$ は極限の特別な場合として重要な正対角行列を含む。
高速最適化の鍵となるアイデアは、ゲルシュゴリンディスクアライメントによって信号適応線形制約として$\mathcal{s}$ で正定円錐制約を書き直し、$\textbf{m}$ の対角およびオフ対角項の交互最適化をフランク・ウルフ反復による線形プログラムとして効率的に解くことである。
我々は,最初の固有ベクトル $\textbf{v}$ of $\textbf{m}$ を用いてゲルシュゴリンディスクを完全アライメントできることを証明した。
実験により, グラフ距離行列の計算効率は, 競合手法を用いて学習した指標よりも優れていた。
関連論文リスト
- Optimal Matrix Sketching over Sliding Windows [38.09464189820894]
マトリックススケッチは、mathbbRNtimes d$で行列 $boldsymbolAを近似することを目的としており、長さ$N$のベクトルストリームとmathbbRelltimes d, ell ll N$で小さなスケッチマトリックス $boldsymbolBで構成されている。
Oleftfracdvarepsilonright)$ space bound for matrix sketching over row-normalized, sequence-based sliding windows。
論文 参考訳（メタデータ） (2024-05-13T14:38:35Z) - Fast Online Node Labeling for Very Large Graphs [11.700626862639131]
現在のメソッドは、$mathcalO(n3)$または$mathcalO(n2)$スペースの複雑さでグラフカーネルランタイムマトリックスを反転させるか、ランダムなスパンニングツリーを大量にサンプリングする。
本稿では,一連の研究によって導入されたテクスチトリン緩和技術に基づく改善を提案する。
論文 参考訳（メタデータ） (2023-05-25T17:13:08Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文 参考訳（メタデータ） (2021-06-03T07:22:48Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment [46.145969174332485]
プロジェクションフリーの高速な一般メトリック学習フレームワークを提案する。
距離あたりの線形制約が考えられるため、距離学習問題におけるPDコーン制約を置き換える。
実験により,我々のグラフ距離の最適化はコーン射影方式よりもはるかに高速であることが示された。
論文 参考訳（メタデータ） (2020-06-15T23:15:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。