論文の概要: Fairness constraints can help exact inference in structured prediction

• arxiv url: http://arxiv.org/abs/2007.00218v1
• Date: Wed, 1 Jul 2020 04:11:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-14 22:00:05.616019
• Title: Fairness constraints can help exact inference in structured prediction
• Title（参考訳）: 公正制約は構造化予測における正確な推論に役立つ
• Authors: Kevin Bello and Jean Honorio
• Abstract要約: 直交連結グラフ$G$と2進ラベルの真のベクトルを持つ生成モデルについて検討する。 フェアネスとモデル性能の間の既知のトレードオフとは対照的に、フェアネス制約の追加は正確なリカバリの確率を向上させる。
• 参考スコア（独自算出の注目度）: 37.76221231305701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many inference problems in structured prediction can be modeled as maximizing a score function on a space of labels, where graphs are a natural representation to decompose the total score into a sum of unary (nodes) and pairwise (edges) scores. Given a generative model with an undirected connected graph $G$ and true vector of binary labels, it has been previously shown that when $G$ has good expansion properties, such as complete graphs or $d$-regular expanders, one can exactly recover the true labels (with high probability and in polynomial time) from a single noisy observation of each edge and node. We analyze the previously studied generative model by Globerson et al. (2015) under a notion of statistical parity. That is, given a fair binary node labeling, we ask the question whether it is possible to recover the fair assignment, with high probability and in polynomial time, from single edge and node observations. We find that, in contrast to the known trade-offs between fairness and model performance, the addition of the fairness constraint improves the probability of exact recovery. We effectively explain this phenomenon and empirically show how graphs with poor expansion properties, such as grids, are now capable to achieve exact recovery with high probability. Finally, as a byproduct of our analysis, we provide a tighter minimum-eigenvalue bound than that of Weyl's inequality.
• Abstract（参考訳）: 構造化予測における多くの推論問題はラベル空間上のスコア関数を最大化するものとしてモデル化することができ、グラフは総スコアをユニタリ(ノード)とペアワイズ(エッジ)の合計に分解する自然な表現である。 有向連結グラフ $g$ とバイナリラベルの真のベクトルを持つ生成モデルが与えられたとき、以前、$g$ が完全グラフや$d$-正規展開器のような良好な拡張特性を持つとき、(高い確率と多項式時間で)真のラベルを各エッジとノードの単一のノイズ観測から正確に回復できることが示されている。 我々はGlobersonらによる以前に研究された生成モデル(2015)を統計的パリティの概念の下で解析した。 すなわち、公正なバイナリノードラベルが与えられた場合、単一エッジとノードの観測から、高い確率と多項式時間で公平な割り当てを回復できるかどうかを問う。 フェアネスとモデル性能の間の既知のトレードオフとは対照的に、フェアネス制約の追加は正確なリカバリの確率を向上させる。 この現象を効果的に説明し、グリッドのような拡張性に乏しいグラフが、高い確率で正確な回復を達成できることを実証的に示す。 最後に、分析の副産物として、ワイルの不等式よりも強い最小固有値が与えられる。

関連論文リスト

• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。 近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。 非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
  論文  参考訳（メタデータ） (2024-10-31T15:56:50Z)
• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。 相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
  論文  参考訳（メタデータ） (2023-02-10T18:21:35Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• An Interpretable Graph Generative Model with Heterophily [38.59200985962146]
  ヘテロフィリーを捉えるのに十分な表現性を持つ最初のエッジ非依存グラフ生成モデルを提案する。 我々の実験は、様々な重要なアプリケーションタスクに対して、我々のモデルの有効性を実証する。
  論文  参考訳（メタデータ） (2021-11-04T17:34:39Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
  2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。 p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。 sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
  論文  参考訳（メタデータ） (2021-01-29T21:49:50Z)
• Residual Correlation in Graph Neural Network Regression [39.54530450932135]
  我々は条件付き独立仮定が予測力を著しく制限していることを示します。 この問題を解釈可能かつ効率的なフレームワークで解決する。 我々のフレームワークは、競合するベースラインよりもかなり高い精度を実現している。
  論文  参考訳（メタデータ） (2020-02-19T16:32:54Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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