論文の概要: Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment
- arxiv url: http://arxiv.org/abs/2106.01642v1
- Date: Thu, 3 Jun 2021 07:22:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-04 16:04:32.563374
- Title: Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment
- Title(参考訳): ガーシュゴリンディスク完全アライメントを用いたプロジェクションフリーグラフベース分類学習
- Authors: Cheng Yang, Gene Cheung, Wai-tian Tan, Guangtao Zhai
- Abstract要約: グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
- 参考スコア(独自算出の注目度): 59.87663954467815
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In semi-supervised graph-based binary classifier learning, a subset of known
labels $\hat{x}_i$ are used to infer unknown labels, assuming that the label
signal $x$ is smooth with respect to a similarity graph specified by a
Laplacian matrix. When restricting labels $x_i$ to binary values, the problem
is NP-hard. While a conventional semi-definite programming (SDP) relaxation can
be solved in polynomial time using, for example, the alternating direction
method of multipliers (ADMM), the complexity of iteratively projecting a
candidate matrix $M$ onto the positive semi-definite (PSD) cone ($M \succeq 0$)
remains high. In this paper, leveraging a recent linear algebraic theory called
Gershgorin disc perfect alignment (GDPA), we propose a fast projection-free
method by solving a sequence of linear programs (LP) instead. Specifically, we
first recast the SDP relaxation to its SDP dual, where a feasible solution $H
\succeq 0$ can be interpreted as a Laplacian matrix corresponding to a balanced
signed graph sans the last node. To achieve graph balance, we split the last
node into two that respectively contain the original positive and negative
edges, resulting in a new Laplacian $\bar{H}$. We repose the SDP dual for
solution $\bar{H}$, then replace the PSD cone constraint $\bar{H} \succeq 0$
with linear constraints derived from GDPA -- sufficient conditions to ensure
$\bar{H}$ is PSD -- so that the optimization becomes an LP per iteration.
Finally, we extract predicted labels from our converged LP solution $\bar{H}$.
Experiments show that our algorithm enjoyed a $40\times$ speedup on average
over the next fastest scheme while retaining comparable label prediction
performance.
- Abstract(参考訳): 半教師付きグラフベースのバイナリ分類器学習では、ラプラシア行列で指定された類似グラフに対してラベル信号$x$が滑らかであると仮定して、既知のラベル$\hat{x}_i$のサブセットを用いて未知のラベルを推論する。
x_i$をバイナリ値に制限する場合、問題はnp-hardである。
例えば、乗算器の交互方向法(admm)を用いて、従来の半定値プログラミング(sdp)の緩和を多項式時間で解くことができるが、候補行列を正半定値(psd)コーン(m \succeq 0$)上に反復的に投影する複雑さは高いままである。
本稿では,最近発表された gershgorin disc perfect alignment (gdpa) と呼ばれる線形代数理論を用いて,線形プログラムのシーケンスを解いて,高速投影フリーな手法を提案する。
具体的には、SDP緩和をSDP双対にリキャストし、実現可能な解である$H \succeq 0$を、バランスの取れた符号グラフに対応するラプラシア行列として解釈することができる。
グラフバランスを達成するために、最後のノードをそれぞれ元の正の辺と負の辺を含む2つに分割し、結果として新しいラプラシアン$\bar{H}$となる。
sdp の双対を解 $\bar{h}$ に置き換えた後、psd の錐制約 $\bar{h} \succeq 0$ を gdpa から導かれた線形制約に置き換える -- $\bar{h}$ が psd であることを保証するのに十分な条件 -- により、最適化はイテレーション当たり lp になる。
最後に、収束したLP解 $\bar{H}$ から予測ラベルを抽出する。
実験により,我々のアルゴリズムは,ラベル予測性能を同等に保ちながら,次の最速のスキームよりも平均40\times$のスピードアップを達成できた。
関連論文リスト
- Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳(メタデータ) (2022-08-18T09:19:01Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳(メタデータ) (2021-09-10T07:01:15Z) - Efficiently Solving MDPs with Stochastic Mirror Descent [38.30919646721354]
線形モデルに与えられた無限水平マルコフ決定過程(MDP)を近似的に解くための統一的な枠組みを提案する。
これらの結果は、より一般的なミラー降下フレームワークを用いて、単純なドメインとボックスドメインで大域的なサドルポイント問題を解くことによって達成される。
論文 参考訳(メタデータ) (2020-08-28T17:58:40Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment [46.145969174332485]
プロジェクションフリーの高速な一般メトリック学習フレームワークを提案する。
距離あたりの線形制約が考えられるため、距離学習問題におけるPDコーン制約を置き換える。
実験により,我々のグラフ距離の最適化はコーン射影方式よりもはるかに高速であることが示された。
論文 参考訳(メタデータ) (2020-06-15T23:15:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。