論文の概要: On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical
Similarity Graphs
- arxiv url: http://arxiv.org/abs/2109.05408v1
- Date: Sun, 12 Sep 2021 02:38:54 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-14 15:56:25.495471
- Title: On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical
Similarity Graphs
- Title（参考訳）: 行列補完の基本極限について:階層的類似性グラフの活用
- Authors: Junhyung Ahn, Adel Elmahdy, Soheil Mohajer, Changho Suh
- Abstract要約: 本稿では,階層的類似性グラフを推薦システムの側情報として活用する行列補完問題について検討する。
階層的ブロックモデルの下では、観測された行列成分の数に対する正確な情報理論の限界を特徴づける。
最適サンプルの複雑性を解析し,階層的類似性グラフの側情報の品質指標に依拠する特徴を同定する。
- 参考スコア（独自算出の注目度）: 39.00971122472004
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the matrix completion problem that leverages hierarchical similarity
graphs as side information in the context of recommender systems. Under a
hierarchical stochastic block model that well respects practically-relevant
social graphs and a low-rank rating matrix model, we characterize the exact
information-theoretic limit on the number of observed matrix entries (i.e.,
optimal sample complexity) by proving sharp upper and lower bounds on the
sample complexity. In the achievability proof, we demonstrate that probability
of error of the maximum likelihood estimator vanishes for sufficiently large
number of users and items, if all sufficient conditions are satisfied. On the
other hand, the converse (impossibility) proof is based on the genie-aided
maximum likelihood estimator. Under each necessary condition, we present
examples of a genie-aided estimator to prove that the probability of error does
not vanish for sufficiently large number of users and items. One important
consequence of this result is that exploiting the hierarchical structure of
social graphs yields a substantial gain in sample complexity relative to the
one that simply identifies different groups without resorting to the relational
structure across them. More specifically, we analyze the optimal sample
complexity and identify different regimes whose characteristics rely on quality
metrics of side information of the hierarchical similarity graph. Finally, we
present simulation results to corroborate our theoretical findings and show
that the characterized information-theoretic limit can be asymptotically
achieved.
- Abstract（参考訳）: 本稿では,階層的類似性グラフを推薦システムのコンテキストにおける側情報として活用する行列補完問題について検討する。
実有意な社会グラフと低ランク格付け行列をよく尊重する階層的確率ブロックモデルの下で,サンプル複雑性の鋭い上下境界を証明し,観測された行列エントリ数(すなわち最適なサンプル複雑性)の正確な情報理論的限界を特徴付ける。
達成可能性証明では, 十分な条件が満たされれば, 十分な数のユーザやアイテムに対して, 最大推定器の誤差の確率がなくなることを示す。
一方、逆証明 (impossibility) は genie-aided maximum max estimator に基づいている。
各条件下では,十分な数のユーザとアイテムに対してエラーの確率が失われないことを示すために,ジェニー支援推定器の例を示す。
この結果の重要な結果の1つは、ソーシャルグラフの階層構造を利用すると、それらの間の関係構造に頼らずに、単に異なるグループを識別するのに対して、サンプルの複雑さが大幅に向上するということである。
より具体的には、最適なサンプルの複雑さを分析し、階層的類似性グラフの側情報の品質指標に依存する特徴を識別する。
最後に, 理論的知見を裏付けるシミュレーション結果を示し, 特徴的情報理論の限界を漸近的に達成できることを示す。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Entry-Specific Bounds for Low-Rank Matrix Completion under Highly
Non-Uniform Sampling [10.824999179337558]
行列全体よりも小さい部分行列上で推定アルゴリズムを実行する方がよく、時には最適であることを示す。
我々の境界は、各エントリを局所的なサンプリング確率の関数として推定する難しさを特徴付ける。
論文 参考訳（メタデータ） (2024-02-29T23:24:43Z) - Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
非一様ハイパーグラフ化ブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討
文献ではじめて、この一様でないケース下での正確な回復のための鋭いしきい値が、小さな制約の下で確立された。
しきい値を超えると正確な回復を達成でき、正確な回復が不可能な場合には最小の確率で達成できる2つの効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-04-25T20:30:33Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳（メタデータ） (2022-10-21T13:19:45Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Matrix Completion with Hierarchical Graph Side Information [39.00971122472004]
ソーシャルグラフやアイテム類似性グラフを副次情報として活用する行列補完問題を考える。
我々は階層的なグラフクラスタリングから始まる普遍的でパラメータフリーで計算効率のよいアルゴリズムを開発した。
我々は、我々の理論的結果を裏付けるために、合成および実世界のデータセットに関する広範な実験を行う。
論文 参考訳（メタデータ） (2022-01-02T03:47:41Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳（メタデータ） (2021-10-12T02:21:30Z) - Probabilistic Simplex Component Analysis [66.30587591100566]
PRISMは、データ循環記述のシンプルさの頂点をデータから識別する確率論的シンプルコンポーネント分析手法である。
この問題には多様な応用があり、最も注目すべきはリモートセンシングにおけるハイパースペクトルアンミックスと機械学習における非負行列分解である。
論文 参考訳（メタデータ） (2021-03-18T05:39:00Z) - Goal-directed Generation of Discrete Structures with Conditional
Generative Models [85.51463588099556]
本稿では,強化学習目標を直接最適化し,期待される報酬を最大化するための新しいアプローチを提案する。
提案手法は、ユーザ定義プロパティを持つ分子の生成と、所定の目標値を評価する短いピソン表現の同定という2つのタスクで検証する。
論文 参考訳（メタデータ） (2020-10-05T20:03:13Z) - Discrete-Valued Latent Preference Matrix Estimation with Graph Side
Information [12.836994708337144]
最適なサンプルの複雑さにマッチするアルゴリズムを開発する。
我々のアルゴリズムはエラーをモデル化し、予測性能の点で既存のアルゴリズムより優れている。
論文 参考訳（メタデータ） (2020-03-16T06:29:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。