論文の概要: Consistent Multigroup Low-Rank Approximation
- arxiv url: http://arxiv.org/abs/2503.21563v1
- Date: Thu, 27 Mar 2025 14:47:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 18:49:11.569495
- Title: Consistent Multigroup Low-Rank Approximation
- Title(参考訳): 一貫性多群低ランク近似
- Authors: Antonis Matakos, Martino Ciaperoni, Heikki Mannila,
- Abstract要約: マルチグループデータに対する一貫した低ランク近似の問題を考察する。
最良の階数(1$プロジェクション)を見つけるには、原始双対アプローチや半有限計画法を用いる。
- 参考スコア(独自算出の注目度): 2.5056643038238504
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of consistent low-rank approximation for multigroup data: we ask for a sequence of $k$ basis vectors such that projecting the data onto their spanned subspace treats all groups as equally as possible, by minimizing the maximum error among the groups. Additionally, we require that the sequence of basis vectors satisfies the natural consistency property: when looking for the best $k$ vectors, the first $d<k$ vectors are the best possible solution to the problem of finding $d$ basis vectors. Thus, this multigroup low-rank approximation method naturally generalizes \svd and reduces to \svd for data with a single group. We give an iterative algorithm for this task that sequentially adds to the basis the vector that gives the best rank$-1$ projection according to the min-max criterion, and then projects the data onto the orthogonal complement of that vector. For finding the best rank$-1$ projection, we use primal-dual approaches or semidefinite programming. We analyze the theoretical properties of the algorithms and demonstrate empirically that the proposed methods compare favorably to existing methods for multigroup (or fair) PCA.
- Abstract(参考訳): 多重群データに対する一貫した低ランク近似の問題を考察し、各群間の最大誤差を最小限に抑えて、その部分空間にデータを射影するような$k$基底ベクトル列を求める。
さらに、基底ベクトルの列は自然な整合性を満たすことを要求する: 最高の$k$ベクトルを求めるとき、最初の$d<k$ベクトルは、$d$基底ベクトルを見つける問題に対する最良の解である。
したがって、この多群ローランク近似法は自然に \svd を一般化し、単一の群を持つデータに対して \svd に還元する。
このタスクに対して反復アルゴリズムを与え、min-max基準に従って最良の階数1$プロジェクションを与えるベクトルを逐次加算し、そのベクトルの直交補数にデータを投影する。
最良の階数(1$プロジェクション)を見つけるには、原始双対アプローチや半有限計画法を用いる。
提案手法は,提案手法が既存のマルチグループ(またはフェア)PCA法と良好に比較できることを実証的に示す。
関連論文リスト
- Project-Probe-Aggregate: Efficient Fine-Tuning for Group Robustness [53.96714099151378]
画像テキスト基礎モデルのパラメータ効率向上のための3段階のアプローチを提案する。
本手法は, マイノリティ標本同定とロバストトレーニングアルゴリズムの2つの重要な要素を改良する。
我々の理論分析は,PPAが少数群の識別を向上し,バランスの取れたグループエラーを最小限に抑えるためにベイズが最適であることを示している。
論文 参考訳(メタデータ) (2025-03-12T15:46:12Z) - SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。
我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
論文 参考訳(メタデータ) (2024-12-30T18:59:46Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳(メタデータ) (2024-08-27T18:28:31Z) - Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams [0.0]
本稿では,主成分分析 (PCA) のための新しいアルゴリズムについて紹介する。
外れ値が存在する場合でも、PCAの最適部分空間にナビゲートする。
このアプローチは、$nd+mathcalO(1)textpoly(n,d)$の時間複雑性を持つ最適解を得る。
論文 参考訳(メタデータ) (2024-08-13T13:05:36Z) - Efficient Algorithms for Empirical Group Distributional Robust
Optimization and Beyond [15.664414751701718]
経験的GDROを$textittwo-level$ finite-sum convex-concave minimax Optimization問題として定式化する。
我々は、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。
注目すべきは、我々の手法が最先端の手法よりも$sqrtm$で優れていることだ。
論文 参考訳(メタデータ) (2024-03-06T09:14:24Z) - Sparse PCA with Oracle Property [115.72363972222622]
新規な正規化を伴うスパースPCAの半定緩和に基づく推定器群を提案する。
我々は、家族内の別の推定器が、スパースPCAの標準半定緩和よりも、より急激な収束率を達成することを証明した。
論文 参考訳(メタデータ) (2023-12-28T02:52:54Z) - Empirical Bayes Covariance Decomposition, and a solution to the Multiple
Tuning Problem in Sparse PCA [2.5382095320488673]
スパース主成分分析(PCA)は,PCAの解釈可能性と信頼性を両立させる手法として提案されている。
経験ベイズ法による「複数チューニング問題」の解法を提案する。
論文 参考訳(メタデータ) (2023-12-06T04:00:42Z) - When Collaborative Filtering is not Collaborative: Unfairness of PCA for Recommendations [6.41560541899312]
主成分分析の基礎的手法(PCA)に着目する。
我々はPCAにおける項目不公平を誘発する2つの基本的人気メカニズムを同定する。
主成分を最適化するアルゴリズムである項目重み付きPCAを開発した。
論文 参考訳(メタデータ) (2023-10-15T00:22:12Z) - Efficient fair PCA for fair representation learning [21.990310743597174]
そこで本研究では,標準的なPCAに類似した解析解をカーネル化可能な,概念的にシンプルなアプローチを提案する。
提案手法は,標準PCAやカーネルPCAと同じ複雑さを持ち,半定値プログラミングや多様体最適化に基づく等価PCAの既存手法よりもはるかに高速に動作する。
論文 参考訳(メタデータ) (2023-02-26T13:34:43Z) - A novel approach for Fair Principal Component Analysis based on
eigendecomposition [10.203602318836444]
1次元探索からなる簡単な戦略を用いて,公平性問題に対処する新しいPCAアルゴリズムを提案する。
私たちの発見は、いくつかの現実の状況と、バランスの取れていないデータセットとバランスの取れていないデータセットの両方のシナリオで一致しています。
論文 参考訳(メタデータ) (2022-08-24T08:20:16Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Local manifold learning and its link to domain-based physics knowledge [53.15471241298841]
多くの反応系では、熱化学状態空間は低次元多様体(LDM)に近く進化すると仮定される。
局所的データクラスタ(ローカルPCA)に適用されたPCAは,熱化学状態空間の固有パラメータ化を検出することができることを示す。
論文 参考訳(メタデータ) (2022-07-01T09:06:25Z) - Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。
我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-01-21T16:43:03Z) - Sparse PCA on fixed-rank matrices [0.05076419064097732]
共分散行列のランクが固定値であれば、大域的最適性に対してスパースPCAを解くアルゴリズムが存在することを示す。
また,主成分の非結合性を必要とするスパースPCAについても同様の結果が得られた。
論文 参考訳(メタデータ) (2022-01-07T15:05:32Z) - AgFlow: Fast Model Selection of Penalized PCA via Implicit
Regularization Effects of Gradient Flow [64.81110234990888]
主成分分析(PCA)は特徴抽出と次元減少の有効な手法として広く用いられている。
High Dimension Low Sample Size (HDLSS) 設定では、ペナル化ロードを備えた修正主成分が好まれる。
ペナル化PCAの高速モデル選択法として近似勾配流(AgFlow)を提案する。
論文 参考訳(メタデータ) (2021-10-07T08:57:46Z) - Optimal N-ary ECOC Matrices for Ensemble Classification [1.3561997774592662]
アンサンブル分類法における誤り訂正出力符号(ECOC)の新たな構成について述べる。
任意の素数$N$が与えられたとき、この決定論的構成は基底-$N$対称二乗行列を$M$で生成する。
論文 参考訳(メタデータ) (2021-10-05T16:50:15Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳(メタデータ) (2020-10-19T16:45:37Z) - Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。
問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。
我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
論文 参考訳(メタデータ) (2020-06-18T17:18:02Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。