論文の概要: Optimal Transport for Measures with Noisy Tree Metric
- arxiv url: http://arxiv.org/abs/2310.13653v3
- Date: Fri, 1 Mar 2024 02:23:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-04 14:09:51.057672
- Title: Optimal Transport for Measures with Noisy Tree Metric
- Title(参考訳): 騒音木量測定器の最適搬送
- Authors: Tam Le, Truyen Nguyen, Kenji Fukumizu
- Abstract要約: 木メートル空間上での確率測度に対する最適輸送問題について検討する。
一般に、1つの空間でサポートされている測度であっても、このアプローチは計算が難しい。
我々は、ロバスト OT が計量特性を満たすことを示し、負の定値であることを示す。
- 参考スコア(独自算出の注目度): 29.950797721275574
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study optimal transport (OT) problem for probability measures supported on
a tree metric space. It is known that such OT problem (i.e., tree-Wasserstein
(TW)) admits a closed-form expression, but depends fundamentally on the
underlying tree structure over supports of input measures. In practice, the
given tree structure may be, however, perturbed due to noisy or adversarial
measurements. To mitigate this issue, we follow the max-min robust OT approach
which considers the maximal possible distances between two input measures over
an uncertainty set of tree metrics. In general, this approach is hard to
compute, even for measures supported in one-dimensional space, due to its
non-convexity and non-smoothness which hinders its practical applications,
especially for large-scale settings. In this work, we propose novel uncertainty
sets of tree metrics from the lens of edge deletion/addition which covers a
diversity of tree structures in an elegant framework. Consequently, by building
upon the proposed uncertainty sets, and leveraging the tree structure over
supports, we show that the robust OT also admits a closed-form expression for a
fast computation as its counterpart standard OT (i.e., TW). Furthermore, we
demonstrate that the robust OT satisfies the metric property and is negative
definite. We then exploit its negative definiteness to propose positive
definite kernels and test them in several simulations on various real-world
datasets on document classification and topological data analysis.
- Abstract(参考訳): 木メートル空間上での確率測度に対する最適輸送(OT)問題について検討する。
そのようなot問題(すなわちtree-wasserstein (tw))は閉形式表現を許容することは知られているが、基本的には入力測度の支持よりも根底にある木構造に依存する。
実際には、与えられた木構造はノイズや逆数の測定によって乱れてしまうことがある。
この問題を軽減するために、木メトリクスの不確実性セット上の2つの入力測度間の最大距離を考えるmax-min robust otアプローチに従う。
一般に、このアプローチは一次元空間で支持される測度に対しても計算が困難であり、これは非凸性と非滑らか性が実用的応用、特に大規模設定を妨げるためである。
そこで本研究では,木構造を多様に網羅したエッジ削除/付加のレンズから,新しい不確実性の木のメトリクスセットを提案する。
したがって,提案する不確実性集合の上に構築し,木構造をサポートよりも活用することにより,ロバストなotは高速計算のための閉形式式を標準ot(すなわちtw)として認めていることを示す。
さらに,ロバストな ot が計量特性を満たし負定値であることを示す。
次に、その負定性を利用して正定値カーネルを提案し、文書分類と位相データ解析に関する様々な実世界のデータセット上でのいくつかのシミュレーションで検証する。
関連論文リスト
- Topology-Aware Uncertainty for Image Segmentation [19.248891926246383]
このようなタスクに対する不確実性の推定に重点を置いているので、人間のアノテータが検証できるように、非常に不確実でエラーを起こしやすい構造を特定できる。
本稿では,隣接する構造物を考慮に入れながら構造物の不確かさを推定する共同予測モデルを提案する。
また,各構造に固有の不確かさをモデル化する新しい確率的DMTを提案する。
論文 参考訳(メタデータ) (2023-06-09T05:01:55Z) - Learning Ultrametric Trees for Optimal Transport Regression [10.524752369156337]
与えられた離散距離空間に対して最適な木構造を求める。
私たちのキーとなるアイデアの1つは、問題を超測度空間に配置することである。
論文 参考訳(メタデータ) (2022-10-21T22:54:42Z) - Social Interpretable Tree for Pedestrian Trajectory Prediction [75.81745697967608]
本稿では,このマルチモーダル予測課題に対処するため,SIT(Social Interpretable Tree)と呼ばれる木に基づく手法を提案する。
木の根から葉までの経路は、個々の将来の軌跡を表す。
ETH-UCYとStanford Droneのデータセットによる実験結果からは,手作り木にもかかわらず,我々の手法が最先端の手法の性能に適合または超えることを示した。
論文 参考訳(メタデータ) (2022-05-26T12:18:44Z) - Lassoed Tree Boosting [53.56229983630983]
有界断面変動のカドラー関数の大きな非パラメトリック空間において,早期に停止するn-1/4$ L2の収束速度を持つ勾配向上木アルゴリズムを証明した。
我々の収束証明は、ネストしたドンスカー類の経験的損失最小化子による早期停止に関する新しい一般定理に基づいている。
論文 参考訳(メタデータ) (2022-05-22T00:34:41Z) - Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
スペクトルトップダウン・リカバリ (STDR) は、大きな潜在木モデルを推定するための分割・コンカレントアプローチである。
STDRの分割ステップは非ランダムです。
代わりに、観測されたノードに関連する適切なラプラシア行列のFiedlerベクトルに基づいている。
私達はSTDRが統計的に一貫性があることを証明し、高い確率で木を正確に回復するために必要なサンプルの数を縛ります。
論文 参考訳(メタデータ) (2021-02-26T02:47:42Z) - Entropy Partial Transport with Tree Metrics: Theory and Practice [5.025654873456756]
我々は,質量の異なる木上の非負測度に対するtextitentropy partial transport (ept)問題を考える。
高速計算と負の確定性を認める新しい EPT 規則化を提案する。
我々は、正規化が効果的な近似をもたらすことを実証的に証明する。
論文 参考訳(メタデータ) (2021-01-24T17:04:24Z) - SGA: A Robust Algorithm for Partial Recovery of Tree-Structured
Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。
Katiyarら。
(2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。
統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文 参考訳(メタデータ) (2021-01-22T01:57:35Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳(メタデータ) (2020-10-21T19:38:57Z) - Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
我々はUniversal Dependency Treebankから多くの言語における最先端の出力を分析する。
最悪の制約違反率は24%です。
論文 参考訳(メタデータ) (2020-10-06T08:31:14Z) - Estimation and Inference with Trees and Forests in High Dimensions [23.732259124656903]
浅い木は、CARTの実証的なMSE基準により、周囲の次元$d$に対数的にのみ依存するMSEレートを達成する。
また,本研究の結果から,完全に成長した森林はMSEの速さを達成でき,その予測も正直に正常であることが示唆された。
論文 参考訳(メタデータ) (2020-07-07T05:45:32Z) - $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a
Robust Divergence Estimator [95.71091446753414]
最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。
本手法は既存の不一致対策よりも高いロバスト性を実現する。
論文 参考訳(メタデータ) (2020-06-13T06:09:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。