論文の概要: 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$のスピードアップを達成できた。
関連論文リスト
- Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming [26.334739062500674]
データから直接バランスの取れたラプラシアングラフを学習する高速な手法を提案する。
合成および実世界のデータセットに対する実験により、バランスの取れたグラフ学習法が競合する手法より優れていることが示された。
論文 参考訳（メタデータ） (2024-09-12T06:53:50Z) - Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。
我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
論文 参考訳（メタデータ） (2024-07-18T15:58:04Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。