論文の概要: Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment

• arxiv url: http://arxiv.org/abs/2006.08816v6
• Date: Fri, 11 Jun 2021 03:32:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 03:33:49.801666
• Title: Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment
• Title（参考訳）: gershgorin disc perfect alignmentによるサイン付きグラフメトリック学習
• Authors: Cheng Yang, Gene Cheung, Wei Hu
• Abstract要約: プロジェクションフリーの高速な一般メトリック学習フレームワークを提案する。 距離あたりの線形制約が考えられるため、距離学習問題におけるPDコーン制約を置き換える。 実験により,我々のグラフ距離の最適化はコーン射影方式よりもはるかに高速であることが示された。
• 参考スコア（独自算出の注目度）: 46.145969174332485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a convex and differentiable objective $Q(\M)$ for a real symmetric matrix $\M$ in the positive definite (PD) cone -- used to compute Mahalanobis distances -- we propose a fast general metric learning framework that is entirely projection-free. We first assume that $\M$ resides in a space $\cS$ of generalized graph Laplacian matrices corresponding to balanced signed graphs. $\M \in \cS$ that is also PD is called a graph metric matrix. Unlike low-rank metric matrices common in the literature, $\cS$ includes the important diagonal-only matrices as a special case. The key theorem to circumvent full eigen-decomposition and enable fast metric matrix optimization is Gershgorin disc perfect alignment (GDPA): given $\M \in \cS$ and diagonal matrix $\S$, where $S_{ii} = 1/v_i$ and $\v$ is $\M$'s first eigenvector, we prove that Gershgorin disc left-ends of similarity transform $\B = \S \M \S^{-1}$ are perfectly aligned at the smallest eigenvalue $\lambda_{\min}$. Using this theorem, we replace the PD cone constraint in the metric learning problem with tightest possible linear constraints per iteration, so that the alternating optimization of the diagonal / off-diagonal terms in $\M$ can be solved efficiently as linear programs via the Frank-Wolfe method. We update $\v$ using Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm start as entries in $\M$ are optimized successively. Experiments show that our graph metric optimization is significantly faster than cone-projection schemes, and produces competitive binary classification performance.
• Abstract（参考訳）: 実対称行列に対して凸で微分可能な$Q(\M)$が与えられたとき、マハラノビス距離を計算するために使われる正定値(PD)錐において$\M$は射影のない高速な一般計量学習フレームワークを提案する。 まず、$\m$ は平衡符号付きグラフに対応する一般化グラフラプラシアン行列の空間 $\cs$ に存在すると仮定する。 PD である$\M \in \cS$ もグラフ計量行列と呼ばれる。 文献で一般的な低ランク計量行列とは異なり、$\cS$ は特別な場合として重要な対角行列を含む。 完全固有分解を回避し、高速な計量行列最適化を可能にするための重要な定理は gershgorin disc perfect alignment (gdpa) である: $\m \in \cs$ と対角行列 $\s$, ここで $s_{ii} = 1/v_i$ と $\v$ は $\m$'s first eigenvector であるので、gershgorin disc left-ends of similarity transform $\b = \s \m \s^{-1}$ は最小の固有値 $\lambda_{\min}$ で完全に整列する。 この定理を用いることで、計量学習問題におけるPDコーン制約を反復毎の最も厳密な線形制約に置き換え、Frank-Wolfe法による対角線/対角線/対角線の項の交互最適化を効率的に線形プログラムとして解ける。 我々は,$\m$のエントリが順次最適化されるので,局所最適ブロック前条件共役勾配 (lobpcg) を用いて$\v$を更新する。 実験により, グラフ距離の最適化はコーン投影方式よりもはるかに高速であり, 競合する二値分類性能が得られた。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• 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)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Graph Metric Learning via Gershgorin Disc Alignment [46.145969174332485]
  そこで,MathcalS$ の目的 $min_textbfM は計量行列 $textbfM$ の凸微分可能な関数である。 Gershgorinディスクは、最初のeigenvector $textbfv$ of $textbfM$を使って完全に整列可能であることを証明します。 実験により, グラフ距離行列の計算効率は, 競合手法を用いて学習した指標よりも優れていた。
  論文  参考訳（メタデータ） (2020-01-28T17:44:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。