# (参考訳) 指数収束率による弱監視の曖昧化 [全文訳有]

Disambiguation of weak supervision with exponential convergence rates ( http://arxiv.org/abs/2102.02789v1 )

ライセンス: CC BY 4.0
Vivien Cabannes, Francis Bach, Alessandro Rudi(参考訳) 教師付き学習を通じてアプローチする機械学習には、高価なデータアノテーションが必要である。 これは、データが不完全だが差別的な情報でアノテートされる弱い教師付き学習を動機付ける。 本論文では,与えられた入力から,潜在的なターゲットの集合が与えられるような,弱い監督の例である部分的ラベリングに焦点を当てる。 本稿では,弱監視から全監督を回復するための曖昧化原理について検討し,経験的曖昧化アルゴリズムを提案する。 古典的学習可能性仮定の下でアルゴリズムの指数関数収束率を証明し,本手法の有用性を実例で示す。

Machine learning approached through supervised learning requires expensive annotation of data. This motivates weakly supervised learning, where data are annotated with incomplete yet discriminative information. In this paper, we focus on partial labelling, an instance of weak supervision where, from a given input, we are given a set of potential targets. We review a disambiguation principle to recover full supervision from weak supervision, and propose an empirical disambiguation algorithm. We prove exponential convergence rates of our algorithm under classical learnability assumptions, and we illustrate the usefulness of our method on practical examples.
公開日: Thu, 4 Feb 2021 18:14:32 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。


    Page: /      
1 2 0 2 b e F 4 1 2 0 2 b e F 4 0.85
] G L . ] G L。 0.79
s c [ 1 v 9 8 7 2 0 sc [ 1 v 9 8 7 2 0 0.68
. 2 0 1 2 : v i X r a . 2 0 1 2 : v i X r a 0.85
Disambiguation of weak supervision with exponential 指数関数による弱監督の曖昧化 0.57
convergence rates Vivien Cabannes INRIA – ENS – PSL∗ 収束率 Vivien Cabannes INRIA – ENS – PSL。 0.80
Paris, France Francis Bach パリ、フランス フランシス・バッハ 0.75
Paris, France Alessandro Rudi INRIA – ENS – PSL∗ パリ、フランス Alessandro Rudi INRIA – ENS – PSL。 0.87
Paris, France February 5, 2021 パリ、フランス 2021年2月5日 0.75
Abstract Machine learning approached through supervised learning requires expensive annotation of data. 概要 教師付き学習を通じてアプローチする機械学習には、高価なデータアノテーションが必要である。 0.48
This motivates weakly supervised learning, where data are annotated with incomplete yet discriminative information. これは、データが不完全だが差別的な情報でアノテートされる弱い教師付き学習を動機付ける。 0.49
In this paper, we focus on partial labelling, an instance of weak supervision where, from a given input, we are given a set of potential targets. 本論文では,与えられた入力から,潜在的なターゲットの集合が与えられるような,弱い監督の例である部分的ラベリングに焦点を当てる。 0.80
We review a disambiguation principle to recover full supervision from weak supervision, and propose an empirical disambiguation algorithm. 本稿では,弱監視から全監督を回復するための曖昧化原理について検討し,経験的曖昧化アルゴリズムを提案する。
訳抜け防止モード: 曖昧さの原則を見直します 弱監視から全監督を回復し、経験的曖昧化アルゴリズムを提案する。
We prove exponential convergence rates of our algorithm under classical learnability assumptions, and we illustrate the usefulness of our method on practical examples. 古典的学習可能性仮定の下でアルゴリズムの指数関数収束率を証明し,本手法の有用性を実例で示す。 0.78
1 Introduction In many applications of machine learning, such as recommender systems, where an input 𝑥 characterizing a user should be matched with a target 𝑦 representing an ordering of a large number 𝑚 of items, accessing fully supervised data (𝑥, 𝑦) is not an option. 1 導入 推薦システムなどの機械学習の多くの応用では、ユーザを特徴付ける入力xが多数の項目の順序を表すターゲットyと一致すべきであり、完全な教師付きデータ(x, y)へのアクセスはオプションではない。 0.71
Instead, one should expect weak information on the target 𝑦, which could be a list of previously taken (if items are online courses), watched (if items are plays), etc., items by a user characterized by the feature vector 𝑥. 代わりに、対象の y についての弱い情報(アイテムがオンラインコースの場合)、視聴(アイテムがプレイの場合)、特徴ベクトル x によって特徴づけられるユーザーによるアイテムのリストである可能性がある)を期待すべきである。 0.78
This motivates weakly supervised learning, aiming at learning a mapping from inputs to targets in such a setting where tools from supervised learning can not be applied off-the-shelves. これは弱い教師付き学習を動機付け、教師付き学習のツールが本棚外で適用できないような環境で、入力からターゲットへのマッピングを学ぶことを目的としている。 0.54
Recent applications of weakly supervised learning showcase impressive results in solving complex tasks such as action retrieval on instructional videos (Miech et al., 2019), image semantic segmentation (Papandreou et al., 2015), salient object detection (Wang et al., 2017), 3D pose estimation (Dabral et al., 2018), text-to-speech synthesis (Jia et al., 2018), to name a few. 最近の弱い教師付き学習の応用は、授業ビデオのアクション検索(miech et al., 2019)、画像意味セグメンテーション(papandreou et al., 2015)、salient object detection(wang et al., 2017)、3d pose estimation(dabral et al., 2018)、text-to-speech synthesis(jia et al., 2018)といった複雑なタスクの解決において印象的な結果を示している。 0.77
However, those applications of weakly supervised learning are usually based on clever heuristics, and theoretical foundations of learning from weakly supervised data are scarce, especially when compared to statistical learning literature on supervised learning (Vapnik, 1995; Boucheron et al., 2005; Steinwart and Christmann, 2008). しかしながら、弱い教師付き学習の応用は通常、巧妙なヒューリスティックに基づいており、弱い教師付きデータからの学習の理論的基礎は、特に教師付き学習に関する統計的学習文献(Vapnik, 1995; Boucheron et al., 2005; Steinwart and Christmann, 2008)と比較すると、ほとんどない。 0.71
We aim to provide a step in this direction. 私たちはこの方向へのステップを提供することを目指しています。 0.56
In this paper, we focus on partial labelling, a popular instance of weak supervision, approached with a structured prediction point of view Ciliberto et al. 本論文では,Ciliberto et alという構造化された予測点にアプローチした,弱い監督の一般的な例である部分ラベリングに注目する。 0.71
(2020). We detail this setup in Section 2. (2020). この設定はセクション2で詳しく説明します。 0.77
Our contributions are organized as follows. 当社の貢献は以下の通りです。 0.69
• In Section 3, we introduce a disambiguation algorithm to retrieve fully supervised samples from weakly supervised ones, before applying off-the-shelf supervised learning algorithms to the completed dataset. •第3節では,既製の教師付き学習アルゴリズムを完成データセットに適用する前に,弱監督付きサンプルから完全に教師付きサンプルを取得するための曖昧化アルゴリズムについて紹介する。 0.62
• In Section 4, we prove exponential convergence rates of our algorithm, in term of the fully supervised •第4節では、完全に監督されたアルゴリズムの指数収束率を証明します。 0.73
excess of risk, given classical learnability assumptions. 古典的な学習可能性の前提から リスクを超過します 0.57
• In Section 5, we explain why disambiguation algorithms are intrinsically non-convex, and provide guidelines • 第5節では、曖昧化アルゴリズムが本質的に凸でない理由を説明し、ガイドラインを提供する。
訳抜け防止モード: • 第5節では、曖昧化アルゴリズムが本質的に非凸である理由を説明する。 ガイドラインや
based on well-grounded heuristics to implement our algorithm. アルゴリズムを実装するための基礎的なヒューリスティックに基づいている。 0.48
∗Institut National de Recherche en Informatique et en Automatique – Département d’Informatique de l’École Normale Supérieure – PSL オートマティック・インフォマティクス・インフォマティクス・インスティテュート・デ・デ・インフォマティック・デ・エコール・ノーマル・シュペリエール(Supérieure informatique de l’École Normale Supérieure) - PSL 0.53
Research University. 1 研究大学。 1 0.80
We end this paper with a review of literature in Section 6, before showcasing the usefulness of our method on practical examples in Section 7, and opening on perspectives in Section 8. 本論文は,第6節の文献のレビューで終わり,第7節の実践例と第8節の視点の展開について,本手法の有用性を示す。 0.76
2 Disambiguation of Partial Labelling In this section, we review the supervised learning setup, introduce the partial labelling problem along with a principle to tackle this instance of weak supervision. 2 部分ラベルの曖昧さ このセクションでは、教師付き学習のセットアップを検討し、部分ラベル問題と弱い監督のこのインスタンスに取り組む原則を紹介します。 0.64
Algorithms can be formalized as mapping an input 𝑥 to a desired output 𝑦, respectively belonging to an input space X and an output space Y. アルゴリズムは入力空間 x と所望の出力 y をそれぞれ入力空間 x と出力空間 y にマッピングするものとして定式化することができる。 0.89
Machine learning consists in automating the design of the mapping 𝑓 : X → Y, based on a joint distribution 𝜇 ∈ ΔX×Y over input/output pairings (𝑥, 𝑦) and a loss function ℓ : Y × Y → R, measuring the error cost of outputting 𝑓 (𝑥) when one should have output 𝑦. 機械学習は、入出力ペアリング (x, y) とロス関数 l : Y × Y → R 上の共同分布 μ ∈ ΔX×Y に基づいて、マッピング f : X → Y の設計を自動化し、出力 y を持つべきときに f (x) を出力する誤差コストを測定する。 0.85
The optimal mapping is defined as satisfying 最適なマッピングは満足と定義されます。 0.62
𝑓 ∗ ∈ arg min 𝑓 :X→Y f ∗ ∈ arg min f :X→Y 0.96
E( 𝑋,𝑌)∼𝜇 [ℓ( 𝑓 (𝑋), 𝑌)] . E( 𝑋,𝑌)∼𝜇 [ℓ( 𝑓 (𝑋), 𝑌)] . 0.68
(1) In supervised learning, it is assumed that one does not have access to the full distribution 𝜇, but only to independent samples (𝑋𝑖, 𝑌𝑖)𝑖≤𝑛 ∼ 𝜇⊗𝑛. (1) 教師あり学習では、完全な分布 μ へのアクセスはないが、独立したサンプル (xi, yi)iبn にのみアクセスすると仮定される。 0.80
In practice, accessing such samples means building a dataset of examples. 実際にそのようなサンプルにアクセスすることは、サンプルのデータセットを構築することを意味する。 0.45
While input data (𝑥𝑖) are usually easily accessible, getting output pairings (𝑦𝑖) generally requires careful annotation, which is both time-consuming and expensive. 入力データ(xi)は一般に簡単にアクセスできますが、yi(output pairing)の取得には一般的に注意深いアノテーションが必要です。 0.73
For example, in image classification, (𝑥𝑖) can be collected by scrapping images over the Internet. 例えば、画像分類では、インターネットで画像をスクラップすることで(xi)を収集できます。 0.76
Subsequently a “data labeller” might be ask to recognize a rare feline 𝑦𝑖 on an image 𝑥𝑖. その後、“data labeller”がイメージxi上のまれなネコのyiを認識するように要求される。 0.71
While getting 𝑦𝑖 will be hard in this setting, recognizing that it is a feline and describing elements of color and shape is easy, and already helps to determine what outputs 𝑓 (𝑥𝑖) are acceptable. この設定では、yiの取得は難しいが、それが糞便であることを認識し、色と形状の要素を記述することは容易であり、f(xi)が許容される出力を決定するのに既に役立っている。 0.67
A second example is given when pooling a known population (𝑥𝑖) to get estimation of their political orientation (𝑦𝑖), one might get information from recent election of percentage of voters across the political landscape, leading to global constraints that (𝑦𝑖) should verify. 第2の例は、既知の人口(xi)をプールして政治的指向(yi)を推定すると、近年の選挙結果から政治状況全体にわたる有権者の割合の情報が得られ、(yi)が検証すべき世界的制約が生じる可能性があることである。 0.71
A supervision that gives information on (𝑦𝑖)𝑖≤𝑛 without giving its precise value is called weak supervision. ii)i≤nの正確な値を与えることなく情報を与える監督は弱監督と呼ばれる。 0.63
Partial labelling, also known as “superset learning”, is an instance of weak supervision, in which, for an input 𝑥, we do not access the precise label 𝑦 but only a set 𝑠 of potential labels, 𝑦 ∈ 𝑠 ⊂ Y. 部分ラベリング (partial labelling) あるいは「スーパーセット学習 (superset learning)」は、弱監督の例であり、入力 x に対して、正確なラベル y にアクセスするのではなく、潜在的なラベルの集合 s のみにアクセスする。 0.66
For example, on a caracal image 𝑥, one might not get the label “caracal” 𝑦, but the set 𝑠 “feline”, containing all the labels 𝑦 corresponding to felines. 例えば、カラカル画像 x において、"caracal" y というラベルは得られないかもしれないが、集合 s は "feline" であり、猫に対応するすべてのラベル y を含む。 0.71
It is modelled through a distribution 𝜈 ∈ ΔX×2Y over X × 2Y generating samples (𝑋, 𝑆), which should be compatible with the fully supervised distribution 𝜇 ∈ ΔX×Y as formalized by the following definition. X × 2Y 生成サンプル (X, S) 上の分布 ν ∈ ΔX×2Y を通じてモデル化されるが、これは次の定義によって形式化された完全監督分布 μ ∈ ΔX×Y と互換性がある。 0.79
Definition 1 (Compatibility, Cabannes et al. 定義 1 (Compatibility, Cabannes et al)。 0.86
(2020)). A fully supervised distribution 𝜇 ∈ ΔX×Y is compatible with a weakly supervised distribution 𝜈 ∈ ΔX×Y, denoted by 𝜇 (cid:96) 𝜈 if there exists an underlying distribution 𝜋 ∈ ΔX×Y×2Y , such that 𝜇, and 𝜈, are the respective marginal distributions of 𝜋 over X ×Y and X × 2Y, and such that 𝑦 ∈ 𝑠 for any tuple (𝑥, 𝑦, 𝑠) in the support of 𝜋 (or equivalently 𝜋|𝑠 ∈ Δ𝑠, with 𝜋|𝑠 denoting the conditional distribution of 𝜋 given 𝑠). (2020)). 完全教師付き分布 μ ∈ ΔX×Y は、μ (cid:96) ν で表される弱教師付き分布 ν ∈ ΔX×Y と互換性があり、μ と ν が X ×Y および X × 2Y 上の π ∈ ΔX×Y×2Y の各々の辺分布であり、π の支持の下で任意のタプル (x, y, s) に対する y ∈ s が π の条件分布を表す π|s であるような基底分布 π ∈ ΔX×2Y が存在する。 0.85
This definition means that a weakly supervised sample (𝑋, 𝑆) ∼ 𝜈 can be thought as proceeding from a fully supervised sample (𝑋, 𝑌) ∼ 𝜇 after loosing information on 𝑌 according to the sampling of 𝑆 ∼ 𝜋| 𝑋,𝑌. この定義は、弱教師付きサンプル (X, S) ^ ν が、完全な教師付きサンプル (X, Y) ^ μ から、S ^ π| X,Y のサンプリングに従って、Y 上の情報を略奪した後、進行すると考えられることを意味する。 0.64
The goal of partial labelling is still to learn 𝑓 ∗ from Eq. 部分ラベリングの目標は、まだ Eq から f ∗ を学ぶことである。 0.68
(1), yet without accessing a fully supervised distribution 𝜇 ∈ ΔX×Y but only the weakly supervised distribution 𝜈 ∈ ΔX×2Y . 1) 完全に教師付き分布 μ ∈ δx×y にアクセスすることなく、弱い教師付き分布 ν ∈ δx×2y のみにアクセスする。
訳抜け防止モード: (1) 完全に教師付き分布 μ ∈ ΔX×Y にアクセスする しかし弱監督分布 ν ∈ ΔX×2Y のみである。
As such, this is an ill-posed problem, since 𝜈 does not discriminate between all 𝜇 compatible with it. したがって、ν は μ と対応するすべての μ を判別しないため、これは不適切な問題である。 0.67
Following lex parsimoniae, Cabannes et al. Lex parsimoniaeに続いて、Cabannes et al。 0.70
(2020) have suggested to look for 𝜇 such that the labels are the most deterministic function of the inputs, which they measure with a loss-based “variance”, leading to the disambiguation inf 𝑓 :X→Y (2020)は、ラベルが入力の最も決定論的関数であり、損失ベースの「ばらつき」で測定し、不明瞭な inf f :X→Y につながるような μ を求めることを提案している。 0.74
E( 𝑋,𝑌)∼𝜇 [ℓ( 𝑓 (𝑋), 𝑌)] , E( 𝑋,𝑌)∼𝜇 [ℓ( 𝑓 (𝑋), 𝑌)] , 0.68
(2) 𝜇∗ ∈ arg min (2) μ∗ ∈ arg min 0.92
𝜇(cid:96)𝜈 μ(cid:96)ν 0.88
and to the definition of the optimal mapping 𝑓 ∗ : X → Y そして、最適写像 f ∗ : X → Y の定義に従えば、 0.76
by 𝑓 ∗ ∈ arg min 𝑓 :X→Y E( 𝑋,𝑆)∼𝜈(cid:2)inf 𝑦∈𝑆 ℓ( 𝑓 (𝑋), 𝑦)(cid:3), matching a prior formulation based on infimum loss (Cour arg min f :X→Y E(X,S)\ν(cid:2)inf y∈S l(f(X), y(cid:3) により、最小損失(Cour)に基づく事前定式化に一致する。 0.86
This principle is motivated by Theorem 1 of Cabannes et al. この原理は、Cabannes et alの Theorem 1 によって動機づけられます。 0.67
(2020) showing that 𝑓 ∗ in Eq. (2020) eq における f ∗ を示す。 0.90
(3) is characterized (3) (3)の特徴 (3) 0.77
𝑓 ∗ ∈ arg min 𝑓 :X→Y f ∗ ∈ arg min f :X→Y 0.96
E( 𝑋,𝑌)∼𝜇∗ [ℓ( 𝑓 (𝑋), 𝑌)] . E( 𝑋,𝑌)∼𝜇∗ [ℓ( 𝑓 (𝑋), 𝑌)] . 0.72
2 2 0.85
et al., 2011; Luo and Orabona, 2010; Hüllermeier, 2014). 2011, 2011, Luo and Orabona, 2010; Hüllermeier, 2014)。 0.68
In practice, it means that if (𝑆|𝑋 = 𝑥) has probability 50% to be the set “feline” and 50% the set “orange with black stripes”, (𝑌|𝑋 = 𝑥) should be considered as 100% “tiger”, rather than 20% “cat”, 30% “lion” and 50% “orange car with black stripes”, which could also explain (𝑆|𝑋 = 𝑥). 実際には、(s|x = x) が集合 "feline" である確率50%、集合が "orange with black stripes" である場合、(y|x = x) は、20% "cat" 、30% "lion" 、50% "orange car with black stripes" ではなく、100% "tiger" と見なされるべきである(s|x = x)。 0.76
Similarly to supervised learning, partial labelling consists in retrieving 𝑓 ∗ without accessing 𝜈 but only samples (𝑋𝑖, 𝑆𝑖)𝑖≤𝑛 ∼ 𝜈⊗𝑛. 教師付き学習と同様に、部分的ラベリングは ν をアクセスせずに f ∗ を検索することであり、サンプル (xi, si) のみである。 0.63
Remark 2 (Measure of determinism). remark 2 (決定論の指標)。 0.69
Eq. (2) is not the only variational way to push towards distribution where labels are deterministic function of the inputs. eqだ (2) は、ラベルが入力の決定論的関数である分布に向かって進む唯一の変分方法ではない。 0.75
For example, one could minimize entropy (e.g., Lienen and Hüllermeier, 2021). 例えば、エントロピーを最小化することができる(例えば、lienen and hüllermeier, 2021)。 0.79
However, a loss-based principle is appreciable since the loss usually encodes structures of the output space (Ciliberto et al., 2020), which will allow sample and computational complexity of consequent algorithms to scale with an intrinsic dimension of the space rather than the real one, e.g., 𝑚 rather than 𝑚! しかし、損失に基づく原理は、通常、損失は出力空間の構造を符号化する(Ciliberto et al., 2020)ので、これは、後続アルゴリズムのサンプルと計算の複雑さが、実数ではなく空間の本質的な次元でスケールできるようにするためである。 0.81
when Y = S𝑚 and ℓ is a suitable ranking loss (see Section 5.4 or Nowak-Vila et al., 2019). Y = Sm と l が適切なランク付け損失である場合(第5.4 節や Nowak-Vila et al., 2019 参照)。 0.75
3 Learning Algorithm In this section, given weakly supervised samples, we present a disambiguation algorithm to retrieve fully supervised samples based on an empirical expression of Eq. 本稿では,弱教師付きサンプルを与えられた場合,eqの経験的表現に基づいて教師付きサンプルを取得するための曖昧さ回避アルゴリズムを提案する。 0.65
(2), before learning a mapping from X to Y based on those fully supervised samples, according to Eq. 2) 完全に監視されたサンプルに基づいて X から Y へのマッピングを学ぶ前に、Eq によると。 0.76
(3). Given a partially labelled dataset D𝑛 = (𝑥𝑖, 𝑠𝑖)𝑖≤𝑛, sampled accordingly to 𝜈⊗𝑛, we retrieve fully supervised (3). 一部ラベル付きデータセット Dn = (xi, si)i≤n を ν に対してサンプリングすると、完全に教師付きとなる。 0.71
samples, based on the following empirical version of Eq. sample, based on the following empirical version of Eq. 0.84
(2), with 𝐶𝑛 =𝑖≤𝑛 𝑠𝑖 ⊂ Y 𝑛 (2) cn = ihtmln si , y n で 0.60
( ˆ𝑦𝑖)𝑖≤𝑛 ∈ arg min (𝑦𝑖)𝑖≤𝑛∈𝐶𝑛 (yi)i≤n ∈ arg min (yi)i≤n∈Cn 0.77
inf (𝑧𝑖)𝑖≤𝑛∈Y 𝑛 inf (zi)i≤n∈Y n 0.78
𝛼 𝑗(𝑥𝑖)ℓ(𝑧𝑖, 𝑦 𝑗), 𝛼 𝑗(𝑥𝑖)ℓ(𝑧𝑖, 𝑦 𝑗), 0.79
(4) seen as the approximation of 𝜇 by 𝑛−1𝑛 (4) n−1-n による μ の近似と見なされる 0.77
where (𝛼𝑖(𝑥))𝑖≤𝑛 is a set of weights measuring how much one should base its prediction for 𝑥 on the observations made at 𝑥𝑖. ここで (αi(x))i≤n は、x に対する予測を xi で行った観測にどれだけ基づけるべきかを測定する重みの集合である。
訳抜け防止モード: ここで (αi(x))i≤n はどのくらいの重さを測る重みの集合である xの予測は xiの観測に基づいてください
This formulation is motivated by the Bayes approximate rule proposed by Stone (1977), which can be Once fully supervised samples (𝑥𝑖, ˆ𝑦𝑖) have been recollected, one can learn 𝑓𝑛 : X → Y, approximating 𝑓 ∗, with classical supervised learning techniques. この定式化は、ストーン(1977)によって提案されたベイズ近似則(英語版)によって動機づけられており、これは一度完全に監督されたサンプル(xi, yi)が再記憶され、fn : X → Y を学習できる。
訳抜け防止モード: この定式化は、Stone (1977 ) によって提案されたベイズ近似則によって動機付けられる。 ひとたび完全に監督されたサンプル(xi, syi )が再コンパイルされる。 fn : X → Y, 近似 f ∗, 古典的な教師付き学習技術で
In this work, we will consider the structured prediction estimator introduced by Ciliberto et al. 本稿では,Cilibertoらによって導入された構造的予測推定器について考察する。 0.63
(2016), defined as 𝑖, 𝑗=1 𝛼 𝑗(𝑥𝑖)𝛿𝑥𝑖 ⊗ 𝛿𝑦 𝑗 in Eq. (2016年) i, j=1 α j(xi)δxi , δy j in Eq。 0.59
(2). 𝑛∑︁ 𝑖, 𝑗=1 (2). 𝑛∑︁ 𝑖, 𝑗=1 0.74
𝑛∑︁ 𝑖=1 𝑓𝑛(𝑥) ∈ arg min 𝑧∈Y 𝑛∑︁ 𝑖=1 fn(x) ∈ arg min z∈Y 0.71
𝛼𝑖(𝑥)ℓ(𝑧, ˆ𝑦𝑖). 𝛼𝑖(𝑥)ℓ(𝑧, ˆ𝑦𝑖). 0.85
(5) Weighting scheme 𝛼. (5) ウェイトスキーム α。 0.73
For the weighting scheme 𝛼, several choices are appealing. 重み付けスキームαでは、いくつかの選択肢が魅力的です。 0.53
Laplacian diffusion is one of them as it incorporates a prior on low density separation to boost learning (Zhu et al., 2003; Zhou et al., 2003; Bengio et al., 2006; Hein et al., 2007). ラプラシアの拡散は、学習を後押しするために低密度分離に先行したものである(Zhu et al., 2003; Zhou et al., 2003; Bengio et al., 2006; Hein et al., 2007)。 0.83
Kernel ridge regression is another due to its theoretical guarantees (Ciliberto et al., 2020). カーネルリッジ回帰は、その理論的保証(Ciliberto et al., 2020)による別の原因です。 0.66
In the theoretical analysis, we will use nearest neighbors. 理論的解析では、最も近い隣人を用いる。 0.73
Assuming X is endowed with a distance 𝑑, and assuming, for readability sake, that ties to define nearest neighbors do not happen, it is defined as X が距離 d で与えられると仮定し、可読性のために、最も近い隣人を定義する関係が起こらないと仮定すると、次のように定義される。 0.75
(cid:26) 𝑘−1 (cid:26) k−1 0.65
0 if 𝑛 𝛼𝑖(𝑥) = 0 もしそうなら 𝛼𝑖(𝑥) = 0.77
𝑗=1 1𝑑(𝑥,𝑥 𝑗)≤𝑑(𝑥,𝑥𝑖) ≤ 𝑘 otherwise, 𝑗=1 1𝑑(𝑥,𝑥 𝑗)≤𝑑(𝑥,𝑥𝑖) ≤ 𝑘 otherwise, 0.98
where 𝑘 is a parameter fixing the number of neighbors. ここで k は隣接する数を固定するパラメータである。 0.77
Our analysis, leading to Theorem 4, also holds for other local averaging methods such as partitioning or Nadaraya-Watson estimators. Theorem 4 に導かれる我々の分析は、パーティショニングやNadaraya-Watson 推定器など、他の局所的な平均化手法にも当てはまる。 0.67
4 Consistency Result In this section, we assume Y finite, and prove the convergence of 𝑓𝑛 towards 𝑓 ∗ as 𝑛, the number of samples, grows to infinity. 4 一貫性結果 この節では、Y は有限であると仮定し、fn の f ∗ への収束を n として証明する。
訳抜け防止モード: 4 一貫性の結果 このセクションでは、Y を有限と仮定します。 fn の f への収束を証明し n、サンプルの数、無限に成長します。
To derive such a consistency result, we introduce a surrogate problem that we relate to the risk このような一貫した結果を導出するために、我々はリスクに関連する代理問題を導入する。
訳抜け防止モード: このような一貫性のある結果を導出する。 リスクに関連する代理問題を導入し
3 3 0.85
through a calibration inequality. 校正の不等式を通して 0.54
We later assume that weights are given by nearest neighbors and review classical assumptions, that we work to derive exponential convergence rates. その後、重みは最寄りの近傍によって与えられ、指数収束率を導出するために働く古典的な仮定を見直しられると仮定する。 0.56
In the following, we are interested in bounding the expected generalization error, defined as 以下に示すように、期待される一般化誤差の有界化に関心がある。 0.61
E( 𝑓𝑛) = ED𝑛 R( 𝑓𝑛) − R( 𝑓 ∗), E( fn) = EDn R( fn) − R( f )) 0.78
(6) where R( 𝑓) = E( 𝑋,𝑌)∼𝜇∗ [ℓ( 𝑓 (𝑋), 𝑌)] , by a quantity that goes to zero, when 𝑛 goes to infinity. (6) ここで R(f) = E(X,Y) = μ∗ [l(f(X, Y)] は n が無限大となるとき 0 となる量である。 0.76
This implies, under boundedness of ℓ, convergence in probability (the randomness being inherited from D𝑛) of R( 𝑓𝑛) towards inf 𝑓 :X→Y R( 𝑓), which is referred as consistency of the learning algorithm.1 We first introduce a few objects. これは、l の有界性の下では、r(fn) の確率収束(確率性は fn から inf f :x→y r(f) へと変換される)が学習アルゴリズムの一貫性と呼ばれることを意味する。 0.68
Introduce 𝜋∗ ∈ ΔX×Y×2Y expressing the compatibility of 𝜇∗ and 𝜈 as in Disambiguation ground truth (𝑦∗ 𝑖 ). disambiguation ground truth において μ と ν の互換性を表す π ∈ ΔX×Y×2Y を導入する。 0.75
Definition 1. Given samples (𝑥𝑖, 𝑠𝑖)𝑖≤𝑛 forming a dataset D𝑛, we enrich this dataset by sampling 𝑦∗ 𝑖 ∼ 𝜋∗|𝑥𝑖,𝑠𝑖, which build an underlying dataset (𝑥𝑖, 𝑦∗ 𝑖 , 𝑠𝑖) sampled accordingly (𝜋∗)⊗𝑛. 定義1。 データセットdnを形成するサンプル(xi, si)iψnが与えられたとき、このデータセットをサンプリングすることで拡張し、それに応じてサンプリングされたデータセット(xi, y∗ i, si)を構築する。 0.76
Given D𝑛, while a priori, 𝑦∗ 𝑖 are random variables, sampled accordingly to 𝜋∗|𝑥𝑖,𝑠𝑖, because of the definition of 𝜇∗ (2), under basic definition ℓ( 𝑓 ∗(𝑥𝑖), 𝑦). 与えられた dn に対し、y∗ i は確率変数であるが、μ∗ (2) の定義から π∗|xi,si に対して、基本定義 l(f ∗(xi), y) の下で標本化される。 0.81
As such, they should be assumptions, they are actually deterministic, defined as 𝑦∗ seen as ground truth for ˆ𝑦𝑖. したがって、それらは実際には決定論的であり、イイの基底真理と見なされるy∗として定義される。 0.70
𝑖 = arg min𝑦∈𝑠𝑖 i = arg miny∈si 0.84
Surrogate estimates. The approximate Bayes rule was successfully analyzed recently through the prism of plug-in estimators by Ciliberto et al. 推定値。 近似ベイズ則はCilibertoらによるプラグイン推定器のプリズムを通じて最近解析に成功した。 0.61
(2020). While we will not cast our algorithm as a plug-in estimator, we will leverage this surrogate approach, introducing two mappings 𝜑 and 𝜓 from Y to an Hilbert space H such that (2020). アルゴリズムをプラグイン推定器としてキャスティングすることはないが、このサーロゲートアプローチを利用して、Y からヒルベルト空間 H への 2 つの写像 φ と φ を導入する。 0.77
(7) Such mappings always exist when Y is finite, and have been used to encode “problem structure” defined by the loss ℓ (Nowak-Vila et al., 2019). (7) そのようなマッピングは常に Y が有限であるときに存在し、ロス l (Nowak-Vila et al., 2019) によって定義される「問題構造」をエンコードするために使われてきた。 0.67
We introduce three surrogate quantities that will play a major role in the following analysis, they map X to H as 以下の分析において主要な役割を果たす3つの代理量を導入し、X を H に写す。 0.76
∀ 𝑧, 𝑦 ∈ Y, z, y ∈ Y である。 0.74
ℓ(𝑧, 𝑦) = (cid:104)𝜓(𝑧), 𝜑(𝑦)(cid:105) , l(z, y) = (cid:104)ψ(z), φ(y)(cid:105) , 0.96
𝑔∗(𝑥) = E𝜇∗ [𝜑(𝑌) | 𝑋 = 𝑥] , 𝑔∗(𝑥) = E𝜇∗ [𝜑(𝑌) | 𝑋 = 𝑥] , 0.94
𝑔𝑛(𝑥) = 𝛼𝑖(𝑥)𝜑( ˆ𝑦𝑖), 𝑔𝑛(𝑥) = 𝛼𝑖(𝑥)𝜑( ˆ𝑦𝑖), 0.81
𝑛∑︁ 𝑖=1 𝑛∑︁ 𝑛∑︁ 𝑖=1 𝑛∑︁ 0.59
(8) It is known that 𝑓 ∗ and 𝑓𝑛 are retrieved from 𝑔∗ and 𝑔𝑛, through the decoding, retrieving 𝑓 : X → Y from 𝑔 : X → H as (8) f∗ と fn が g∗ と gn から取り出され、デコードによって f : x → y を g : x → h から取り出すことが知られている。 0.85
𝑖=1 𝑛(𝑥) = 𝑔∗ 𝑖=1 𝑛(𝑥) = 𝑔∗ 0.78
𝛼𝑖(𝑥)𝜑(𝑦∗ 𝑖 ). 𝛼𝑖(𝑥)𝜑(𝑦∗ 𝑖 ). 0.93
𝑓 (𝑥) = arg min 𝑧∈Y f (x) = arg min z∈Y 0.96
(cid:104)𝜓(𝑧), 𝑔(𝑥)(cid:105) , (cid:104)ψ(z), g(x)(cid:105) , 1.00
(9) when 𝜇∗|𝑥 is a Dirac for all 𝑥 ∈ supp 𝜈X , for any weighting scheme that sums to one, i.e.,𝑛 (9) μ∗|x がすべての x ∈ supp νX に対して Dirac であるとき、重み付けスキームは 1 にまとめる。 0.81
which explains the wording of plug-in estimator (Ciliberto et al., 2020). プラグイン推定器(Ciliberto et al., 2020)の単語を説明します。 0.75
We now introduce a calibration inequality, that relates the error between 𝑓𝑛 and 𝑓 ∗ with surrogate error quantities. 本研究では,fn と f ∗ の誤差をサロゲート誤差量と関係付ける校正不等式を導入する。 0.72
Lemma 3 (Calibration inequality). Lemma 3 (Calibration inequality)。 0.74
When Y is finite, and the labels are a deterministic function of the input, i.e., 𝑖=1 𝛼𝑖(𝑥) = 1 for all 𝑥 ∈ supp 𝜈X , y が有限でラベルが入力の決定論的関数であるとき、すなわち、すべての x ∈ supp νx に対して i=1 αi(x) = 1 である。 0.77
(cid:13)(cid:13)𝐿1 𝑛(𝑋) − 𝑔∗(𝑋)(cid:13)(cid:13) > 𝛿(cid:1) , This lemma, proven in Appendix A.1, separates a part reading in(cid:13)(cid:13)𝑔𝑛 − 𝑔∗ (cid:13)(cid:13), due to the disambiguation error 𝑛 − 𝑔∗(cid:13)(cid:13) due to the consistency of the fully supervised learning algorithm. (cid:13)(cid:13)L1 n(X) − g∗(X)(cid:13)(cid:13) > δ(cid:1) , この補題は Appendix A.1 で証明され、完全教師付き学習アルゴリズムの整合性による曖昧な誤差 n − g∗(cid:13)(cid:13) のため、(cid:13)(cid:13)gn − g∗ (cid:13) を分離する。 0.84
The expression of the first part in(cid:13)(cid:13)𝑔∗ 最初の部分 (cid:13)(cid:13)g∗ の表現 0.89
(10) with 𝑐𝜓 = sup𝑧∈Y (cid:107)𝜓(𝑧)(cid:107), 𝑐𝜑 = sup𝑧∈Y (cid:107)𝜑(𝑦)(cid:107), and 𝛿 a parameter that depend on the geometry of ℓ and its decomposition through 𝜑. (10) {\displaystyle c} = supz∈Y (cid:107)\(z)(cid:10 7), cφ = supz∈Y (cid:107)φ(y)(cid:107), δ は l の幾何学と φ による分解に依存するパラメータである。 0.88
𝑖 ), and a part relates to Theorem 7 in Ciliberto et al. i) と Ciliberto et al の Theorem 7 に関係している部分。 0.83
(2020) while the second part relates to Theorem 6 in Cabannes et al. (2020年)、第2部はカバネス等におけるTheorem 6に関するものである。 0.57
(2021). 𝑖 ) together with the stability of the learning algorithm when substituting ( ˆ𝑦𝑖) for (𝑦∗ (2021). i) (y∗) を置換する場合の学習アルゴリズムの安定性とともに 0.80
(cid:13)(cid:13)𝑔∗ + 8𝑐𝜓𝑐𝜑 P𝑋(cid:0)(cid:13)(cid: 13)𝑔∗ (cid:13)(cid:13)g∗ + 8c\cφ PX(cid:0)(cid:13)(ci d:13)g∗ 0.66
between ( ˆ𝑦𝑖) and (𝑦∗ と (y) の間にあります。 0.59
R( 𝑓𝑛) − R( 𝑓 ∗) ≤ 4𝑐𝜓 R(fn) − R(f ∗) ≤ 4c である。 0.88
𝑛 − 𝑔𝑛 𝑛 1If E |𝑋 | < +∞ and E[|𝑋𝑛 − 𝑋 |] → 0, 𝑋𝑛 → 𝑋 in probability. 𝑛 − 𝑔𝑛 𝑛 1 E |X | < +∞ および E[|Xn − X |] → 0 の場合、Xn → X は確率である。 0.88
4 4 0.85
4.1 Classical learnability assumptions In the following, we suppose that the weights 𝛼 are given by nearest neighbors, that X is a compact metric space endowed with a distance 𝑑, that Y is finite and that ℓ is proper in the sense that it strictly positive except on the diagonal of Y × Y diagonal where it is zero. 4.1 古典的学習可能性の仮定 以下では、重み α は近傍から与えられると仮定し、X は距離 d が与えられたコンパクト計量空間であり、Y は有限であり、l はそれがゼロである Y × Y 対角線の対角線を除いて厳密に正であるという意味で適切である。 0.81
We now review classical assumptions to prove consistency. 古典的仮定を見直し、整合性を証明する。 0.47
First, assume that 𝜈X is regular in the following sense. まず、νX が次の意味で正規であると仮定する。 0.69
Assumption 1 (𝜈X well-behaved). 仮定1(νX well-behaved)。 0.68
Assume that 𝜈X is such that there exists ℎ1, 𝑐𝜇, 𝑞 > 0 satisfying, with B designing balls in X , νX が h1, cμ, q > 0 が存在し、B が X 内の球を設計することを仮定する。 0.81
∀ 𝑥 ∈ supp 𝜈X , ∀ 𝑟 < ℎ1, x ∈ supp νX , y r < h1 である。 0.65
𝜈X (B(𝑥, 𝑟)) > 𝑐𝜇𝑟 𝑞. νX (B(x, r)) > cμr q。 0.93
Assumption 1 is useful to make sure that neighbors in D𝑛 are closed with respect to the distance 𝑑, it is usually derived by assuming that X is a subset of R𝑞; that 𝜈X has a density 𝑝 against the Lebesgue measure 𝜆 with minimal mass 𝑝min in the sense that for any 𝑥 ∈ supp 𝜈X , 𝑝(𝑥) > 𝑝min; and that supp 𝜈X has regular boundary in the sense that 𝜆(B(𝑥, 𝑟) ∩ supp 𝜈X) ≥ 𝑐𝜆(B(𝑥, 𝑟) for any 𝑥 ∈ supp 𝜈X and 𝑟 < ℎ (e.g., Audibert and Tsybakov, 2007). 仮定1は、Dn の近傍が距離 d に関して閉であることを確認するのに有用であり、通常、X が Rq の部分集合であると仮定することによって導出される; νX は、任意の x ∈ supp νX , p(x) > pmin に対して、最小質量 pmin のルベーグ測度 λ に対して密度 p を持ち、その supp νX は、任意の x ∈ supp νX および r < h (例えば、Audibert および Tsybakov, 2007) に対して λ(B(x, r) ^ cλ(B(x, r) に対して正規境界を持つ。 0.90
We now switch to a classical assumption in partial labelling, allowing for population disambiguation. 現在では、部分的ラベル付けの古典的な仮定に切り替え、人口の曖昧さを解消します。 0.48
Assumption 2 (Non ambiguity, Cour et al. 仮定2(非曖昧性、Cour et al)。 0.69
(2011)). Assume the existence of 𝜂 ∈ [0, 1), such that for any 𝑥 ∈ supp 𝜈X , there exists 𝑦𝑥 ∈ Y, such that P𝜈 (𝑦𝑥 ∈ 𝑆 | 𝑋 = 𝑥) = 1, and ∀ 𝑧 ≠ 𝑦𝑥, P𝜈 (𝑧 ∈ 𝑆 | 𝑋 = 𝑥) ≤ 𝜂. (2011)). η ∈ [0, 1) の存在を仮定し、任意の x ∈ supp νx に対して、pν (yx ∈ s | x = x) = 1 で かつ z 次 yx, pν (z ∈ s | x = x) ≤ η となるような yx ∈ y が存在するとする。 0.88
Assumption 2 states that when given the full distribution 𝜈, there is one, and only one, label that is coherent with every observable sets for a given input. 仮定 2 は、完全分布 ν が与えられたとき、与えられた入力に対するすべての可観測集合と一貫性のあるラベルが 1 つだけ存在することを述べる。 0.76
It is a classical assumption in literature about the learnability of the partial labelling problem (e.g., Liu and Dietterich, 2014). これは部分的ラベル問題(例えば、liu and dietterich, 2014)の学習可能性に関する文学における古典的な仮定である。 0.69
When ℓ is proper, this implies that 𝜇∗|𝑥 = 𝛿𝑦𝑥, and 𝑓 ∗(𝑥) = 𝑦𝑥. l が真のとき、これは μ∗|x = δyx、f ∗(x) = yx を意味する。 0.84
Finally, we assume that 𝑔∗ is regular. 最後に、g は正則であると仮定する。 0.54
As we are considering local averaging method, we will use Lipschitz- 局所平均化法を検討中であるので,lipschitz- 0.65
continuity, which is classical in such a setting.2 Assumption 3 (Regularity of 𝑔∗). 連続性(continuity)は、そのような設定で古典的である。 0.54
Assume that there exists 𝑐𝑔 > 0, such that for any 𝑥, 𝑥(cid:48) ∈ X , we have cg > 0 が存在し、任意の x に対して x(cid:48) ∈ x が成り立つと仮定する。 0.78
(cid:107)𝑔∗(𝑥) − 𝑔∗(𝑥(cid:48))(cid:107)H ≤ 𝑐𝑔𝑑(𝑥, 𝑥(cid:48)). (cid:107)g∗(x) − g∗(x(cid:48))(cid:107) H ≤ cgd(x, x(cid:48))。 0.92
It should be noted that regularity of 𝑔∗, Assumption 3, together with determinism of 𝜇∗|𝑥 inherited from Assumption 2 implies that classes X𝑦 = {𝑥 | 𝑓 ∗(𝑥) = 𝑦} are separated in X , in the sense that there exists ℎ2 > 0, such that for any 𝑦, 𝑦(cid:48) ∈ Y and (𝑥, 𝑥(cid:48)) ∈ X𝑦 × X𝑦(cid:48), 𝑑(𝑥, 𝑥(cid:48)) > ℎ2, which is a classical assumption to derive consistency of semi-supervised learning algorithm (e.g., Rigollet, 2007). g , Assumption 3 の正則性、および Assumption 2 から継承された μ*|x の決定性は、クラス Xy = {x | f (x) = y} が X で分離されていること、すなわち任意の y, y(cid:48) ∈ Y および (x, x(cid:48)) ∈ Xy × Xy(cid:48), d(x, x(cid:48)) > h2 が存在し、これは半教師学習アルゴリズム(例えば Rigollet, 2007) の一貫性を導出するための古典的な仮定である。 0.84
We detailed those implications in Appendix A.2. それらの影響をAppendix A.2で詳述した。 0.49
4.2 Exponential convergence rates We are now ready to state our convergence result. 4.2 指数収束率 収束結果を宣言する準備が整いました。 0.66
We introduce ℎ = min(ℎ1, ℎ2) and 𝑝 = 𝑐𝜇 ℎ𝑞, so that for any 𝑥 ∈ supp 𝜈X , 𝜈X (B(𝑥, ℎ)) > 𝑝. Theorem 4 (Exponential convergence rates). h = min(h1, h2) と p = cμ hq を導入し、任意の x ∈ supp νX , νX (B(x, h)) > p. Theorem 4 (Exponential convergence rate) について述べる。 0.92
When the weights 𝛼 are given by nearest neighbors, under Assumptions 1, 2 and 3, the excess of risk in Eq. 重み α が隣人によって与えられるとき、仮定 1, 2 および 3 の下では、Eq のリスクは過大である。 0.75
(6) is bounded by E( 𝑓𝑛) ≤ 8𝑐𝜓𝑐𝜑(𝑛 + 1) exp (6)は束縛される E( fn) ≤ 8c\cφ(n + 1) exp 0.86
(cid:17) (cid:16)− 𝑛𝑝 (cid:17) (cid:16)-np 0.81
16 (11) as soon as 𝑘 < 𝑛𝑝/4, with 𝑚 = #Y. 16 (11) k < np/4 であればすぐに m = #y となる。 0.86
By taking 𝑘𝑛 = 𝑘0𝑛, for 𝑘0 < 𝑝/4, this implies exponential convergence rates E( 𝑓𝑛) = 𝑂(𝑛 exp(−𝑛)). kn = k0n を k0 < p/4 とすると、指数収束速度 E( fn) = O(n exp(−n)) となる。 0.84
+ 8𝑐𝜓𝑐𝜑𝑚 exp (−𝑘 |log(𝜂)|) , + 8cψcφm exp (−k |log(η)|) , 0.76
2Its generalization through Hölder-continuity would work too. 2Hölder-continuityによる一般化も機能する。 0.62
5 5 0.85
Sketch for Theorem 4. Sketch for Theorem 4 (英語) 0.74
In essence, based on Lemma 3, Theorem 4 can be understood as two folds. 本質的に、補題 3 に基づいて定理 4 は2つの折りたたみとして解釈できる。 0.65
𝑛 and 𝑔∗. This error can be controlled in exp(−𝑛𝑝) as the non-ambiguity • A fully supervised error between 𝑔∗ assumption implies a hard Tsybakov margin condition, a setting in which the fully supervised estimate 𝑔∗ is known to converge to the population solution 𝑔∗ with such rates (Cabannes et al., 2021). n と g です。 この誤差はexp(−np) において非曖昧性として制御できる • g∗ の仮定の間の完全教師付き誤差は、厳密な Tsybakov margin 条件を意味し、完全に教師付き推定 g∗ がそのような速度で集団解 g∗ に収束することが知られている(Cabannes et al., 2021)。 0.73
• A weakly disambiguation error, that is exponential too, since, based on Assumption 2, disambiguating between 𝑧 ∈ Y and 𝑦𝑥 from 𝑘 sets 𝑆 sampled accordingly to 𝜈|𝑥 can be done in 𝜂𝑘, and disambiguating between all 𝑧 ≠ 𝑦𝑥 and 𝑦𝑥 in 𝑚𝜂𝑘 = 𝑚 exp(−𝑘 |log(𝜂)|). なぜなら、仮定 2 に基づいて ν|x に従ってサンプリングされた k 集合 S からの z ∈ Y と yx の間の曖昧化は ηk で行うことができ、また mηk = m exp(−k |log(η)| におけるすべての z yx と yx の間の曖昧化は ηk で行うことができるからである。 0.66
𝑛 Appendix A.3 provides details. 𝑛 Appendix A.3は詳細を提供する。 0.71
(cid:3) Theorem 4 states that under a non-ambiguity assumption and a regularity assumption implying no-density separation, one can expect exponential convergence rates of 𝑓𝑛 learned with weakly supervised data to 𝑓 ∗ the solution of the fully supervised learning problem, measured with excess of fully supervised risk. (cid:3) 定理4は、非曖昧性仮定と非密度分離を意味する正則性仮定の下では、弱教師付きデータで学習した fn の指数収束率を期待でき、完全に教師付きされた学習問題の解を f ∗ にすることができる。 0.69
Because of exponential convergence rates, we could expect polynomial convergence rates for a broader class of problems that are approximated by problems satisfying assumptions of Theorem 4. 指数収束率のために、定理4の仮定を満たす問題によって近似されるより広いクラスの問題の多項式収束率が期待できる。 0.77
The derived rates in 𝑛 exp(−𝑛) should be compared with rates in 𝑛−1/2 and 𝑛−1/4, respectively derived, under the same assumptions, by Cour et al. n exp(−n) の導出率は、Cour らによってそれぞれ n-1/2 と n−1/4 の導出率と比較されるべきである。 0.69
(2011); Cabannes et al. (2011年)、カバネスら。 0.46
(2020). 5 Optimizaton Considerations In this section, we focus on implementations to solve Eq. (2020). 5 Optimizaton Considerations このセクションでは、Eqを解決する実装に焦点を当てます。 0.81
(4). We explain why disambiguation objectives, such as Eq. (4). Eqのような曖昧な目的がなぜあるのかを説明します。 0.66
(2) are intrinsically non-convex and express a heuristic strategy to solve Eq. (2)は本質的に非凸であり、Eqを解決するためのヒューリスティック戦略を表す。 0.64
(4) besides non-convexity in classical well-behaved instances of partial labelling. (4) 古典的有望な部分ラベリングの例における非凸性に加えて。 0.59
Note that we do not study implementations to solve Eq. 注意すべき点は、Eq を解くための実装を研究しないことである。 0.40
(5) as this study has already been done by Nowak-Vila et al. (5) この研究は、すでにNowak-Vilaらによって行われました。 0.77
(2019). We end this section by considering a practical example to make derivations more concrete. (2019). この節は、導出をより具体化するための実践的な例を考えることで終了する。 0.68
5.1 Non-convexity of disambiguation objectives For readability, suppose that X is a singleton, justifying to remove the dependency on the input in the following. 5.1 可読性に対する曖昧さの目的の非凸性 x をシングルトンと仮定し、次の入力への依存性を取り除くことを正当化する。 0.69
Consider 𝜈 ∈ Δ2Y a distribution modelling weak supervision. ν ∈ δ2y を弱い監督を伴う分布モデルとする。 0.63
While the domain {𝜇 ∈ ΔY | 𝜇 (cid:96) 𝜈} is convex, a disambiguation objective E : ΔY → R defining 𝜇∗ ∈ arg min𝜇(cid:96)𝜈 E(𝜇), similarly to Eq. 領域 {μ ∈ ΔY | μ (cid:96) ν} が凸であるとき、曖昧な目的 E : ΔY → R が μ∗ ∈ arg minμ(cid:96)ν E(μ) を定義する。 0.84
(2), that is minimized for deterministic distributions, which correspond to 𝜇 a Dirac, i.e., minimized on vertices of its definition domain ΔY, can not be convex. 2)その定義域 δy の頂点上で最小化されたμ a dirac に対応する決定論的分布に対して最小化されるが、凸化できない。 0.82
In other terms, any disambiguation objective that pushes toward distributions where targets are deterministic function of the input, as mentioned in Remark 2, can not be convex. 言い換えれば、Remark 2で述べたように、ターゲットが入力の決定論的関数である分布にプッシュする曖昧な目的は凸であることはできない。 0.79
Indeed, smooth disambiguation objectives such as entropy and our piecewise linear loss-based principle (2), reading pointwise E(𝜇) = inf𝑧∈Y E𝑌∼𝜇[ℓ(𝑧, 𝑌)], are concave. 実際、エントロピーや分断線形損失に基づく原理(2)のような滑らかな曖昧さの目的、すなわち、ポイントワイズ e(μ) = infz ajaxy ey\μ[l(z, y)] は凹凸である。 0.70
Similarly, its quadratic variant E(cid:48)(𝜇) = E𝑌 ,𝑌(cid:48)∼𝜇[ℓ(𝑌 , 𝑌 (cid:48))], is concave as soon as (ℓ(𝑦, 𝑦(cid:48)))𝑦,𝑦(cid:48)∈Y is semi-definite negative. 同様に、その二次多様体 E(cid:48)(μ) = EY , Y(cid:48)\μ[l(Y , Y(cid:48)) は (l(y, y(cid:48)))y,y(cid:4 8)∈Y が半有限負である。 0.87
We illustrate those considerations on a concrete example with graphical illustration in Appendix C. We should see how this translates on generic implementations to solve the empirical objective (4). これらの考察を、付録 C でグラフィカルなイラストで具体的な例で説明します。これは、経験的な目的を解決するための汎用実装にどのように変換されるかを見るべきです(4)。
訳抜け防止モード: 付録cの図式による具体例でこれらの考察を例示します。 これは、経験的目的(4)を解決するためのジェネリック実装に翻訳される。
5.2 Generic implementation for Eq. 5.2 Eqのジェネリック実装。 0.65
(4) Depending on ℓ and on the type of observed set (𝑠𝑖), Eq. (4) lおよび観察されたセット(si)のタイプによって、Eq。 0.78
(4) might be easy to solve. (4)解くのが簡単かもしれない。 0.73
In the following, however, we will introduce optimization considerations to solve it in a generic structured prediction fashion. しかし、以下では、汎用的な構造化予測方式で解くために最適化考慮事項を導入する。 0.75
To do so, we recall the decomposition of ℓ (7) and rewrite Eq. そのために、l(7)の分解を思い出し、Eqを書き換えます。 0.61
(4) as ( ˆ𝑦𝑖)𝑖≤𝑛 ∈ arg min 𝑦𝑖∈𝐶𝑛 (4) i≤n ∈ arg min yi∈Cn 0.70
inf (𝑧𝑖)∈Y 𝑛 inf (zi)∈Y n 0.97
𝛼 𝑗(𝑥𝑖)𝜓(𝑧𝑖)(cid:62)𝜑(𝑦 𝑗). α j(xi)(zi)(cid:62)φ(y j) である。 0.89
𝑛∑︁ 𝑖, 𝑗=1 𝑛∑︁ 𝑖, 𝑗=1 0.69
Since, given (𝑦 𝑗), the objective is linear in 𝜓(𝑧 𝑗), the constraint 𝜓(𝑧 𝑗) ∈ 𝜓(Y) can be relaxed with 𝜁𝑖 ∈ Conv 𝜓(Y).3 Similarly, with respect to 𝜑(𝑦 𝑗), this objective is the infimum of linear functions, therefore is y j が与えられたとき、目的が ψ(z j) で線型となるので、制約 ψ(z j) ∈ ψ(y) は φ(y j) に関しても同様に φ(y j)3 で緩和できるので、この目的は線型函数の無限大である。
訳抜け防止モード: 与えられた (y j ) から、目的は ψ(z j ) において線型である。 制約 ψ(z j ) ∈ ψ(y ) は、同様に i ∈ conv ψ(y).3 で緩和することができる。 φ(y j ) に関して、この目的は線型函数の無限遠である。
3The minimization pushes towards extreme points of the definition domain. 3最小化は定義領域の極端点にプッシュする。 0.79
6 6 0.85
concave, and the constraint 𝜑(𝑦 𝑗) ∈ 𝜑(𝑠 𝑗), could be relaxed with 𝜉𝑖 ∈ Conv 𝜑(𝑠 𝑗). 凹凸、および制約 φ(y j) ∈ φ(s j) は、i ∈ Conv φ(s j) で緩和することができる。 0.81
Hence, with H0 = Conv 𝜓(Y) したがって、H0 = Conv(Y) である。 0.83
and Γ𝑛 = 𝑗 ≤𝑛 Conv 𝜑(𝑠 𝑗), the optimization is cast as j ≤n Conv φ(s j) は、最適化をキャストします。 0.69
𝑛∑︁ since Eq. (5) can be rewritten as 𝑓𝑛(𝑥) ∈ arg min𝑧∈Y 𝜓(𝑧)(cid:62)𝑛 略称はEq。 (5) は fn(x) ∈ arg minz∈Y (z)(cid:62) として書き換えることができる。 0.59
( ˆ𝜉𝑖)𝑖≤𝑛 ∈ arg min (𝜉𝑖)∈Γ𝑛 (i)ihtmln ∈ arg min(i)groovyγn 0.75
(𝜁𝑖)∈H𝑛 0 inf (i)∈Hn 0 inf 0.90
𝑖, 𝑗=1 𝑖=1 𝛼𝑖(𝑥) ˆ𝜉𝑖. 𝑖, 𝑗=1 𝑖=1 𝛼𝑖(𝑥) ˆ𝜉𝑖. 0.86
𝛼 𝑗(𝑥𝑖)𝜁(cid:62) α j(xi) ^ (cid:62) 0.96
𝑖 𝜉 𝑗 . (12) 𝑖 𝜉 𝑗 . (12) 0.85
Because of concavity, ( ˆ𝜉𝑖) will be an extreme point of Γ𝑛, that could be decoded into ˆ𝑦𝑖 = 𝜑−1( ˆ𝜉𝑖). 空洞性のため、(i) は γn の極点となるが、これは syi = φ−1( si) にデコードできる。 0.62
However, it should be noted that if only interested in 𝑓𝑛 and not in the disambiguation ( ˆ𝑦𝑖), this decoding can be avoided, しかし、fnのみに興味を持ち、曖昧さ(syi)を含まない場合、この復号は避けられることに注意する必要がある。 0.69
5.3 Alternative minimization with good initialization To solve Eq. 5.3 よい初期化を用いる代替最小化 Eq を解決するため。 0.64
(12), we suggest to use an alternative minimization scheme. (12) 代替の最小化方式を提案する。 0.67
The output of such an scheme is highly dependent to the variable initialization. そのようなスキームの出力は変数の初期化に大きく依存する。 0.83
In the following, we introduce well-behaved problem, where (𝜉𝑖)𝑖≤𝑛 can be initialized smartly, leading to an efficient implementation to solve Eq. ここでは(i)i≤nをスマートに初期化することができ、Eqを解決するための効率的な実装につながります。 0.75
(12). Definition 5 (Well-behaved partial labelling problem). (12). 定義5(Well-behaved partial labelling problem)。 0.85
A partial labelling problem (ℓ, 𝜈) is said to be wellbehaved if for any 𝑠 ∈ supp 𝜈2Y , there exists a signed measure 𝜇𝑠 on Y such that the function from Y to R defined 部分ラベル問題 (l, ν) が wellbehaved であるとは、任意の s ∈ supp ν2y に対して、y から r への函数が定義される y 上の符号付き測度 μs が存在することを言う。 0.70
Y ℓ(𝑧, 𝑦) d𝜇𝑠(𝑦) is minimized for, and only for, 𝑧 ∈ 𝑠. Y l(z, y) dμs(y) は z ∈ s に対してのみ最小化される。 0.88
as 𝑧 →∫ 𝑖 z → として。 𝑖 0.67
We provide a real-world example of a well-behaved problem in Section 5.4 as well as a synthetic example with graphical illustration in Appendix C. On those problems, we suggest to solve Eq. 私たちは、第5.4節でうまく行動した問題の実世界の例と、付録Cでグラフィカルなイラストの合成例を提供します。
訳抜け防止モード: われわれは第5章4節でうまく振る舞う問題の実例と、Appendix C のグラフィカルイラストレーションによる合成例を提示している。 我々はEqを解くことを提案する。
(12) by considering the initialization 𝜉(0) = E𝑌∼𝜇𝑠𝑖 [𝜑(𝑌)], and performing alternative minimization of Eq. (12) 初期化 ey(0) = ey μsi [ φ(y)] を考慮し、eq の代替最小化を行う。 0.78
(12), until attaining 𝜉(∞) as the limit of the alternative minimization scheme (which exists since each step decreases the value of the objective in Eq. (12) 代替最小化スキーム(各ステップが Eq の目標の値を下げるので存在する)の限界として φ(∞) に達するまで。 0.79
(12) and there is a finite number of candidates for (𝜉𝑖)). (12) かつ (i) の候補は有限である。 0.54
It corresponds to a disambiguation guess ˜𝑦𝑖 = 𝜑−1(𝜉(∞) ). これは、曖昧さの推測 :yi = φ−1(\(∞) ) に対応する。 0.65
Then we suggest to learn ˆ𝑓𝑛 from (𝑥𝑖, ˜𝑦𝑖) based on Eq. 次に, eq に基づいて (xi, syi) から sfn を学ぶことを提案する。 0.68
(5), and existing algorithmic tools for this problem (Nowak-Vila et al., 2019). (5)、およびこの問題のための既存のアルゴリズムツール(Nowak-Vila et al., 2019)。 0.84
To assert the well-groundedness of this heuristic, we refer to the following proposition, proven in Appendix A.4. このヒューリスティックの十分根拠を主張するために、付録A.4で証明された次の提案を参照する。
訳抜け防止モード: このヒューリスティックの善良さを主張する Appendix A.4 で証明された以下の命題を参照する。
Proposition 6. Under the non-ambiguity hypothesis, Assumption 2, the solution of Eq. 命題6。 非曖昧性仮説の下で、仮定2はEqの解である。 0.62
(3) is characterized by 𝑛 : X → H defined as 𝑛 defined through (3) は n : X → H が n として定義されることを特徴とする。 0.74
𝑓 ∗ ∈ arg min 𝑓 :X→Y E( 𝑋,𝑆)∼𝜈(cid:2)E𝑌∼𝜇𝑆 [ℓ( 𝑓 (𝑋), 𝑌)](cid:3) . f(X) ∈ arg min f :X→Y E(X,S) ν(cid:2)EY μS [l(f(X),Y)](cid:3) 。 0.87
Moreover, if the surrogate function 𝑔◦ 𝑛(𝑥) =𝑛 さらに、もしサーロゲート函数 g が n(x) =*n ならば 0.67
𝑖=1 𝛼𝑖(𝑥)𝜉𝑠𝑖, with 𝜉𝑠 = E𝑌∼𝜇𝑠[𝜑(𝑌)], converges towards 𝑔◦(𝑥) = E𝑆∼𝜈|𝑥 [𝜉𝑆] in 𝐿1, 𝑓 ◦ i=1 αi(x)-si で、ys = EY\μs[φ(Y)] で、L1 において g (x) = ES\ν|x [\S] へ収束する。 0.72
𝑔◦ the decoding Eq. g は Eq を復号する。 0.67
(9) converges in risk towards 𝑓 ∗. (9) は f に対して危険に収束する。 0.72
𝑖 𝑖 𝑖 𝑖 𝑖 Given that our algorithm scheme is initialized for 𝜉(0) 𝑖 𝑖 𝑖 𝑖 𝑖 アルゴリズムのスキームが s(0) に対して初期化されることを考える。 0.81
= 𝜉𝑠𝑖 and 𝜁 (0) 𝑛 (𝑥𝑖) and stopped once having 𝑛 , which given consistency result exposed in =イシ、イシ(0) n (xi) で停止し、n を持つと、一貫性が露呈する。 0.65
and 𝜁 (∞) ∞ (複数形 ∞s) 0.68
= ˆ𝑓𝑛(𝑥𝑖), = ˆ𝑓𝑛(𝑥𝑖), 0.73
ˆ𝑓𝑛 is arguably better than 𝑓 ◦ fn は f より間違いなく良い。 0.77
attained 𝜉(∞) Proposition 6, is already good enough. 成就した(∞)命題6は既に十分である。 0.71
Remark 7 (IQP implementation for Eq. Remark 7 (IQP implementation for Eq)。 0.88
(4)). Other heuristics to solve Eq. (4)). Eqを解くための他のヒューリスティックス。 0.75
(4) are conceivable. (4)が考えられる。 0.77
For example, considering 𝑧𝑖 = 𝑦𝑖 in this equation, we remark that the resulting problem is isomorphic to an integer quadratic program (IQP). 例えば、この方程式において zi = yi を考えると、結果として生じる問題は整数二次プログラム(IQP)に同型である。 0.72
Similarly to integer linear programming, this problem can be approached with relaxation of the “integer constraint” to get a real-valued solution, before “thresholding” it to recover an integer solution. 整数線形プログラミングと同様に、この問題は「整数制約」を緩和して実値の解を得るか、整数解を「保持」する前にアプローチすることができる。 0.65
This heuristic can be seen as a generalization of the Diffrac algorithm (Bach and Harchaoui, 2007; Joulin et al., 2010). このヒューリスティックはディフフラアルゴリズムの一般化と見なすことができる(Bach and Harchaoui, 2007; Joulin et al., 2010)。 0.71
we present it in details in Appendix B. 詳細はAppendix Bで発表します。 0.63
Remark 8 (Link with EM, (Dempster et al., 1977)). Remark 8 (Link with EM, (Dempster et al., 1977)。 0.74
Arguably, our alternative minimization scheme, optimizing respectively the targets 𝜉𝑖 = 𝜑(𝑦𝑖) and the function estimates 𝜁𝑖 = 𝜓( 𝑓𝑛(𝑥𝑖)) can be seen as the non-parametric version of the Expectation-Maximiza tion algorithm, popular for parametric model (Dempster et al., 1977). おそらく、我々の代替の最小化スキームは、それぞれ目標 si = φ(yi) と関数推定 si = ψ(fn(xi)) を最適化し、パラメトリックモデルによく使われる期待最大化アルゴリズムの非パラメトリックバージョンと見なすことができる(dempster et al., 1977)。 0.87
= 𝑓 ◦ 5.4 Application: Ranking with partial ordering Ranking is a problem consisting, for an input 𝑥 in an input space X , to learn a total ordering 𝑦, belonging to Y = S𝑚, modelling preference over 𝑚 items. = 𝑓 ◦ 5.4 適用: 部分順序付けのランク付けは、入力空間 X の入力 x に対して、Y = Sm に属する総順序付け y を学習し、m 項目に対する優先度をモデル化する問題である。 0.82
It is usually approach with the Kendall loss ℓ(𝑦, 𝑧) = −𝜑(𝑦)(cid:62)𝜑(𝑧), 通常、これはケンドール損失 l(y, z) = −φ(y)(cid:62)φ(z) でアプローチされる。 0.79
7 7 0.85
with 𝜑(𝑦) = (sign (𝑦(𝑖) − 𝑦( 𝑗)))𝑖, 𝑗 ≤𝑚 ∈ {−1, 1}𝑚2 (Kendall, 1938). φ(y) = (sign (y(i) − y(j)))i, j ≤m ∈ {−1, 1}m2 (Kendall, 1938) である。 0.91
Full supervision corresponds, for a given 𝑥, to be given a total ordering of the 𝑚 items. 完全な監督は、与えられた x に対して、m 個の項目の総順序を与えられる。
訳抜け防止モード: 与えられた x に対して、完全な監督は対応する m項目の合計順序を付与する。
This is usually not an option, but one could expect to be given partial ordering that 𝑦 should follow (Cao et al., 2007; Hüllermeier et al., 2008; Korba et al., 2018). これは通常オプションではありませんが、yが従うべき部分的な順序付けが与えられる可能性があります(Cao et al., 2007; Hüllermeier et al., 2008; Korba et al., 2018)。 0.84
Formally, this equates to the observation of some, but not all, coordinates 𝜑(𝑦)𝑖 of the vector 𝜑(𝑦) for some 𝑖 ∈ 𝐼 ⊂ (cid:200)1, 𝑚(cid:201)2. 形式的には、これはいくつかの i ∈ I (cid:200)1, m(cid:201)2 に対するベクトル φ(y) の φ(y)i の観測に等しいが、すべてではない。 0.86
In this setting, 𝑠 ⊂ Y is a set of total orderings that match the given partial ordering. この設定では、s = Y は与えられた部分順序に一致する全順序の集合である。 0.71
It can be represented by a vector 𝜉𝑠 ∈ H, that satisfies the partial ordering observation, (𝜉𝑠)𝐼 = 𝜑(𝑦)𝐼, and that is agnostic on unobserved coordinates, (𝜉𝑠)𝑐 𝐼 = 0. 部分順序付け観測(英語版)(s)i = φ(y)i を満たすベクトル s ∈ h で表され、観測されていない座標(英語版)、 (s)c i = 0 上では不可知である。
訳抜け防止モード: これは、部分順序観測を満たすベクトル s ∈ H で表すことができる。 (s)I = φ(y)I で、これは観測されていない座標に非依存である。 ( 𝜉𝑠)𝑐 𝐼 = 0 .
This vector satisfies that 𝑧 → 𝜓(𝑧)(cid:62)𝜉𝑠 is minimized for, and only for, 𝑧 ∈ 𝑠. このベクトルは z → ψ(z)(cid:62) s が z ∈ s に対してのみ最小化されることを満たす。 0.87
Hence, it constitutes a good initialization for the alternative minimization scheme detailed above. したがって、上述の代替最小化スキームのよい初期化を構成する。 0.79
We provide details in Appendix A.5, where we also show that 𝜉𝑠 can be formally translated in a 𝜇𝑠 to match the Definition 5, proving that ranking with partial labelling is a well-behaved problem. 我々は Appendix A.5 に詳細を述べるが、ここでは定義 5 に一致するような μs で正式に変換できることも示し、部分ラベリングによるランク付けが良い問題であることを証明している。 0.70
Many real world problems can be formalized as a ranking problem with partial ordering observations. 多くの現実世界の問題は、部分順序観察によるランキング問題として形式化することができる。 0.58
For example, 𝑥 could be a social network user, and the 𝑚 items could be posts of her connection that the network would like to order on her feed accordingly to her preferences. 例えば、xはソーシャルネットワークのユーザーになり得るし、m項目は、ネットワークが彼女の好みに応じてフィードを注文したいという彼女のコネクションの投稿かもしれない。 0.75
One might be told that the user 𝑥 prefer posts from her close rather than from her distant connections, which translates formally as the constraint that for any 𝑖 corresponding to a post of a close connection and 𝑗 corresponding to a post of a distant connection, we have 𝜑(𝑦)𝑖 𝑗 = 1. ユーザ x は、彼女の遠い接続からではなく、彼女の近い接続からのポストを好むと伝えられるが、これは正式には、閉じた接続のポストに対応する任意の i と、遠い接続のポストに対応する j に対して、φ(y)i j = 1 を持つという制約として解釈される。 0.71
Nonetheless, designing non-parametric structured prediction models that scale well when the intrinsic dimension 𝑚 of the space Y is very large (such as the number of post on a social network) remains an open problem, that this paper does not tackle. それにもかかわらず、空間 Y の本質的な次元 m が非常に大きい(ソーシャルネットワーク上のポスト数など)ときによくスケールする非パラメトリック構造化予測モデルの設計は、この論文が取り組まないオープンな問題のままである。 0.86
6 Related work Weakly supervised learning has been approached through parametric and non-parametric methods. 6 パラメトリックおよび非パラメトリック手法を用いて、弱教師付き学習にアプローチした。 0.68
Parametric models are usually optimized through maximum likelihood (Heitjan and Rubin, 1991; Jin and Ghahramani, 2002). パラメトリックモデルは、通常極大確率で最適化される(Heitjan and Rubin, 1991; Jin and Ghahramani, 2002)。 0.91
Hüllermeier (2014) show that this approach, as formalized by Denoeux (2013), equates to disambiguating sets by averaging candidates, which was shown inconsistent by Cabannes et al. Hüllermeier (2014) は、この方法がデノー (2013) によって定式化されたように、平均的候補による集合の曖昧さに等しいことを示した。 0.78
(2020) when data are not missing at random. (2020) データがランダムに欠落していない場合。 0.80
Among non-parametric models, Xu et al. 非パラメトリックモデルのうち、xu など。 0.67
(2004); Bach and Harchaoui (2007) developed an algorithm for clustering, that has been cast for weakly supervised learning problem (Joulin et al., 2010), leading to a disambiguation algorithm similar than ours, yet without consistency results. 2004年) bach and harchaoui (2007年) は、弱い教師付き学習問題(joulin et al., 2010年)のためにキャストされたクラスタリングのためのアルゴリズムを開発した。
訳抜け防止モード: (2004 ) ; Bach と Harchaoui (2007 ) はクラスタリングのためのアルゴリズムを開発した。 弱教師付き学習問題(Joulin et al , 2010)で採用されている。 あいまいなアルゴリズムが我々のものと似ていますが 一貫性はありませんでした
More recently, half-way between theory and practice, Gong et al. 最近では、Gongらの理論と実践の中間にある。 0.73
(2018) derived an algorithm geared towards classification, based on a disambiguation objective, incorporating several heuristics, such as class separation, and Laplacian diffusion. (2018)は、クラス分離やラプラシアン拡散といったいくつかのヒューリスティックを組み込んだ曖昧さの目標に基づいた分類のためのアルゴリズムを導出した。 0.60
Those heuristics could be incorporated formally in our model. これらのヒューリスティックは、私たちのモデルに正式に組み込むことができます。 0.45
The infimum loss principle has been considered by several authors, among them Cour et al. infimum Lossの原則は、Cour et alを含む数人の著者によって検討されている。 0.52
(2011); Luo and Orabona (2010); Hüllermeier (2014). (2011年)、Luo and Orabona (2010年)、Hüllermeier (2014年)。 0.67
It was recently analyzed through the prism of structured prediction by Cabannes et al. 最近、cabannesらによって構造化予測のプリズムを通して分析された。 0.67
(2020), leading to a consistent non-parametric algorithm that will constitute the baseline of our experimental comparison. (2020)、私たちの実験比較のベースラインを構成する一貫した非パラメトリックアルゴリズムにつながります。 0.84
This principle is interesting as it does not assume knowledge on the corruption process (𝑆|𝑌) contrarily to the work of Cid-Sueiro et al. この原理は、Cid-Sueiroらの仕事とは対照的に腐敗プロセス(S|Y)に関する知識を前提としていないので興味深い。 0.61
(2014) or van Rooyen and Williamson (2017). 2014年) または van Rooyen and Williamson (2017)。 0.81
The non-ambiguity assumption has been introduced by Cour et al. 非曖昧性の仮定はcourらによって導入された。 0.37
(2011) and is a classical assumption of learning with partial labelling (Liu and Dietterich, 2014). (2011)であり、部分ラベリングによる学習の古典的な仮定である(Liu and Dietterich, 2014)。 0.75
Assumptions of Lipschitzness and minimal mass are classical assumptions to prove convergence of local averaging method (Audibert and Tsybakov, 2007; Biau and Devroye, 2015). リプシッツ性の仮定と最小質量は局所平均化法の収束を証明する古典的な仮定である(Audibert and Tsybakov, 2007; Biau and Devroye, 2015)。 0.81
Those assumptions imply class separation in X , which has been leverage in semi-supervised learning, justifying Laplacian regularization (Rigollet, 2007; Zhu et al., 2003). これらの仮定は、ラプラシア正規化(Rigollet, 2007; Zhu et al., 2003)を正当化する、半教師付き学習に活用されているXのクラス分離を意味する。 0.63
Note that those assumptions might not hold on raw representation of the data, but with appropriate metrics, which could be learned through unsupervised Duda et al. これらの仮定はデータの生の表現ではなく、教師なしの Duda などを通じて学習できる適切なメトリクスで成り立っている。 0.52
(2000) or self-supervised learning Doersch and Zisserman (2017). (2000) or self-supervised learning doersch and zisserman (2017)。 0.92
As such, the practitioner might consider weights 𝛼 given by similarity metrics derived through such techniques, before computing the disambiguation (4) and learning 𝑓𝑛 from the recollected fully supervised dataset with deep learning. このような手法により得られた類似度測定値から得られる重みαを、曖昧さ(4)を計算し、深層学習を用いて再構成された完全教師付きデータセットからfnを学習する前に考えることができる。 0.66
7 Experiments In this section, we review a baseline, and experiments that showcase the usefulness of our algorithm Eqs. 7 実験 この節では,アルゴリズムEqsの有用性を示す基礎と実験について概説する。
訳抜け防止モード: 7 実験 このセクションでは、ベースラインをレビューします。 そして私達のアルゴリズムEqsの有用性を示す実験。
(4) and (5). (4)と(5)である。 0.72
8 8 0.85
Baseline. We consider as a baseline the work of Cabannes et al. ベースライン。 私達はCabannesらの仕事の基礎ラインとして考慮します。 0.65
(2020), which is a consistent structured prediction approach to partial labelling through the infimum loss. (2020) は, 無限損失による部分ラベリングに対する一貫した構造的予測手法である。 0.77
It is arguably the state-of-the-art of partial labelling approached through structured prediction. これは、構造化予測によってアプローチされる部分的ラベリングの最先端であることは間違いない。 0.41
It follow the same loss-based variance disambiguation principle, yet in an implicit fashion, leading to the inference algorithm, 𝑓𝑛 : X → Y, これは損失に基づく分散の曖昧さの原理と同じだが、暗黙の方法で推論アルゴリズム fn : X → Y に導かれる。 0.78
𝑛∑︁ 𝑖=1 𝑓𝑛(𝑥) ∈ arg min 𝑧∈Y 𝑛∑︁ 𝑖=1 fn(x) ∈ arg min z∈Y 0.71
inf (𝑦𝑖)∈𝐶𝑛 inf (yi)∈Cn 0.99
𝛼𝑖(𝑥)ℓ(𝑧, 𝑦𝑖). 𝛼𝑖(𝑥)ℓ(𝑧, 𝑦𝑖). 0.85
(13) Statistically, exponential convergence rates similar to Theorem 4 could be derived. (13) 統計的には、指数収束率は Theorem 4 と類似している。 0.79
Yet, as we will see, our algorithm outperforms this state-of-the-art baseline. しかし、私たちのアルゴリズムは、この最先端のベースラインを上回っています。 0.54
Disambiguation coherence - Interval regression. 曖昧さコヒーレンス - インターバル回帰。 0.65
The baseline Eq. ベースラインはEq。 0.64
(13) implicitly requires to disambiguate ( ˆ𝑦𝑖(𝑥)) differently for every 𝑥 ∈ X . (13) は暗黙的にすべての x ∈ X に対して異なるあいまいさ(yi(x))を必要とする。 0.72
This is counter intuitive since (𝑦∗ 𝑖 ) does not depend on 𝑥. y∗ i ) は x に依存しないため、これは逆直観的である。 0.68
It means that ( ˆ𝑦𝑖) could equal to some ( ˆ𝑦(0) ) on a subset X0 of X , and to another ( ˆ𝑦(1) ) on a disjoint subset X1 ⊂ X , leading to irregularity of 𝑓𝑛 between X0 and X1. X の部分集合 X0 上のある ( sy(0) ) と、X0 と X1 の間の fn の不規則性につながる不整合な部分集合 X1 の別の ( sy(1) ) と等しくなることを意味する。 0.80
We illustrate this graphically on Figure 1. これを図1で図示します。 0.66
This figure showcases an interval regression problem, which corresponds to the regression setup (Y = R, ℓ(𝑦, 𝑧) = |𝑦 − 𝑧|2) of partial labelling, where one does not observed 𝑦 ∈ R but an interval 𝑠 ⊂ R containing 𝑦. この図は区間回帰問題を示しており、y ∈ r ではなく y を含む区間 s 次 r である部分的ラベリングの回帰設定 (y = r, l(y, z) = |y − z|2) に対応する。
訳抜け防止モード: この図は、部分ラベリングの回帰セットアップ(Y = R, l(y, z ) = |y − z|2 )に対応する区間回帰問題を示す。 ここでは y ∈ R を観測せず、y を含む区間 s = R を観測する。
Among others this problem appears in physics (Sheppard, 1897) and economy (Tobin, 1958). この問題は、物理学 (sheppard, 1897) や経済 (tobin, 1958) にも現れている。 0.85
𝑖 𝑖 Figure 1: Interval regression. 𝑖 𝑖 図1:インターバル回帰。 0.76
See Appendix D for the exact reproducible experimental setup (Left) Setup. 正確な再現可能な実験セットアップ(左)の設定については、 appendix d を参照してください。 0.57
The goal is to learn 𝑓 ∗ : X → R represented by the dashed line, given samples (𝑥𝑖, 𝑠𝑖), where (𝑠𝑖) are intervals represented by the blue segments. 目的は、 (xi, si) が青いセグメントで表される区間であるサンプル (xi, si) を与えられた、破線で表される f ∗ : X → R を学ぶことである。 0.82
(Right) We compare the Infimum Loss (IL) baseline (13) shown in green, with our Disambiguation Framework (DF), Eqs. (右) 緑で示される Infimum Loss (IL) ベースライン (13) と,Disambiguation Framework (DF), Eqs を比較した。
訳抜け防止モード: (右)緑色のInfimum Loss(IL)ベースライン(13)を比較します。 の私達のDisambiguationフレームワーク(DF)、Eqsを使って。
(4) and (5), shown in orange; with weights 𝛼 given by kernel ridge regression. (4)および(5)はオレンジ色で示され、重量αはカーネルリッジ回帰によって与えられる。 0.79
(DF) retrieves ˆ𝑦𝑖 before learning a smooth 𝑓𝑛 based on (𝑥𝑖, ˆ𝑦𝑖), while (IL) implicitly retrieves ˆ𝑦𝑖(𝑥) differently for each input, leading to irregularity of the consequent estimator of 𝑓 ∗. (DF) は (xi, syi) に基づいて滑らかな fn を学習する前に、(IL) は各入力に対して暗黙的に syi(x) を異なる方法で取得し、f の帰結的な推定子の不規則性をもたらす。 0.66
Computation attractiveness - Ranking. 計算の魅力 - ランキング。 0.65
Computationally, the baseline requires to solve a disambiguation problem, recovering ( ˆ𝑦𝑖(𝑥)) ∈ 𝐶𝑛 for every 𝑥 ∈ X for which we want to infer 𝑓𝑛(𝑥). 計算上、ベースラインは、 fn(x) を推論したいすべての x ∈ X に対して ( yi(x)) ∈ Cn を回復する、曖昧な問題を解く必要がある。 0.76
This is much more costly, than doing the disambiguation of ( ˆ𝑦𝑖) ∈ 𝐶𝑛 once, and solving the supervised learning inference problem Eq. これは、一度(yyi) ∈ Cn の曖昧化を行い、教師付き学習推論問題 Eq を解くよりもはるかにコストがかかる。 0.73
(5), for every 𝑥 ∈ X for which we want to infer 𝑓𝑛(𝑥). (5)、fn(x) を推論したいすべての x ∈ X に対して。 0.72
To illustrate the computation attractiveness of our algorithm, consider the case of ranking, defined in Section 5.4. 本稿では,アルゴリズムの計算魅力を説明するために,第5.4節で定義されたランキングの事例について考察する。
訳抜け防止モード: アルゴリズムの計算魅力を説明する。 第5.4節で定義されたランキングの場合を考える。
Fully supervised inference scheme (5) corresponds to solving a NP-hard problem, equivalent to the minimum feedback arcset problem (Duchi et al., 2010). 完全教師付き推論スキーム (5) は最小フィードバックアークセット問題(duchi et al., 2010)に相当するnp-ハード問題を解くことに対応する。 0.75
While disambiguation approaches with alternative minimization implied by Eq. 曖昧さの解消は eq が含意する代替最小化に近づいた。 0.54
(4) and Eq. (13) require to solve this NP-hard problem for each minimization step. (4)およびEq。 (13) 各最小化ステップのnp-hard問題を解く必要がある。 0.76
In other terms, the baseline ask to solve multiple NP-hard problem every time one wants to infer 𝑓𝑛 given by Eq. 言い換えれば、ベースラインは Eq が fn を推論するたびに複数の NP-ハード問題を解くことを要求する。 0.74
(13) on an input 𝑥 ∈ X . (13) 入力 x ∈ X である。 0.76
Meanwhile, our disambiguation approach asks to solve multiple NP-hard problem upfront to solve Eq. 一方、私たちの曖昧化アプローチは、複数のNPハード問題を事前に解決してEqを解決するように求めます。 0.49
(4), yet only require to solve one NP-hard problem to infer 𝑓𝑛 given by Eq. (4)、しかし、Eq によって与えられる fn を推論するために1つの NP ハード問題を解くだけである。
訳抜け防止モード: (4)ただし必要なだけ Eq によって与えられる fn を推論する 1 つの NP - 問題を解く。
(5) on an input 𝑥 ∈ X . (5) を入力 x ∈ X で表す。 0.82
Better empirical results - Classification. より良い実験結果 - 分類。 0.78
Finally, we compare our algorithm, our baseline (13) and the baseline considered by Cabannes et al. 最後に,本アルゴリズム,ベースライン (13) およびベースラインをcabannesらによって検討した。 0.66
(2020) on real datasets from the LIBSVM dataset (Chang and Lin, 2011). (2020) は LIBSVM データセット (Chang and Lin, 2011) の実際のデータセットである。 0.87
Those datasets (𝑥𝑖, 𝑦𝑖) correspond to fully supervised classification problem. これらのデータセット(xi, yi)は、完全に教師付き分類問題に対応する。 0.52
In this setup, Y = (cid:200)1, 𝑚(cid:201) for 𝑚 a number of classes, and ℓ(𝑦, 𝑧) = 1𝑦≠𝑧. この設定では、 m に対して Y = (cid:200)1, m(cid:201) と l(y, z) = 1y\z が成り立つ。
訳抜け防止モード: このセットアップでは、 Y = ( cid:200)1, m(cid:201 ) for m a number of class, and ℓ(𝑦 , 𝑧 ) = 1𝑦≠𝑧.
We “corrupt” labels in order to create a synthetic weak supervision datasets (𝑥𝑖, 𝑠𝑖). 合成的な弱い監督データセット(xi, si)を作成するためにラベルを“分解”します。 0.67
9 xyProblemsettingSign alSamplesxyReconstru ctionDFIL 9 xyProblemsettingSign alSamplesxyReconstru ctionDFIL 0.47
We consider skewed corruption, in the sense that (𝑠𝑖) is generated by a probability such that𝑧∈Y P𝑆𝑖(𝑧 ∈ 𝑆𝑖|𝑦𝑖) すなわち、(si) は、z∈Y PSi(z ∈ Si|yi) のような確率によって生成される。 0.71
depends on the value of 𝑦𝑖. yiの値によって異なります。 0.81
This corruption is parametrized by a parameter that related with the ambiguity parameter 𝜂 of Assumption 2. この腐敗は、仮定 2 の曖昧性パラメータ η に関連するパラメータによってパラメトリ化される。 0.80
Results on Figure 2 show that, in addition to having a lower computation cost, our algorithm performs better in practice than the state-of-the-art baseline.4 図2の結果は、計算コストが低いことに加えて、アルゴリズムが最先端のベースラインよりも性能が良いことを示している。 0.71
Figure 2: Testing errors as function of the supervision corruption on real dataset corresponding to classification with partial labels. 図2:部分ラベルによる分類に対応する実データセット上の監視腐敗の機能としてのエラーをテストする。 0.76
We split fully supervised LIBSVM datasets into training and testing dataset. 完全な教師付きLIBSVMデータセットをトレーニングとテストデータセットに分割しました。 0.56
We corrupt training data in order to get partial labels. 部分的なラベルを取得するためにトレーニングデータを破損します。 0.54
Corruption is managed through a parameter, represented by the 𝑥-axis, that relates to the ambiguity degree 𝜂 of Assumption 2. 腐敗は、仮定 2 の曖昧度 η に関連する x-軸で表されるパラメータによって管理される。 0.69
For each methods (our algorithm (DF), the baseline (IL), and the baseline of the baseline (AC, consisting of averaging candidates 𝑦𝑖 in sets 𝑆𝑖)), we consider weights 𝛼 given by kernel ridge regression with Gaussian kernel, for which we optimized hyperparameters with cross-validation on the training set. 各手法(アルゴリズム(DF)、ベースライン(IL)、ベースライン(AC)のベースライン(Si における平均候補 yi からなる)に対して、ガウスカーネルによるカーネルリッジ回帰によって与えられる重み α について検討し、トレーニングセット上で超パラメータをクロスバリデーションで最適化する。 0.77
We then learn an estimate 𝑓𝑛 that we evaluate on the testing set, represented by the 𝑦-axis, on which we have full supervision. 次に、y軸で表されるテストセットで評価する推定fnを学び、その上で完全な監督を行う。
訳抜け防止モード: 次に、テストセットで評価する見積 fn を学びます。 私達に完全な監督があるy軸によって表される。
The figure show the superiority of our method, that achieves error similar to baseline when full supervision (𝑥 = 0) or no supervision (𝑥 = 100%) is given, but performs better when only in presence of partial supervision. この図は,全監督 (x = 0) や監督 (x = 100%) が与えられていない場合に,基準線に類似した誤差を達成する手法の優越性を示すが,部分監督が存在する場合にのみ優れた性能を発揮する。 0.58
See Appendix D for reproducibility specifications, where we also provide Figure 6 showcasing similar empirical results in the case of ranking with partial ordering. 再現性仕様については付録Dを参照してください。ここでは、部分順序付けでランキングした場合に同様の実証結果を示す図6も示します。 0.56
Beyond Eq. (2) - Semi-supervised learning. Eqより。 (2) - 半教師付き学習。 0.67
The main limitation of Eq. 主な制限はEqである。 0.83
(2) is that it is a pointwise principle that decorrelates inputs, in the sense that the optimization of 𝜇∗|𝑥, for 𝑥 ∈ X , only depends on 𝜈|𝑥 and not on what is happening on X\ {𝑥}. (2) は、x ∈ X に対する μ∗|x の最適化は ν|x にのみ依存し、X\ {x} 上で何が起こっているかには依存しないという意味で、入力をデコレーションする点ワイズ原理である。 0.74
As such, this principle failed to tackle semi-supervised learning, where 𝜈|𝑥 is equal to 𝜇|𝑥 (in the sense that 𝜋|𝑥,𝑦 = 𝛿{𝑦}) for 𝑥 ∈ X𝑙 and is equal to 𝛿Y for 𝑥 ∈ X𝑢 := X\X𝑙. したがって、この原理は、x ∈ Xl に対して ν|x が μ|x (π|x,y = δ{y}) に等しく、x ∈ Xu := X\Xl に対して δY に等しくなる半教師付き学習に取り組むことに失敗した。 0.82
In such a setting, for 𝑥 ∈ X𝑢, 𝜇∗|𝑥 can be set to any 𝛿𝑦 for 𝑦 ∈ Y. Interestingly, in practice, while the baseline suffer the same limitation, for our algorithm, weighting schemes have a regularization effect, that contrasts with those considerations. このような設定では、x ∈ Xu に対して、μ*|x は y ∈ Y に対して任意の δy に設定することができる。
訳抜け防止モード: そのような設定では、x ∈ Xu に対して μ∗|x は y ∈ Y に対して任意の δy に設定できる。 実際には、ベースラインが同じ制限を被っている間、我々のアルゴリズムは、 重み付け方式には 規則化効果があります。
We illustrate it on Figure 3. Figure 3: Semi-supervised learning, “concentric circle” instance with four classes (red, green, blue, yellow). 図3に示します。 図3: 半教師付き学習、四つのクラス(赤、緑、青、黄色)を持つ“同心円”インスタンス。 0.65
Reproducibility details provided in Appendix D. (Left) We represent points 𝑥𝑖 ∈ X ⊂ R2, there is many unlabelled points (represented by black dots and corresponding to 𝑆𝑖 = Y), and one labelled point for each class (represented in color, corresponding to 𝑆𝑖 = {𝑦𝑖}). Appendix D. (Left) で提供される再現性の詳細 点 xi ∈ X ・ R2 を表し、多くの不規則点(黒い点で表され、Si = Y に対応する)と各クラスのラベル付き点(Si = {yi} に対応する色で表される)がある。 0.79
(Middle) Reconstruction 𝑓𝑛 : X → Y given by our algorithm Eqs. (中) アルゴリズム Eqs によって与えられる再構成 fn : X → Y。 0.85
(4) and (5). (4)と(5)である。 0.72
Our algorithm succeeds to comprehend the concentric circle structure of the input distribution and clusters classes accordingly. 本アルゴリズムは入力分布とクラスタクラスの同心円構造を理解することに成功している。 0.82
(Right) Reconstruction 𝑓𝑛 : X → Y given by the baseline Eq. (右) リコンストラクション fn : X → Y はベースライン Eq によって与えられる。 0.84
(13). The baseline performs as if only the four supervised data points where given. (13). ベースラインは、与えられた4つの教師付きデータポイントのみを実行する。 0.76
4All the code is available online - https://github.com/V ivienCabannes/partia l_labelling/. https://github.com/V ivienCabannes/partia l_labelling/。 0.60
10 01020304050607080Cor ruption(in%)Loss“Dna”datasetDFILAC0102030 4050607080Corruption (in%)Loss“Svmguide2”datasetDFILACSemi-su pervisionsettingDFre constructionILrecons truction 10 01020304050607080Cor ruption(in%)Loss “Dna”datasetDFILAC0102030 40607080Corruption(i n%)Loss “Svmguide2”datasetDFILACSemi-su pervisionsettingDFre constructionILrestru ction 0.67
8 Conclusion In this work, we have introduced a structured prediction algorithm Eqs. 8 結論本研究では,構造化予測アルゴリズムEqsを導入した。 0.77
(4) and (5), to tackle partial labelling. (4)および(5)は部分的なラベリングに取り組む。 0.69
We have derived exponential convergence rates for the nearest neighbors instance of this algorithm under classical learnability assumptions. 古典的学習可能性の仮定の下で,このアルゴリズムの最も近い近傍のインスタンスに対する指数収束率を導出した。 0.63
We provided optimization considerations to implement this algorithm in practice, and have successfully compared it with the state-of-the-art. このアルゴリズムを実際に実装するために最適化検討を行い,最先端のアルゴリズムと比較した。 0.76
Several open problems offer prospective follow-up of this works: • Semi-supervised learning and beyond. いくつかのオープンな問題は、この研究の将来のフォローアップを提供する: • 半教師付き学習など。 0.50
While we only proved convergence in situation where 𝜇∗ of Eq. Eq の μ が収束する状況でのみ証明された。 0.71
(2) is uniquely defined, therefore excluding semi-supervised learning, Figure 3 suggests that our algorithm (4) could be analyzed in a broader setting than the one considered in this paper. 2) は一意に定義されるため, 半教師付き学習を除けば, 図3は, アルゴリズム(4) が本論文で検討したものよりも広い範囲で解析できることを示唆している。 0.77
Among others, we conjecture that the non-ambiguity assumption could be replaced by a cluster assumption (Rigollet, 2007) together with a non-ambiguity assumption cluster-wise in Theorem 4. その中で、非曖昧性仮定はクラスタ仮定(Rigollet, 2007)と、Theorem 4 における非曖昧性仮定に置き換えることができると推測する。 0.69
• Hard-coded weak supervision. ・ハードコード弱監督。 0.52
Variational principles Eqs. (2) and (3) could be extended beyond partial labelling to any type of hard-coded weak supervision, which is when weak supervision can be cast as a set of hard constraint that 𝜇 should satisfy, formally written as a set of fully supervised distributions compatible with weak information. 変分原理 eqs。 (2) および(3) は、部分的なラベル付けを超えて、弱い監視をμ が満たすべきハード制約の集合として、弱い情報と互換性のある完全に監視された分布の集合として公式に記述できるような、任意のタイプのハードコードされた弱い監督に拡張することができる。 0.63
Hard-coded weak supervision includes label proportion (Quadrianto et al., 2009; Dulac-Arnold et al., 2019), but excludes supervision of the type “80% of the experts say this nose is broken, and 20% say it is not”. ハードコードによる弱い監督にはラベル比率(quadrianto et al., 2009; dulac-arnold et al., 2019)が含まれているが、「専門家の80%はこの鼻が折れており、20%はそうではないと答えている」タイプの監督は除外している。
訳抜け防止モード: ハードコード弱監督にはラベルの割合(Quadrianto et al , 2009 ; Dulac - Arnold et al , 2019 )が含まれる。 専門家の80%は鼻が折れていると言っています 20%はそうではないと言っています。
Providing a unifying framework for those problems would make an important step in the theoretical foundation of weakly supervised learning. これらの問題の統一フレームワークを提供することは、弱い教師付き学習の理論的な基礎において重要なステップとなる。 0.60
• Missing input data. •入力データの欠落。 0.84
While weak supervision assumes that only 𝑦 is partially known, in many applications of machine learning, 𝑥 is also only partially known, especially when the feature vector 𝑥 is built from various source of information, leading to missing data. 弱い監督は、yだけが部分的に知られていると仮定しているが、機械学習の多くの応用において、xは部分的にしか知られていない。
訳抜け防止モード: 弱い監督は y だけが部分的に知られていると仮定するが、 機械学習の多くのアプリケーションでは、xは部分的にしか知られていません。 特に、特徴ベクトルxが様々な情報源から構築され、データが欠けている場合。
While we only considered a principle to fill missing output information, similar principles could be formalized to fill missing input information. 欠落した出力情報を埋める原則のみを検討しましたが、欠落した入力情報を埋めるために同様の原則を形式化できます。 0.62
Acknowledgments This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). この研究は、ANR-19-P3IA-0001(PRA IRIE 3IA Institute)を参照する「Agence Nationale de la Recherche」プログラムの一環として、フランス政府によって部分的に資金提供されました。 0.71
References Audibert, J.-Y. Audibert, J.-Yを参照。 0.70
and Tsybakov, A. とTsybakov, A。 0.72
(2007). Fast learning rates for plug-in classifiers. (2007). プラグイン分類器の高速学習率。 0.78
Annals of Statistics. Bach, F. and Harchaoui, Z. 統計学者。 Bach、F.およびHarchaoui、Z。 0.76
(2007). DIFFRAC: a discriminative and flexible framework for clustering. (2007). DIFFRAC: クラスタリングのための差別的で柔軟なフレームワーク。 0.78
In Neural Information Processing Systems 20. 神経系 情報処理システム20。 0.60
Bengio, Y., Delalleau, O., and Roux, N. L. (2006). Bengio, Y., Delalleau, O., and Roux, N. L. (2006)。 0.93
Label propagation and quadratic criterion. ラベル伝播と二次的基準 0.64
In Semi-Supervised Learning. MIT Press. 半監督で 学習。 MIT出版。 0.61
Biau, G. and Devroye, L. (2015). Biau, G. and Devroye, L. (2015)。 0.95
Lectures on the Nearest Neighbor Method. 最近近傍法に関する講義 0.47
Springer International Publishing. Springer International Publishing(英語) 0.71
Boucheron, S., Bousquet, O., and Lugosi, G. (2005). Boucheron, S., Bousquet, O., and Lugosi, G. (2005)。 0.87
Theory of classification: a survey of some recent advances. 分類の理論:いくつかの最近の進歩の調査。 0.81
ESAIM: Probability and Statistics. ESAIM: 確率と統計。 0.75
Cabannes, V., Rudi, A., and Bach, F. (2020). Cabannes, V., Rudi, A., and Bach, F. (2020)。 0.88
Structured prediction with partial labelling through the infimum infimum による部分ラベリングによる構造予測 0.77
loss. In International Conference on Machine Learning. 負けた 機械学習に関する国際会議で。 0.66
Cabannes, V., Rudi, A., and Bach, F. (2021). Cabannes, V., Rudi, A., and Bach, F. (2021)。 0.88
Fast rates in structured prediction. 構造化予測における高速レート。 0.68
Technical Report 2102.00760, 技術報告 2102.00760 0.77
ArXiv. Cao, Z., Qin, T., Liu, T.-Y., Tsai, M.-F., and Li, H. (2007). arxiv。 Cao, Z., Qin, T., Liu, T.-Y., Tsai, M.-F., Li, H. (2007)。 0.81
Learning to rank: from pairwise approach to listwise ランク付けへの学習:ペアワイズアプローチからリストワイズへ。 0.67
approach. In International Conference of Machine Learning. 近づいた 国際機械学習会議に参加。 0.53
Chang, C. and Lin, C. (2011). Chang, C. and Lin, C. (2011)。 0.95
LIBSVM: A library for support vector machines. LIBSVM: ベクターマシンをサポートするためのライブラリ。 0.87
ACM TIST. 11 ACM TIST。 11 0.82
Cid-Sueiro, J., García-García, D., and Santos-Rodríguez, R. (2014). Cid-Sueiro, J., García-García, D., Santos-Rodríguez, R. (2014)。 0.80
Consistency of losses for learning from 学ぶための損失の一貫性 0.84
weak labels. Lecture Notes in Computer Science. 弱いラベル。 コンピュータ科学における講義ノート。 0.70
Ciliberto, C., Rosasco, L., and Rudi, A. Ciliberto、C.、Rosasco、L.、およびRudi、A。 0.82
(2016). A consistent regularization approach for structured prediction. (2016). 構造予測のための一貫した正則化手法 0.75
In Neural Information Processing Systems 29. 内 神経情報処理システム29。 0.67
Ciliberto, C., Rosasco, L., and Rudi, A. Ciliberto、C.、Rosasco、L.、およびRudi、A。 0.82
(2020). A general framework for consistent structured prediction with (2020). 一貫した構造予測のための一般的な枠組み 0.78
implicit loss embeddings. 暗黙の損失埋め込み。 0.67
Journal of Machine Learning Research. journal of machine learning researchの略。 0.70
Cour, T., Sapp, B., and Taskar, B. Cour、T.、Sapp、B.およびTaskar、B。 0.73
(2011). Learning from partial labels. (2011). 部分的なラベルから学ぶ。 0.75
Journal of Machine Learning Research. journal of machine learning researchの略。 0.70
Dabral, R., Mundhada, A., Kusupati, U., Afaque, S., Sharma, A., and Jain, A. Dabral, R., Mundhada, A., Kusupati, U., Afaque, S., Sharma, A., Jain, A. 0.80
(2018). Learning 3D human pose (2018). 3d人間のポーズを学ぶ 0.74
from structure and motion. 構造や動きから始まります 0.75
In European Conference on Computer Vision. 欧州コンピュータビジョン会議に参加。 0.73
Dempster, A., Laird, N., and Rubin, D. (1977). Dempster, A., Laird, N., and Rubin, D. (1977)。 0.89
Maximum likelihood from incomplete data via the EM algorithm. EMアルゴリズムによる不完全データからの最大可能性。 0.80
Journal of the Royal Statistical Society. 王立統計学会 (Royal Statistical Society) の略称。 0.56
Denoeux, T. (2013). Denoeux、T.(2013)。 0.74
Maximum likelihood estimation from uncertain data in the belief function framework. 信念関数の枠組みにおける不確かさデータからの最大推定 0.76
IEEE Transactions on Knowledge and Data Engineerin. IEEE 知識とデータエンジニアに関するトランザクション。 0.83
Doersch, C. and Zisserman, A. Doersch, C. and Zisserman, A。 0.91
(2017). Multi-task self-supervised visual learning. (2017). マルチタスク自己教師付き視覚学習。 0.74
In International Conference on Computer Vision. 国際会議において コンピュータビジョンについてです 0.66
Duchi, J. C., Mackey, L. W., and Jordan, M. I. Duchi、J.C.、Mackey、L.W.、Jordan、M.I。 0.79
(2010). On the consistency of ranking algorithms. (2010). ランキングアルゴリズムの一貫性について。 0.77
In International Conference on Machine Learning. 海外では 機械学習に関する会議。 0.74
Duda, R., Hart, P., and Stork, D. (2000). Duda, R., Hart, P., and Stork, D. (2000)。 0.86
Pattern Classification, 2nd Edition. パターン分類、第2版。 0.78
Wiley. Dulac-Arnold, G., Zeghidour, N., Cuturi, M., Beyer, L., and Vert, J.-P. (2019). Wiley Dulac-Arnold, G., Zeghidour, N., Cuturi, M., Beyer, L., and Vert, J.-P. (2019)。 0.74
Deep multiclass learning from 深いマルチクラス学習。 0.81
label proportions. In ArXiv. ラベルの比率。 ArXiv所属。 0.65
Gong, C., Liu, T., Tang, Y., Yang, J., Yang, J., and Tao, D. (2018). Gong, C., Liu, T., Tang, Y., Yang, J., Yang, J., and Tao, D. (2018)。 0.87
A regularization approach for instance-based インスタンスベースのための正規化アプローチ 0.63
superset label learning. スーパーセットラベル学習。 0.73
IEEE Transactions on Cybernetics. IEEE Transactions on Cybernetics 0.65
Harris, C., Millman, J., van der Walt, S., et al. Harris, C., Millman, J., van der Walt, S., など。 0.78
(2020). Array programming with NumPy. (2020). NumPyによるアレープログラミング。 0.82
Nature. Hein, M., Audibert, J.-Y., and von Luxburg, U. 自然。 Hein, M., Audibert, J.-Y., von Luxburg, U. 0.79
(2007). Graph Laplacians and their convergence on random (2007). グラフ・ラプラシアンとそのランダム収束 0.79
neighborhood graphs. Journal of Machine Learning Research. 近所のグラフ。 journal of machine learning researchの略。 0.71
Heitjan, D. and Rubin, D. (1991). Heitjan, D. and Rubin, D. (1991)。 0.96
Ignorability and coarse data. 不可知性と粗いデータ。 0.76
The Annals of Statistics. Hüllermeier, E. (2014). 統計学者。 Hüllermeier, E. (2014)。 0.73
Learning from imprecise and fuzzy observations: Data disambiguation through 不正確でファジィな観察から学ぶ:データの曖昧化 0.72
generalized loss minimization. International Journal of Approximate Reasoning. 一般化損失最小化 International Journal of Approximate Reasoning(英語) 0.74
Hüllermeier, E., Fürnkranz, J., Cheng, W., and Brinker, K. (2008). Hüllermeier, E., Fürnkranz, J., Cheng, W., and Brinker, K. (2008)。 0.87
Label ranking by learning pairwise preferences. ペアワイズ設定を学習してラベルランキング。 0.57
Artificial Intelligence. IBM (2017). 人工知能。 IBM(2017年)。 0.66
IBM ILOG CPLEX 12.7 User’s Manual. IBM ILOG CPLEX 12.7 ユーザーマニュアル。 0.79
IBM ILOG CPLEX Division. IBM ILOG CPLEX Division所属。 0.93
Jia, Y., Zhang, Y., Weiss, R., Wang, Q., Shen, J., Ren, F., Chen, Z., Nguyen, P., Pang, R., Lopez-Moreno, I., and Wu, Y. Jia, Y., Zhang, Y., Weiss, R., Wang, Q., Shen, J., Ren, F., Chen, Z., Nguyen, P., Pang, R., Lopez-Moreno, I., and Wu, Y。 0.88
(2018). Transfer learning from speaker verification to multispeaker text-to-speech synthesis. (2018). 話者検証から多話者音声合成への変換学習 0.78
In Neural Information Processing Systems. 神経情報処理システム。 0.58
Jin, R. and Ghahramani, Z. Jin, R. and Ghahramani, Z 0.81
(2002). Learning with multiple labels. (2002). 複数のラベルで学ぶ。 0.83
In Neural Information Processing Systems. 神経情報処理システム。 0.58
Joulin, A., Bach, F., and Ponce, J. Joulin, A., Bach, F., Ponce, J。 0.75
(2010). Discriminative clustering for image co-segmentation. (2010). 画像共同分割のための識別クラスタリング 0.78
In Conference on Computer Vision and Pattern Recognition. 会議では コンピュータビジョンとパターン認識についてです 0.78
Kendall, M. (1938). Kendall, M. (1938)。 0.92
A new measure of rank correlation. ランク相関の新しい尺度。 0.57
Biometrika. 12 バイオメトリカ。 12 0.66
Korba, A., Garcia, A., and d’Alché-Buc, F. (2018). Korba, A., Garcia, A., d'Alché-Buc, F. (2018)。 0.91
A structured prediction approach for label ranking. ラベルランキングのための構造化予測手法 0.74
In Neural Information Processing Systems. 神経系 情報処理システム。 0.60
Lienen, J. and Hüllermeier, E. (2021). Lienen, J. and Hüllermeier, E. (2021)。 0.95
From label smoothing to label relaxation. ラベルの平滑化からラベルの緩和まで。 0.63
In AAAI Conference on Artificial AAAI Conference on Artificial に参加して 0.68
Intelligence. Liu, L.-P. and Dietterich, T. (2014). インテリジェンス。 Liu, L.-P. and Dietterich, T. (2014)。 0.68
Learnability of the superset label learning problem. スーパーセットラベル学習問題の学習可能性 0.69
In International Conference on Machine Learning. 海外では 機械学習に関する会議。 0.74
Luo, J. and Orabona, F. (2010). Luo, J. and Orabona, F. (2010)。 0.95
Learning from candidate labeling sets. 候補のラベリングセットから学ぶ。 0.61
In Neural Information Processing Systems. 神経情報処理システム。 0.58
Miech, A., Zhukov, D., Alayrac, J.-B., Tapaswi, M., Laptev, I., and Sivic, J. Miech, A., Zhukov, D., Alayrac, J.-B., Tapaswi, M., Laptev, I., and Sivic, J. 0.92
(2019). Howto100m: Learning a text-video embedding by watching hundred million narrated video clips. (2019). howto100m: 1億のナレーションビデオクリップを視聴してテキストビデオを埋め込む学習。 0.79
In International Conference on Computer Vision. コンピュータビジョンに関する国際会議に参加。 0.82
Nowak-Vila, A., Bach, F., and Rudi, A. Nowak-Vila, A., Bach, F., Rudi, A。 0.87
(2019). Sharp analysis of learning with discrete losses. (2019). 離散的損失を伴う学習の鋭い分析 0.84
In Artificial Intelligence and Statistics. 人工的に 情報と統計。 0.64
Papandreou, G., Chen, L.-C., Murphy, K., and Yuille, A. Papandreou, G., Chen, L.-C., Murphy, K., and Yuille, A. 0.94
(2015). Weakly- and semi-supervised learning of a deep (2015). 深層学習の弱・半教師学習 0.74
convolutional network for semantic image segmentation. 意味画像分割のための畳み込みネットワーク 0.70
In International Conference on Computer Vision. コンピュータビジョンに関する国際会議に参加。 0.82
Perchet, V. and Quincampoix, M. (2015). Perchet, V. and Quincampoix, M. (2015)。 0.96
On a unified framework for approachability with full or partial 完全あるいは部分的な接近性のための統一フレームワークについて 0.62
monitoring. Mathematics of Operations Research. 監視だ オペレーション・リサーチの数学。 0.69
Quadrianto, N., Smola, A., Caetano, T., and Le, Q. V. (2009). Quadrianto, N., Smola, A., Caetano, T., and Le, Q. V. (2009)。 0.90
Estimating labels from label proportions. ラベル比率からラベルを推定する。 0.68
Journal of Machine Learning Research. 日誌 機械学習の研究です 0.71
Rigollet, P. (2007). Rigollet, P. (2007)。 0.90
Generalization error bounds in semi-supervised classification under the cluster assumption. クラスタ仮定下での半教師付き分類における一般化誤差境界 0.66
Journal of Machine Learning Research. journal of machine learning researchの略。 0.70
Sheppard, W. (1897). シェパード、W.(1897年)。 0.61
On the calculation of the most probable values of frequency constants, for data arranged データ配置における周波数定数の最も可能性の高い値の計算について 0.77
according to equidistant division of a scale. スケールの等価分割に従って。 0.65
Proceedings of the London Mathematical Society. ロンドン数学会(London Mathematical Society)の会員。 0.58
Steinwart, I. and Christmann, A. Steinwart, I. and Christmann, A. 0.94
(2008). Support vector machines. (2008). ベクトルマシンのサポート。 0.86
Springer Science & Business Media. Springer Science & Business Mediaの略。 0.76
Stone, C. (1977). Stone, C. (1977年)。 0.78
Consistent nonparametric regression. 一貫した非パラメトリック回帰。 0.51
The Annals of Statistics. Tobin, J. 統計学者。 トビン、J。 0.56
(1958). Estimation of relationships for limited dependent variables. (1958). 限定依存変数に対する関係の推定。 0.83
Econometrica. van Rooyen, B. and Williamson, R. C. (2017). エコノメトリカ。 van Rooyen, B. and Williamson, R. C. (2017)。 0.68
A theory of learning with corrupted labels. ラベルの破損による学習の理論。 0.73
Journal of Machine Journal of Machine(英語) 0.55
Learning Research. Vapnik, V. (1995). 研究を学ぶ。 vapnik, v. (1995)。 0.83
The Nature of Statistical Learning Theory. 統計的学習理論の性質。 0.73
Springer-Verlag. Springer-Verlag 0.81
Wang, L., Lu, H., Wang, Y., Feng, M., Wang, D., Yin, B., and Ruan, X. Wang, L., Lu, H., Wang, Y., Feng, M., Wang, D., Yin, B., Ruan, X。 0.80
(2017). Learning to detect salient objects (2017). 突出した物体を検知する学習 0.77
with image-level supervision. イメージレベルの監視。 0.69
In Conference on Computer Vision and Pattern Recognition. コンピュータビジョンとパターン認識に関する会議で。 0.81
Xu, L., Neufeld, J., Larson, B., and Schuurmans, D. (2004). Xu, L., Neufeld, J., Larson, B., and Schuurmans, D. (2004)。 0.87
Maximum margin clustering. 最大マージンクラスタリング。 0.65
Neural Information Processing Systems. 神経情報 処理システム。 0.72
Zhou, D., Bousquet, O., Lal, T. N., Weston, J., and Schölkopf, B. Zhou, D., Bousquet, O., Lal, T. N., Weston, J., Schölkopf, B。 0.83
(2003). Learning with local and global (2003). ローカルとグローバルで学ぶ。 0.84
consistency. In Neural Information Processing Systems. 一貫性。 神経情報処理システム。 0.58
Zhu, X., Ghahramani, Z., and Lafferty, J. D. (2003). Zhu, X., Ghahramani, Z., and Lafferty, J. D. (2003)。 0.92
Semi-supervised learning using Gaussian fields and harmonic ガウス場と調和を用いた半教師付き学習 0.51
functions. In International Conference of Machine Learning. 機能。 国際機械学習会議に参加。 0.71
13 13 0.85
A Proofs Mathematical assumptions. To make formal what should be seen as implicit assumptions heretofore, we consider X and Y Polish spaces, Y compact, ℓ : Y × Y → R continuous, H a separable Hilbert space, 𝜑 measurable, and 𝜓 continuous. 数学的仮定の証明。 それまでは暗黙の仮定とみなすべき公式なものを作るために、X と Y のポーランド空間、Y コンパクト、l : Y × Y → R 連続、H を分離可能ヒルベルト空間、φ 可測、および φ 連続とみなす。 0.75
We also assume that for 𝜈𝑥-almost every 𝑥 ∈ X , and any 𝜇 (cid:96) 𝜈, that the pushforward measure 𝜑∗𝜇|𝑥 has a second moment. また、すべての x ∈ x および任意の μ (cid:96) ν に対して、プッシュフォワード測度 φ∗μ|x が第二モーメントを持つと仮定する。 0.72
This is the sufficient setup in order to be able to define formally objects and solutions considered all along the paper. これは、紙に沿って考慮された公式なオブジェクトとソリューションを定義することができる十分なセットアップです。 0.77
Notations. Beside standard notations, we use #Y to design the cardinality of Y, and 2Y to design the set of subsets of Y. 表記。 標準的な表記に加えて、#Y を使って Y のカーディナリティを、2Y で Y のサブセットを設計する。 0.60
Regarding measures, we use 𝜇X and 𝜇|𝑥 respectively the marginal over X and the conditional accordingly to 𝑥 of 𝜇 ∈ ΔX×Y. 測度については、それぞれ μX と μ|x を μ ∈ ΔX×Y の x に対して境界オーバー X と条件付きとする。 0.73
We denote by 𝜇⊗𝑛 the distribution of the random variable (𝑍1, · · · , 𝑍𝑛), where the 𝑍𝑖 are sampled independently according to 𝜇. 我々は、Ziがμに応じて独立にサンプリングされるランダム変数(Z1, · · · · · , Zn)の分布をμ*nで示します。 0.80
For 𝐴 a Polish space, we consider Δ𝐴 the set of Borel probability measures on this space. ポーランド空間 A に対して、ΔA をこの空間上のボレル確率測度の集合と考える。 0.71
For 𝜑 : Y → H and 𝑆 ⊂ Y, we φ : Y → H および S > Y に対して、我々は 0.91
denote by 𝜑(𝑆) the set {𝜑(𝑦) | 𝑦 ∈ 𝑆}. φ(s) で表すと、集合 { φ(y) | y ∈ s} となる。 0.82
For a family of sets (𝑆𝑖), we denote by 𝑆𝑖 the Cartesian product 𝑆1 × 𝑆2 × · · · , also defined as the set of points (𝑦𝑖) such that 𝑦𝑖 ∈ 𝑆𝑖 for all index 𝑖, and by Y 𝑛 the Cartesian product𝑖≤𝑛 Y. 集合 (Si) の族に対して、d は直交積 S1 × S2 × · · · · であり、すべての指数 i に対して yi ∈ Si が yi ∈ Y であるような点 (yi) の集合として定義される。 0.70
Finally, for 𝐸 a subset ∫ 𝑥 d𝜇(𝑥), extending this notation usually reserved to probability measure. 最後に、E に対して、この表記を通常確率測度に限定して拡張する部分集合 x dμ(x) が与えられる。 0.60
More importantly, when considering 2Y, we should さらに重要なことに 2yを考えてみると 0.62
of a vector space 𝐸(cid:48), Conv 𝐸 denotes the convex hull of 𝐸 and Span(𝐸) its span. ベクトル空間 E(cid:48) について、Conv E は E と Span(E) の凸包を表す。 0.74
Abuse of notations. For readability sake, we have abused notations. 表記の乱用。 可読性のため、私たちは表記法を悪用した。 0.55
For a signed measure 𝜇, we denote by E𝜇[𝑋] the integral actually restrict ourselves to the subspace S ⊂ 2Y of closed subsets of Y, as S is a Polish space (metrizable by the Hausdorff distance) while 2Y is not always. 符号付き測度 μ に対して、積分は実際に Y の閉部分集合の部分空間 S × 2Y に制限されることを Eμ[X] で表すが、S はポーランド空間(ハウスドルフ距離で測れる)であるが、2Y は必ずしもそうではない。 0.76
However, when Y is finite, those two spaces are equals, 2Y = S. しかし、Y が有限であるとき、それらの2つの空間は等しい、2Y = S である。 0.69
A.1 Proof of Lemma 3 From Lemma 3 in Cabannes et al. A.1 Lemma 3 From Lemma 3 in Cabannes et al. (英語) 0.82
(2021), we pulled the calibration inequality (2021年) 校正の不平等を 0.58
R( 𝑓𝑛) − R( 𝑓 ∗) ≤ 2𝑐𝜓 E(cid:2)1(cid:107)𝑔𝑛( 𝑋)−𝑔∗( 𝑋) (cid:107)>𝑑(𝑔∗( 𝑋),𝐹) (cid:107)𝑔𝑛(𝑋) − 𝑔∗(𝑋)(cid:107)(cid:3) . R(fn) − R(f ∗) ≤ 2c = E(cid:2)1(cid:107)gn (X) −g∗(X) (cid:107)>d(g∗(X),F) (cid:107)gn(X) −g∗(X)(cid:107)(cid:3) である。 0.90
Where 𝐹 is defined as the set of points 𝜉 ∈ Conv 𝜑(Y) leading to two decodings ここで f は 2 つのデコードに繋がる点 s ∈ conv φ(y) の集合として定義される。 0.69
(cid:26) 𝐹 = (cid:26) 𝐹 = 0.82
𝜉 ∈ Conv 𝜑(Y) ~ ∈ Conv φ(Y) 0.82
(cid:27) (cid:12)(cid:12)(cid :12)(cid:12) # arg min 𝑛(𝑋) − 𝑔∗(𝑋)(cid:13)(cid:13) and that, if 𝑎 ≤ 𝑏 + 𝑐, (cid:27) (cid:12)(cid:12)(cid :12)(cid:12) # arg min n(x) − g∗(x)(cid:13)(cid:13) and that, if a ≤ b + c, 0.84
(cid:104)𝜓(𝑧), 𝜉(cid:105) > 1 (cid:104)ψ(z) ,(cid:105) > 1 0.95
(cid:107)𝜉 − 𝜉(cid:48)(cid:107)H . (cid:107)--(cid:48)( cid:107)h。 0.83
𝑧∈Y , and 𝑑 is defined as the extension of the norm distance to sets, for 𝜉 ∈ H z∈Y , そして d は集合へのノルム距離の延長として定義される。
訳抜け防止モード: z∈Y , d は集合へのノルム距離の拡張として定義される。 s ∈ H に対して
1𝑎>𝛿𝑎 ≤ 1𝑏+𝑐>𝛿𝑏 + 𝑐 ≤ 12 sup(𝑏,𝑐) >𝛿2 sup 𝑏, 𝑐 = 2 sup 𝑒∈𝑏,𝑐 1𝑎>𝛿𝑎 ≤ 1𝑏+𝑐>𝛿𝑏 + 𝑐 ≤ 12 sup(𝑏,𝑐) >𝛿2 sup 𝑏, 𝑐 = 2 sup 𝑒∈𝑏,𝑐 0.95
Using that (cid:107)𝑔𝑛(𝑋) − 𝑔∗(𝑋)(cid:107) ≤(cid:13)(cid:13)𝑔𝑛(𝑋) − 𝑔∗ R( 𝑓𝑛) − R(𝑔∗) ≤ 4𝑐𝜓 E(cid:2)12(cid:107)𝑔𝑛( 𝑋)−𝑔∗ E(cid:2)12(cid:107)𝑔𝑛( 𝑋)−𝑔∗ それを使用して (cid:107)gn(X)(cid:1 07) ≤(cid:13)(cid:13)gn(X ) − g* R(fn) − R(g) ≤ 4c* E(cid:2)12(cid:107)g n(X)−g* E(cid:2)12(cid:107)g n(X)−g) 0.88
The first term is bounded with 最初の用語は有界です。 0.66
We get the refined inequality While for the second term, we proceed with 洗練された不平等と 2期目の間、私たちは進みます 0.60
𝑛( 𝑋)−𝑔∗( 𝑋) (cid:107)>𝑑(𝑔∗( 𝑋),𝐹)(cid:13)(cid:13)𝑔∗ E(cid:2)12(cid:107)𝑔∗ When weights sum to one, that is𝑛 n(x)−g∗(x) (cid:107)>d(g∗(x),f)(cid:13)(cid:1 3)g∗ e(cid:2)12(cid:107)g ∗ 重量が 1 に積もったとき、そのイシン 0.75
𝑑(𝜉, 𝐹) = inf 𝜉(cid:48)∈𝐹 d(~, F) = inf ~(cid:48)・F 0.80
𝑛(𝑋)(cid:13)(cid:13) +(cid:13)(cid:13)𝑔∗ 𝑛( 𝑋) (cid:107)>𝑑(𝑔∗( 𝑋),𝐹)(cid:13)(cid:13)𝑔𝑛(𝑋) − 𝑔∗ 𝑛( 𝑋) (cid:107)>𝑑(𝑔∗( 𝑋),𝐹)(cid:13)(cid:13)𝑔𝑛(𝑋) − 𝑔∗ 𝑛(𝑋) − 𝑔∗(𝑋)(cid:13)(cid:13)(ci d:3) ≤(cid:13)(cid:13)𝑔∗ 𝑛 − 𝑔∗(cid:13)(cid:13)𝐿∞ P𝑋 (cid:13)(cid:13)𝑔∗ 𝑛 − 𝑔∗(cid:13)(cid:13)𝐿∞ ≤ 2𝑐𝜑. n(X)(cid:13)(cid:13) (cid:13) +(cid:13)(cid:13)(cid :13)g∗ n(X) (cid:107)>d(g∗(X) − g∗ n(X) (cid:107)>d(g∗(X) − g∗(X) (cid:13)(cid:13)(cid :13)(cid:3) ≤(cid:13)(cid:13)(cid :13)g∗ n − g∗(cid:13)(cid:13)(cid :13)L∞ PX(cid:13)(cid:13)(c id:13)g∗ n − g∗(cid:13)(cid:13)(cid :13)L∞ 2c(cid:13)(cid:13)L∞ 2c)。 0.79
𝑖=1 𝛼𝑖(𝑋) = 1, both 𝑔∗ 𝑖=1 𝛼𝑖(𝑋) = 1, both 𝑔∗ 0.92
1𝑒>𝛿𝑒 ≤ 21𝑏>𝛿𝑏 + 21𝑐>𝛿𝑐. 1𝑒>𝛿𝑒 ≤ 21𝑏>𝛿𝑏 + 21𝑐>𝛿𝑐. 0.96
𝑛( 𝑋)−𝑔∗( 𝑋) (cid:107)>𝑑(𝑔∗( 𝑋),𝐹)(cid:13)(cid:13)𝑔∗ n(X)−g∗(X) (cid:107)>d(g∗(X),F)(cid:13)(cid:1 3)g∗ 0.93
𝑛(𝑋)(cid:13)(cid:13) + 12(cid:107)𝑔∗ 𝑛(𝑋)(cid:13)(cid:13)(ci d:3) ≤(cid:13)(cid:13)𝑔𝑛 − 𝑔∗ (cid:13)(cid:13)𝐿1 . n(X)(cid:13)(cid:13) + 12(cid:107)g∗ n(X)(cid:13)(cid:13) (cid:3) ≤(cid:13)(cid:13)gn − g∗ (cid:13)(cid:13)L1。 0.79
(cid:18) 𝑛(𝑋) − 𝑔∗(𝑋)(cid:13)(cid:13) > 2(cid:13)(cid:13)𝑔∗ (cid:18) n(X) − g(X)(cid:13)(cid:13) > 2(cid:13)(cid:13) 0.88
𝑛 𝑛(𝑋) − 𝑔∗(𝑋)(cid:13)(cid:13)(ci d:3) . 𝑛 n(X) − g∗(X)(cid:13)(cid:13)( cid:3)。 0.84
(cid:19) 𝑑(𝑔∗(𝑋), 𝐹) 𝑛(𝑋) and 𝑔∗(𝑋) are averaging of 𝜑(𝑦) for 𝑦 ∈ Y, therefore (cid:19) d(g∗(X), F) n(X) および g∗(X) は y ∈ Y に対する φ(y) の平均化である。 0.82
𝑥∈supp 𝜈X xftpsupp νx 0.61
inf . Finally, when the labels are a deterministic function of the input, 𝑔∗(𝑋) = 𝜑( 𝑓 ∗(𝑋)), and 𝑑(𝑔∗(𝑋), 𝐹) ≤ sup𝑦∈Y 𝑑(𝜑(𝑦), 𝐹). inf . 最後に、ラベルが入力の決定論的関数であるとき、 g*(X) = φ(f )(X)), d(g*(X), F) ≤ supy∈Y d(φ(y), F) となる。 0.83
Defining 𝛿 := sup𝑦∈Y 𝑑(𝜑(𝑦), 𝐹)/2, and adding everything together leads to Lemma 3. δ := supy∈Y d(φ(y), F)/2 を定義し、すべてを一緒に追加すると Lemma 3 となる。 0.85
14 14 0.85
Implication of Assumptions 2 and 3 推定 2 および 3 の含意 0.67
A.2 Assume that Assumption 2 holds, consider 𝑥 ∈ supp 𝜈X , let us show that 𝑓 ∗(𝑥) = 𝑦𝑥 and 𝜇∗|𝑥 = 𝛿𝑦𝑥. A.2 仮定 2 が成り立つとすると、x ∈ supp νX を考えると、f ∗(x) = yx と μ∗|x = δyx が成り立つ。 0.86
First of all, notice that まず最初に注意してください。 0.61
𝑆;𝑆∈supp 𝜈|𝑥 = {𝑦𝑥}; that 𝛿𝑦𝑥 (cid:96) 𝜈|𝑥, as it corresponds to 𝜋|𝑥,𝑆 = 𝛿𝑦𝑥 ∈ Δ𝑆, for all 𝑆 in the support of 𝜈|𝑥; and that, because ℓ is S;S∈supp ν|x = {yx}; その δyx (cid:96) ν|x は π|x,S = δyx ∈ ΔS に対応する。
訳抜け防止モード: すなわち δyx ( cid:96 ) ν|x である。 π|x,s = δyx ∈ δs に対応するので、ν|x の台を持つすべての s に対して ν|x ; だってlは
well-behaved, ℓ(𝑧, 𝑦𝑥) = ℓ(𝑦𝑥, 𝑦𝑥) = 0. よく振る舞う。 ℓ(𝑧, 𝑦𝑥) = ℓ(𝑦𝑥, 𝑦𝑥) = 0. 0.58
inf 𝑧∈Y This infimum is only achieved for 𝑧 = 𝑦𝑥, hence if we prove that 𝜇∗|𝑥 = 𝛿𝑦𝑥, we directly have that 𝑓 ∗(𝑥) = 𝑦𝑥. inf z∈Y このインフィムは z = yx に対してのみ達成されるため、μ∗|x = δyx が証明されたとき、直接 f ∗(x) = yx となる。 0.76
Finally, suppose that 𝜇|𝑥 (cid:96) 𝜈|𝑥 charges 𝑦 ≠ 𝑦𝑥. 最後に、μ|x (cid:96) ν|x が y > yx を課すと仮定する。 0.57
Because 𝑦 does not belong to all sets charged by 𝜈|𝑥, 𝜇|𝑥 should charge an other 𝑦(cid:48) ∈ Y, and therefore y は ν|x で表されるすべての集合に属さないので、μ|x は他の y(cid:48) ∈ Y を充電しなければならない。 0.64
E𝑌∼𝜇|𝑥 [ℓ(𝑧, 𝑦)] ≥ inf 𝑧∈Y Which shows that 𝜇∗|𝑥 = 𝛿𝑦𝑥. EY\μ|x [l(z, y)] ≥ inf z∂Y これは μ∗|x = δyx を示す。 0.70
We deduce that 𝑔∗(𝑥) = 𝑦𝑥. g*(x) = yx と仮定する。 0.68
and 𝑓 (𝑥(cid:48)) = 𝑦(cid:48). f (x(cid:48)) = y(cid:48) である。 0.80
We have that 𝑔∗(𝑥) = 𝜑(𝑦) and 𝑔∗(𝑥(cid:48)) = 𝜑(𝑦(cid:48)), therefore, したがって、g∗(x) = φ(y) と g∗(x(cid:48)) = φ(y(cid:48)) である。 0.82
inf 𝑧∈Y 𝜇|𝑥(𝑦)ℓ(𝑧, 𝑦) + 𝜇|𝑥(𝑦(cid:48))ℓ(𝑧, 𝑦(cid:48)) > 0. inf z∈Y μ|x(y)l(z, y) + μ|x(y(cid:48))l(z, y(cid:48)) > 0 0.83
Now suppose that Assumption 3 holds too, and consider two 𝑥, 𝑥(cid:48) ∈ supp 𝜈X belonging to two different classes 𝑓 (𝑥) = 𝑦 仮定 3 も成り立つと仮定し、二つの異なるクラス f (x) = y に属する x, x(cid:48) ∈ supp νX を考える。 0.85
Define ℎ2 = inf 𝑦≠𝑦(cid:48) 𝑐−1 (cid:107)𝜑(𝑦) − 𝜑(𝑦(cid:48))(cid:107)H. Let us now show that ℎ2 > 0. h2 = inf y\y(cid:48) c−1 (cid:107) φ(y) − φ(y(cid:48))(cid:107) h と定義する。 0.89
When Y is finite, this infimum is a minimum, therefore, ℎ2 = 0, only if there exists a 𝑦 ≠ 𝑦(cid:48), such that 𝜑(𝑦) = 𝜑(𝑦(cid:48)), which would implies that ℓ(·, 𝑦) = ℓ(·, 𝑦(cid:48)) and therefore ℓ(𝑦, 𝑦(cid:48)) = ℓ(𝑦, 𝑦) which is impossible when ℓ is proper. y が有限であるとき、このインフィムは最小であり、従って h2 = 0 は、 φ(y) = φ(y(cid:48)) であるような y(y) = φ(y(cid:48)) が存在し、したがって l(y, y(cid:48)) = l(y, y(cid:48)) であり、したがって l が正則であれば不可能である。 0.82
𝑑(𝑥, 𝑥(cid:48)) ≥ 𝑐−1 (cid:107)𝜑(𝑦) − 𝜑(𝑦(cid:48))(cid:107)H . d(x, x(cid:48)) ≥ c−1 (cid:107)φ(y) − φ(y(cid:48))(cid:107) H である。 0.83
A.3 Proof of Theorem 4 Reusing Lemma 3, we have a.3 定理 4 の証明 lemma 3 を使って 0.72
E( 𝑓𝑛) ≤ 4𝑐𝜓 ED𝑛,𝑋(cid:2)(cid:13)(cid: 13)𝑔∗ E( fn) ≤ 4c\ EDn,X(cid:2)(cid:13) (cid:13)g 0.82
We will first prove that 私たちはまずそれを証明します 0.60
𝑛(𝑋) − 𝑔𝑛(𝑋)(cid:13)(cid:13)H 𝑛( 𝑋)−𝑔∗( 𝑋) (cid:107)>𝛿(cid:3) ≤ exp (cid:2)1(cid:107)𝑔∗ n(X) − gn(X)(cid:13)(cid:13 )(cid:13)H n(X)−g∗(X) (cid:107)>δ(cid:3) ≤ exp(cid:2)1(cid:107) g∗ 0.81
(cid:16)− 𝑛𝑝 (cid:16)-np 0.84
𝑛( 𝑋)−𝑔∗( 𝑋) (cid:107)>𝛿(cid:3) . n(X)−g∗(X) (cid:107)>δ(cid:3)。 0.84
(cid:3) + 8𝑐𝜓𝑐𝜑 ED𝑛,𝑋(cid:2)1(cid:107)𝑔∗ (cid:17) 𝑛(𝑥) = 𝑘−1𝑖;𝑋𝑖∈N (𝑥) 𝜑(𝑦𝑖) = 𝜑(𝑦𝑥) = 𝑔∗(𝑥), (cid:3) + 8cψcφ edn,x(cid:2)1(cid:10 7)g∗ (cid:17) n(x) = k−1i;xihtmln (x) φ(yi) = φ(yx) = g∗(x) 0.85
8 as long as 𝑘 < 𝑛𝑝/2. 8 k < np/2 である。 0.85
The error between 𝑔∗ and 𝑔𝑛 relates to classical supervised learning of 𝑔∗ from samples (𝑋𝑖, 𝑌𝑖) ∼ 𝜇∗. g∗ と gn の間の誤差は、サンプル (Xi, Yi) から g∗ の古典的な教師付き学習に関係している。 0.58
We invite the reader who would like more insights on this fully supervised part of the proof to refer to the several monographs written on local averaging methods and, in particular, nearest neighbors, such as Biau and Devroye (2015). 証拠のこの完全に監督された部分についてもっと詳しく知りたい読者を招待し、ローカル平均法で書かれたいくつかのモノグラフ、特にBiauやDevroye(2015)などの近隣諸国を参照してください。
訳抜け防止モード: 我々は,この証明の完全に監督された部分についてさらなる洞察を求める読者を招待し,局所平均化法に書かれたいくつかのモノグラフを参照する。 特に特に biau や devroye (2015) といった近隣諸国。
Because of class separation, we know that, if 𝑘 points fall at distance at most ℎ of 𝑥 ∈ supp 𝜈X , 𝑔∗ where N (𝑥) designs the 𝑘-nearest neighbors of 𝑥 in (𝑋𝑖). クラス分離のため、k 個の点が x ∈ supp νX , g∗ の最大 h で一致するとき、N (x) は x in (Xi) の k-アネレス近傍を設計する。 0.78
Because the probability of falling at distance ℎ of 𝑥 for each 𝑋𝑖 is lower bounded by 𝑝, we have that 各Xi に対して x の距離 h で落ちる確率は p より低いので、我々はそれを持っている。 0.78
ED𝑛 For the disambiguation part in(cid:13)(cid:13)𝑔𝑛 − 𝑔∗ EDn 曖昧化部分 in(cid:13)(cid:13)gn − g について 0.72
𝑘-neighbors at are distance at least ℎ, ensuring that disambiguation can be done by clusters, and datasets that does not verify this property. k-neighbor は少なくとも h の距離であり、クラスタやこのプロパティを検証しないデータセットによって曖昧さを回避できる。 0.73
Consider the event This can be upper bound by exp(−𝑛𝑝/8) as soon as 𝑘 < 𝑛𝑝/2, based on Chernoff multiplicative bound (see Biau and Devroye, 2015, for a reference), meaning イベントを考える これは k < np/2 のときすぐに exp(−np/8) で上限となり、チャーンオフ乗法の境界(参照は biau と devroye, 2015 を参照)に基づく。
訳抜け防止モード: イベントを考える これは k < np/2 の直後にexp(−np/8 ) によって上界化することができる。 Chernoff乗法境界に基づく (参考文献:Bau and Devroye, 2015)
PD𝑛(𝑔∗ 𝑛(𝑥) ≠ 𝑔∗(𝑥)) ≤ P(Bernouilli(𝑛, 𝑝) < 𝑘). PDn(g∗) 𝑛(𝑥) ≠ 𝑔∗(𝑥)) ≤ P(Bernouilli(𝑛, 𝑝) < 𝑘). 0.89
𝑛 ED𝑛,𝑋(cid:2)1(cid:107)𝑔∗ (cid:13)(cid:13)𝐿1, we distinguish two types of datasets, the ones where for any input 𝑋𝑖 its (cid:26) (cid:13)(cid:13)𝑔∗ 𝑛 EDn,X(cid:2)1(cid:10 7)g∗ (cid:13)(cid:13)L1, we distinguish two type of datasets, the which where for any input Xi its (cid:26) (cid:13)(cid:13)g∗ 0.85
𝑛( 𝑋)−𝑔∗( 𝑋) (cid:107)≥𝛿(cid:3) ≤ exp(−𝑛𝑝/8). n(X)−g∗(X) (cid:107)≥δ(cid:3) ≤ exp(−np/8)。 0.85
(cid:12)(cid:12)(cid :12)(cid:12) sup (cid:27) (cid:13)(cid:13)∞ PD𝑛((𝑋𝑖) ∉ D) + ED𝑛,𝑋(cid:2)(cid:13)(cid: 13)𝑔∗ (cid:12)(cid:12)(cid :12)(cid:27) (cid:13)(cid:13)∞ PDn((Xi) > D) + EDn,X(cid:2)(cid:13) (cid:13)g∗ 0.87
𝑛(𝑋) − 𝑔𝑛(𝑋)(cid:13)(cid:13)H n(X) − gn(X)(cid:13)(cid:13 )H 0.95
(cid:12)(cid:12) (𝑋𝑖) ∈ D(cid:3) , (cid:12)(cid:12) (Xi) ∈ D(cid:3) , 0.86
(𝑋𝑖)𝑖≤𝑛 𝑛 − 𝑔𝑛 (𝑋𝑖)𝑖≤𝑛 𝑛 − 𝑔𝑛 0.85
𝑑(𝑋𝑖, 𝑋(𝑘)(𝑋𝑖)) < ℎ where 𝑋(𝑘)(𝑥) design the 𝑘-th nearest neighbor of 𝑥 in (𝑋𝑖)𝑖≤𝑛. d(Xi, X(k)(Xi)) < h ここで X(k)(x) は (Xi)i≤n において x の k 番目の近傍を設計する。 0.88
We proceed with D = 𝑖 私たちは D = 𝑖 0.76
ED𝑛,𝑋(cid:2)(cid:13)(cid: 13)𝑔∗ EDn,X(cid:2)(cid:13) (cid:13)g∗ 0.78
𝑛(𝑋) − 𝑔𝑛(𝑋)(cid:13)(cid:13)H n(X) − gn(X)(cid:13)(cid:13 )H 0.95
(cid:3) ≤ sup (cid:3) ≤ sup 0.88
𝑋∈X 15 X∈X 15 0.72
Which is based on 𝐸[𝑍] = P(𝑍 ∈ 𝐴) E[𝑍| 𝐴] + P(𝑍 ∉ 𝐴) E[𝑍|𝑐 𝐴]. これは E[Z] = P(Z ∈ A) E[Z| A] + P(Z ) A) E[Z|c A] に基づいている。 0.93
For the term corresponding to bad datasets, we can bound 𝑛(𝑋), are the disambiguation error with the maximum error. 悪いデータセットに対応する用語に対して、n(x) は最大の誤差を伴う曖昧さの誤りである。 0.70
Similarly to the derivation for Lemma 3, because 𝑔∗ averaging of 𝜑(𝑦), we have that Lemma 3 の導出と同様に、φ(y) の g∗ 平均化が成り立つからである。 0.76
𝑛(𝑥) and 𝑔∗ (cid:13)(cid:13)𝑔𝑛(𝑥) − 𝑔∗ n(x) と g∗ (cid:13)(cid:13)gn(x ) − g 0.91
𝑛(𝑥)(cid:13)(cid:13) ≤ 2𝑐𝜑. n(x)(cid:13)(cid:13) ≤ 2cφ。 0.85
sup 𝑥∈supp 𝜈X sup xftpsupp νx 0.73
Indeed, we allow ourselves to pay the worst error on those datasets as their probability is really small, which can be proved based on the following derivation. 実際、それらのデータセットの確率が本当に小さいので、私たち自身が最悪のエラーを支払うことを許しています。
訳抜け防止モード: 実際 私たちは データセットに最悪のエラーを 犯すために その確率は非常に小さいため、次の導出に基づいて証明することができる。
PD𝑛((𝑋𝑖)𝑖≤𝑛 ∉ D) = P( 𝑋𝑖)(sup PDn((Xi)i≤n × D) = P( Xi)(sup) 0.97
This last probability has already been work out when dealing with the fully supervised part, and was bounded as この最後の確率は、完全に教師された部分を扱う際に既に検討され、境界づけられた。 0.58
≤ 𝑛∑︁ 𝑖=1 𝑖 ≤ 𝑛∑︁ 𝑖=1 𝑖 0.71
𝑑(𝑋𝑖, 𝑋(𝑘)(𝑋𝑖)) ≥ ℎ) = P( 𝑋𝑖)(cid:0)∪𝑖≤𝑛(cid:8)𝑑(𝑋𝑖, 𝑋(𝑘)(𝑋𝑖)) ≥ ℎ(cid:9)(cid:1) P( 𝑋𝑖)(cid:0)𝑑(𝑋𝑖, 𝑋(𝑘)(𝑋𝑖)) ≥ ℎ(cid:1) = 𝑛 P𝑋,D𝑛−1 (cid:0)𝑑(𝑋, 𝑋(𝑘)(𝑋)) ≥ ℎ(cid:1) . d(Xi, X(k)(Xi)) ≥ h) = P(Xi)(cid:0) ≥ h(cid:8)d(Xi, X(k)(Xi)) ≥ h(cid:9)(cid:1) P(Xi)(cid:0)d(Xi, X(k)(Xi)) ≥ h(cid:1) = n PX, Dn−1(cid:0)d(X, X(k)(X)) ≥ h(cid:1) である。 0.94
(cid:0)𝑑(𝑋, 𝑋(𝑘)(𝑋)) ≥ ℎ(cid:1) ≤ exp (−(𝑛 − 1) 𝑝/8) . (cid:0)d(X, X(k)(X)) ≥ h(cid:1) ≤ exp (−(n − 1) p/8) である。 0.91
(cid:13)(cid:13)∞ PD𝑛((𝑋𝑖)𝑖≤𝑛 ∉ D) ≤ 2𝑐𝜑𝑛 exp (−(𝑛 − 1) 𝑝/8) . (cid:13)(cid:13)∞ PDn((Xi) ≤ 2cφn exp (−(n − 1) p/8) である。 0.90
P𝑋,D𝑛−1 as long as 𝑘 < (𝑛 − 1) 𝑝/2. PX,Dn−1 は k < (n − 1) p/2 である。 0.88
Finally we have 𝑛 − 𝑔𝑛 最後に n − gn である。 0.75
(cid:13)(cid:13)𝑔∗ (cid:13)(cid:13) 0.83
sup 𝑋∈X that ˆ𝑦𝑖 = 𝑦∗ only contained 𝑦∗ sup X∈X yi = y∗ は y∗ のみを含む 0.65
For the expectation term, corresponding to datasets, D𝑛 ∈ D, that cluster data accordingly to classes, we have to make sure 𝑖 is the only acceptable solution of Eq. クラスに応じたクラスタデータのデータセット Dn ∈ D に対応する期待項に対しては、i が Eq の唯一の許容可能な解であることを確認する必要がある。 0.79
(4), which is true as soon as the intersection of 𝑆 𝑗, for 𝑥 𝑗 the neighbors of 𝑥𝑖, (4)、これは s j の交叉と同時に真であり、x j は xi の近傍である。 0.69
𝑖 . To work out the disambiguation algorithm, notice that 𝑖 . 曖昧化アルゴリズムを実行するには、注意してください。 0.68
(cid:13)(cid:13)𝑔𝑛 − 𝑔∗ (cid:13)(cid:13)gn − g∗ 0.78
𝑛 𝑖=1 ∫ X = 𝑘−1 𝑛 𝑖=1 ∫ X = k−1 0.77
(cid:13)(cid:13)𝐿1 = (cid:13)(cid:13)L1 = 0.76
𝛼𝑖(𝑥)𝜑( ˆ𝑦𝑖) − 𝜑(𝑦∗ 𝑖 ) 𝛼𝑖(𝑥)𝜑( ˆ𝑦𝑖) − 𝜑(𝑦∗ 𝑖 ) 0.91
(cid:13)(cid:13)(cid :13)(cid:13)(cid:13) d𝜈X (𝑥) ≤ (cid:13)(cid:13)(cid :13)(cid:13)(cid:13) 𝑛∑︁ 𝑛∑︁ P𝑋 (𝑋𝑖 ∈ N (𝑋))(cid:13)(cid:13)𝜑( ˆ𝑦𝑖) − 𝜑(𝑦∗ (cid:34) 𝑛∑︁ (cid:12)(cid:12) (𝑋𝑖) ∈ D(cid:3) = 2𝑐𝜑 𝑘−1 E( 𝑋𝑖) 𝑛(𝑋) − 𝑔𝑛(𝑋)(cid:13)(cid:13)H (cid:34) 𝑛∑︁ (cid:13)(cid:13)(cid :13)(cid:13)(cid:13) (cid:13) dνx (x) ≤ (cid:13)(cid:13)(cid :13)(cid:13) n の px (xi ∈ n (x))(cid:13)(cid:13) (cid:13) φ(syi) − φ(y∗ (cid:34) n (cid:12)(cid:12) (xi) ∈ d(cid:3) = 2cφ k−1 e(xi) n(x) − gn(x)(cid:13)(cid:13 ) h(cid:34) n である。 0.72
𝑖=1 𝑖=1 = 2𝑐𝜑 𝑘−1 E( 𝑋𝑖),𝑋 𝑖=1 𝑖=1 = 2cφ k−1 E(Xi), X 0.68
X 𝑖=1 𝑘−1 ∫ 𝑛∑︁ 𝑖 )(cid:13)(cid:13) ≤ 2𝑐𝜑 𝑘−1 X 𝑖=1 𝑘−1 ∫ 𝑛∑︁ 𝑖 )(cid:13)(cid:13) ≤ 2𝑐𝜑 𝑘−1 0.69
P𝑋 (𝑋𝑖 ∈ N (𝑋)) 1𝜑( ˆ𝑦𝑖)≠𝜑(𝑦∗ 𝑖 ) . PX (Xi ∈ N (X)) 1φ( yyi) φ(y, i ) である。 0.88
1𝑋𝑖∈N (𝑥)(cid:13)(cid:13)𝜑( ˆ𝑦𝑖) − 𝜑(𝑦∗ 𝑛∑︁ 1Xi・N(x)(cid:13)(cid:13) φ( syi) − φ(y∗ n) 0.68
𝑖 )(cid:13)(cid:13) d𝜈X (𝑥) (cid:12)(cid:12)(cid :12) (𝑋𝑖)(cid:105)(cid:12)(c id:12)(cid:12)(cid:1 2)(cid:12) (𝑋𝑖) ∈ D (cid:104)1𝜑( ˆ𝑦𝑖)≠𝜑(𝑦∗ 𝑖 )(cid:12)(cid:12) (𝑋𝑖)(cid:1)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12) (𝑋𝑖) ∈ D (cid:35) 1𝑋𝑖∈N ( 𝑋) P(𝑆𝑖)(cid:0)𝜑( ˆ𝑦𝑖) ≠ 𝜑(𝑦∗ i )(cid:13)(cid:13) dνx (x) (cid:12)(cid:12)(cid :12) (xi)(cid:105)(cid:12 )(cid:12)(cid:12)(ci d:12)(cid:12) (xi) ∈ d (cid:104)1 φ( syi) (cid:12)(cid:12) (xi)(cid:12)(cid:12) (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12)(cid:12) (xi) ∈ d (cid:35) 1xiدn (x) p(si)(cid:0) φ(cid:0) (xi) ∈ d (cid:104)1 φ(y) (cid:12)(cid:12) (cid:12) (cid:12) (cid:12) (cid:12)) (cid:12)(cid:12)(cid :12)) (cid:12) (cid:12) (cid:12)(cid:12) (cid:12)(cid:12)(cid :12)(cid:0) (x) (x) (xi) (xi) ∈ d(cid)(cid(y) φ(yi)(yi)(y) φ(y) (y) (y) (y)。 0.38
P𝑋 (𝑋𝑖 ∈ N (𝑋)) E(𝑆𝑖) PX (Xi ∈ N (X)) E(Si) 0.85
𝑖=1 𝑖 ) . (cid:35) 𝑖=1 𝑖 ) . (cid:35) 0.77
𝑖=1 ED𝑛,𝑋(cid:2)(cid:13)(cid: 13)𝑔∗ 𝑖=1 EDn,X(cid:2)(cid:13) (cid:13)g∗ 0.69
Finally we have, after proper conditionning, considering the variability in 𝑆𝑖 while fixing 𝑋𝑖 first, 最後に、適切な条件付けの後、まずXiを固定しながらSiの可変性を考える。 0.64
We design D, because when this event holds, we know that the 𝑘-th nearest neighbor of any input 𝑋𝑖 is at distance at most ℎ of 𝑖 ) and 𝑧 𝑗 = 𝑦 𝑗, 𝑋𝑖, meaning the because of class separation, 𝑦𝑥𝑖 ∈ 𝑆 𝑗 for any 𝑋 𝑗 ∈ N (𝑋𝑖). この事象が成立すると、任意の入力 Xi の k 番目の近傍が (i の最大 h において) と z j = y j, Xi であることが分かるので、クラス分離のため、任意の X j ∈ N (Xi) に対して yxi ∈ S j が成り立つ。 0.79
This mean that outputting ( ˆ𝑦𝑖) = (𝑦∗ will lead to an optimal error in Eq. これは、 ( yi) = (y∗) の出力が Eq の最適誤差につながることを意味する。 0.77
(4). Now suppose that there is an other solution for Eq. (4). ここで、Eqの別の解決策があると仮定する。 0.78
(4) such that ˆ𝑦𝑖 ≠ 𝑦∗ 𝑖 , it should also achieve an optimal error, therefore it should verify 𝑧 𝑗 = ˆ𝑦 𝑗 for all 𝑗 as well as ˆ𝑦 𝑗 = ˆ𝑦𝑖 for all 𝑗 such that 𝑋 𝑗 is one of the 𝑘 nearest neighbors of 𝑋𝑖. (4) であるから、最適誤差も達成できるので、すべての j に対して z j = y j を検証すべきであり、Xj が Xi の k 近傍の1つであるようなすべての j に対して y j = yi を検証すべきである。 0.89
This implies that ˆ𝑦𝑖 ∈ ∩ 𝑗;𝑋 𝑗 ∈N ( 𝑋𝑖) 𝑆 𝑗, which happen with probability これは、確率で起こる syi ∈ > j;X j ∈N ( Xi) S j であることを意味する。 0.82
With 𝑚 = #Y the number of element in Y. m = #Y の場合、Y の要素の数です。 0.81
We deduce that 私たちはそれを推測します 0.40
P(𝑆 𝑗) 𝑗;𝑋 𝑗 ∈N ( 𝑋𝑖) (∃𝑧 ≠ 𝑦𝑖, 𝑧 ∈ ∩ 𝑗 𝑆 𝑗) ≤ 𝑚 P𝑆 𝑗 (𝑧 ∈ 𝑆 𝑗) 𝑘 ≤ 𝑚𝜂𝑘 = 𝑚 exp(−𝑘 |log(𝜂)|). P(𝑆 𝑗) 𝑗;𝑋 𝑗 ∈N ( 𝑋𝑖) (∃𝑧 ≠ 𝑦𝑖, 𝑧 ∈ ∩ 𝑗 𝑆 𝑗) ≤ 𝑚 P𝑆 𝑗 (𝑧 ∈ 𝑆 𝑗) 𝑘 ≤ 𝑚𝜂𝑘 = 𝑚 exp(−𝑘 |log(𝜂)|). 0.93
P(𝑆𝑖)(cid:0)𝜑( ˆ𝑦𝑖) ≠ 𝜑(𝑦∗ 𝑛(𝑋) − 𝑔𝑛(𝑋)(cid:13)(cid:13)H P(Si)(cid:0)φ( yyi) φ(y, n(X) − gn(X)(cid:13)(cid:13 )H 0.94
𝑖 )(cid:12)(cid:12) (𝑋𝑖)(cid:1) ≤ 𝑚 exp(−𝑘 |log(𝜂)|). i )(cid:12)(cid:12) (Xi)(cid:1) ≤ m exp(−k |log()|)。 0.90
(cid:12)(cid:12) (𝑋𝑖) ∈ D(cid:3) ≤ 2𝑐𝜑𝑚 exp(−𝑘 |log(𝜂)|). (cid:12)(cid:12) (Xi) ∈ D(cid:3) ≤ 2cφm exp(−k |log(\)|)。 0.93
ED𝑛,𝑋(cid:2)(cid:13)(cid: 13)𝑔∗ EDn,X(cid:2)(cid:13) (cid:13)g∗ 0.78
𝑖=1 1𝑋𝑖∈N ( 𝑋) = 𝑘, we conclude that i=1 1Xi∈N ( X) = k である。 0.78
And because𝑛 16 そして、なぜなら、 16 0.65
Finally, adding everything together we get 最後に、すべてのものを追加します 0.62
E( 𝑓𝑛) ≤ 8𝑐𝜑𝑐𝜓 exp E( fn) ≤ 8cφc exp 0.85
−(𝑛 − 1) 𝑝 −(𝑛 − 1) 𝑝 0.85
+ 8𝑐𝜑𝑐𝜓𝑚 exp (−𝑘 |log(𝜂)|) . + 8cφc\m exp (−k |log(\)|) 。 0.87
(cid:16)− 𝑛𝑝 (cid:16)-np 0.84
8 (cid:17) + 8𝑐𝜑𝑐𝜓𝑛 exp 8 (cid:17) + 8cφcψn exp 0.72
(cid:18) (cid:19) (cid:18) (cid:19) 0.78
8 as long as 𝑘 < (𝑛 − 1) 𝑝/2, which implies Theorem 4 as long as 𝑛 ≥ 2. 8 は k < (n − 1) p/2 で、これは定理 4 が n ≥ 2 であることを意味する。 0.85
Remark 9 (Other approaches). remark 9 (他のアプローチ)。 0.69
While we have proceed with analysis based on local averaging methods, other paths could be explored to prove convergence results of the algorithm provided Eq. 局所平均化法に基づく解析を進めてきたが、Eqのアルゴリズムの収束結果を証明するために他の経路を探索することができた。 0.75
(4) and (5). (4)と(5)である。 0.72
For example, one could prove Wasserstein 𝑖 ), together with some continuity of the learning algorithm as a function of those 例えば、Wasserstein i ) をそれらの関数として学習アルゴリズムの連続性とともに証明することができる。 0.84
𝑖=1 𝛿(𝑥𝑖, ˆ𝑦𝑖) towards𝑛 i=1 δ(xi, syi) の向き 0.80
convergence of𝑛 𝑖=1 𝛿(𝑥𝑖, ˆ𝑦∗ エンの収束 𝑖=1 𝛿(𝑥𝑖, ˆ𝑦∗ 0.67
distributions.5 This analysis could be understood as tripartite: 分布.5 この分析は三部類と解釈できる。 0.62
• A disambiguation error, comparing ˆ𝑦𝑖 to 𝑦∗ 𝑖 . • yi を y∗ i と比較する曖昧な誤り。 0.69
• A stability / robustness measure of the algorithm to learn 𝑓𝑛 from data when substituting 𝑦∗ • A consistency result regarding 𝑓 ∗ • y∗ を置換するときデータから fn を学習するアルゴリズムの安定性/ロバスト性測度 • f ∗ に関する一貫性結果 0.91
𝑛 learnt on (𝑥𝑖, 𝑦∗ 𝑖 ). n は (xi, y∗ i ) で学習する。 0.71
Our analysis followed a similar path, yet with the first two parts tackled jointly. 我々の分析も同様の道をたどったが、最初の2部は共同で取り組んだ。 0.69
𝑖 by ˆ𝑦𝑖. A.4 Proof of Proposition 6 Under the non-ambiguity hypothesis (Assumption 2), the solution of Eq. 私はシイです。 A.4 提案の証明6 非曖昧性仮説(仮定2)の下で、Eqの解。 0.64
(3) is characterized pointwise by 𝑓 ∗(𝑥) = 𝑦𝑥 for all 𝑥 ∈ supp 𝜈X . (3) はすべての x ∈ supp νX に対して f ∗(x) = yx で特徴付けられる。 0.83
Similarly under Assumption 2, we have the characterization 𝑓 ∗(𝑥) ∈ ∩𝑆∈supp 𝜈|𝑥 𝑆. 同様に、仮定 2 の下では、特性 f ∗(x) ∈ s ∈supp ν|x s が成り立つ。 0.73
With the notation of Definition 5, since 𝑓 ∗(𝑥) minimizes 𝑧 → E𝑌∼𝜇𝑆 [ℓ(𝑧, 𝑌)] for all 𝑆 ∈ supp 𝜈|𝑥, it also minimizes 𝑧 → E𝑆∼𝜈|𝑥 For the second part of the proposition, we use the structured prediction framework of Ciliberto et al. 定義 5 の表記で f ∗(x) はすべての S ∈ supp ν|x に対して z → EY\μS [l(z, Y)] を最小化するので、命題の第2部では、Ciliberto et al の構造化予測フレームワークを使用する。 0.74
(2020). DeE𝑌∼𝜇𝑆 [𝛿𝑌], and 𝑓 ◦ : X → Y the solution 𝑓 ◦ ∈ fine the signed measure 𝜇◦ defined as 𝜇◦ that 𝑓 ◦ = 𝑓 ∗ under Assumption 2. (2020). DeEY μS [δY] と f × : X → Y の解 f × ∈ は μ として定義される符号付き測度 μ を分解する。 0.79
The framework of Ciliberto et al. ciliberto et alの枠組み。 0.59
(2020), tells us that 𝑓 ◦ is obtained after decoding, Eq. (2020) では、f は復号後に得られる、Eq である。 0.75
(9), of 𝑔◦ : X → H, and that if 𝑔◦ 𝑛 converges to 𝑓 ◦ in term of the 𝜇◦-risk. (9) の g は X → H で、g が f に収束すると μ とリスクの項で収束する。 0.73
Under Assumption 2 and mild hypothesis on 𝜇◦, it is possible to prove that convergence in term of the 𝜇◦-risk implies convergence in term of the 𝜇-risk (for example through calibration inequality similar to Proposition 2 of Cabannes et al. 仮定 2 と μ 上の穏やかな仮説の下では、μ-リスクの項の収束が μ-リスクの項の収束を意味することを証明できる(例えば、カバネスらの命題 2 に類似したキャリブレーションの不等式を通して)。 0.69
(2020)). arg min 𝑓 :X→Y E( 𝑋,𝑌)∼𝜇◦[ℓ( 𝑓 (𝑋), 𝑌)] = arg min 𝑓 :X→Y E( 𝑋,𝑌)∼𝜈(cid:2)E𝑌∼𝜇𝑆 [ℓ( 𝑓 (𝑋), 𝑌)](cid:3). (2020)). arg min f :X→Y E(X,Y) μ [l(f(X),Y)] = arg min f :X→Y E(X,Y) ν(cid:2)EY μS [l(f(X),Y)](cid:3) である。 0.86
The first part of the proposition tells us 提案の最初の部分は私たちに説明します 0.67
𝑛 converges to 𝑔◦ with the 𝐿1 norm, 𝑓 ◦ n は l1 のノルム f で g に収束する。 0.62
X := 𝜈X and 𝜇◦|𝑥 := E𝑆∼𝜈|𝑥 X :=νX と μ νx := ES ν|x 0.68
E𝑌∼𝜇𝑆 [ℓ(𝑧, 𝑌)]. EY\μS [l(z, Y)]。 0.70
A.5 Ranking with Partial ordering is a well behaved problem Here, we discuss about building directly 𝜉𝑆 to initialize our alternative minimization scheme or considering 𝜇𝑆 given by the definition of well-behaved problem (Definition 5). 部分順序付きa.5ランキングはよく振る舞う問題である。ここでは、代替の最小化スキームを初期化するために直接 s を構築するか、 well-behaved problem の定義で与えられた μ を考える(定義5)。
訳抜け防止モード: A.5 ranking with partial ordering is a well behaviord problem here. 直接Sを組み立てることについて 議論します 代替の最小化方式を初期化し あるいは well の定義によって与えられる μS を考える。
Since the existence of 𝜇𝑆 implying 𝜉𝑆 defined as E𝑌∼𝜇𝑆 [𝜑(𝑌)], we will only study when 𝜉𝑆 can be cast as a 𝜇𝑆. φ(Y)] として定義される μS を暗示する μS の存在を考えると、ある μS を μS としてキャストできる時期についてのみ研究する。
訳抜け防止モード: μS は EY μS [ φ(Y ) ] として定義される。 μS が μS としてキャストできるときのみ研究します。
In ranking, we have that 𝜓 = −𝜑, which corresponds to “correlation losses”. ランク付けでは、ψ = − φ であり、これは「相関損失」に対応する。 0.65
In this setting, we have that Span(𝜑(Y)) = Span(𝜓(Y)). この設定では、Span(φ(Y)) = Span(φ(Y)) が成立する。 0.70
More generally, looking at a “minimal” representation of ℓ, one can always assume the equality of those spans, as what happens on the orthogonal of the intersection of those spans, does not modify the scalar product 𝜑(𝑦)(cid:62)𝜓(𝑧). より一般的には、l の「最小」表現を考えると、それらのスパンの交点の直交で起こることがスカラー積 φ(y)(cid:62)(z) を変更しないので、常にそれらのスパンの等価性を仮定することができる。 0.68
Similarly, 𝜉𝑆 can be restricted to Span(𝜓(Y)), and therefore Span(𝜑(Y)), which exactly the image by 𝜇 → E𝑌∼𝜇[𝜑(𝑌)] of the set of signed measures, showing the existence of a 𝜇𝑆 matching Definition 5. 同様に、span(Y) と Span(φ(Y)) に制限することができるので、span(φ(Y)) は、符号付き測度集合の μ → EY*μ[φ(Y)] による像を正確に示し、定義 5 に一致する μS の存在を示す。 0.82
B IQP implementation for Eq. Eq の B IQP 実装。 0.65
(4) In this section, we introduce an IQP implementation to solve for Eq. (4) このセクションでは、Eq を解決する IQP 実装を紹介します。 0.75
(4). We first mention that our alternative minimization scheme is not restricted to well-behaved problem, before motivating the introduction of the IQP algorithm in two different ways, and finally describing its implementation. (4). 我々はまず,iqpアルゴリズムの導入を2つの方法で動機づける前に,我々の代替最小化スキームが十分に解決された問題に制限されないことを述べ,最終的にその実装を記述した。 0.76
Initialization of alternative minimization for non well-behaved problem 不利な問題に対する代替最小化の初期化 0.74
B.1 Before describing the IQP implementation to solve Eq. B.1 Eqを解決するIQP実装を記述する前に。 0.67
(12), we would like to stress that, even for non well-behaved partial labelling problems, it is possible to search for smart ways to initialize variables of the alternative minimization scheme. (12)我々は、不十分な部分ラベル問題であっても、代替最小化スキームの変数を初期化するためのスマートな方法を探すことが可能であることを強調する。 0.78
For 5The Wasserstein metric is useful to think in term of distributions, which is natural when considering partial supervision that can be cast as a set of admissible のために 5 ワッサースタイン計量は分布の観点で考えるのに有用であり、許容できる集合としてキャストできる部分的監督を考えると自然である。 0.62
fully supervised distributions. 完全に管理された分布です 0.45
This approach has been successfully followed by Perchet and Quincampoix (2015) to deal with partial monitoring in games. このアプローチはPerchet と Quincampoix (2015) によってゲームの部分的なモニタリングに成功している。 0.76
17 17 0.85
example, one could look at 𝑧(0) that this intersection is a singleton. 例えば、この交叉がシングルトンであるz(0)を見ることができる。 0.67
𝑖 ∈ ∩ 𝑗;𝑥 𝑗 ∈N𝑘𝑖 𝑖 ∈ , j;x j ∈Nki 0.88
𝑆 𝑗, where N𝑘 designs the 𝑘 nearest neighbors of 𝑥𝑖 in (𝑥 𝑗) 𝑗 ≤𝑛, and 𝑘𝑖 is chosen such s j, ここで nk は (x j) j ≤n における xi の k に近い近傍をデザインし、ki が選択される。
訳抜け防止モード: Sj, where Nk は (x j ) j ≤n の xi の k 近傍を設計する。 キは そんな風に選ばれて
B.2 Link with Diffrac and empirical risk minimization Our IQP algorithm is similar to an existing disambiguation algorithm known as the Diffrac algorithm (Bach and Harchaoui, 2007; Joulin et al., 2010).6 This algorithm was derived by implicitly following empirical risk minimization of Eq. b.2 link with diffrac and empirical risk minimization our iqp algorithm is similar to the existing disambiguation algorithm known the diffrac algorithm (bach and harchaoui, 2007; joulin et al., 2010).6 このアルゴリズムはeqの実証的リスク最小化に暗黙的に従うことによって導かれたものである。 0.84
(2). This approach leads to algorithms written as (2). このアプローチはアルゴリズムにつながります。 0.78
(𝑦𝑖) ∈ arg min (𝑦𝑖)∈𝐶𝑛 (yi) ∈ arg min (yi)∈Cn 0.93
inf 𝑓 ∈F ℓ( 𝑓 (𝑥𝑖), 𝑦𝑖) + 𝜆Ω( 𝑓), inf f ∈F ℓ( 𝑓 (𝑥𝑖), 𝑦𝑖) + 𝜆Ω( 𝑓), 0.87
𝑛∑︁ 𝑖=1 for F a space of functions, and Ω : F → R+ a measure of complexity. 𝑛∑︁ 𝑖=1 F は函数の空間であり、Ω : F → R+ は複雑性の尺度である。 0.67
Under some conditions, it is possible to simplify the dependency in 𝑓 (e.g., Xu et al., 2004; Bach and Harchaoui, 2007). ある条件下では f の依存性を単純化することが可能である(例: Xu et al., 2004; Bach and Harchaoui, 2007)。 0.85
For example, if ℓ(𝑦, 𝑧) can be written as (cid:107)𝜑(𝑦) − 𝜑(𝑧)(cid:107)2 for a mapping 𝜑 : X → Y, e.g. 例えば、写像 φ : X → Y に対して l(y, z) を (cid:107)φ(y) − φ(z)(cid:107)2) と書くことができる。 0.83
the Kendall loss detailed in Section 5.4,7 and the search of 𝜑( 𝑓) : X → 𝜑(Y) is relaxed as a 𝑔 : X → H. With Ω and F linked with kernel regression on the surrogate functional space X → H, it is possible to solve the 𝑗=1 𝛼 𝑗(𝑥𝑖)𝜑(𝑦𝑖), with 𝛼 given by kernel ridge regression (Ciliberto et al., 2016), ケンドールの損失は、第5.4,7節で詳述され、 φ(f) : x → φ(y) の探索は、g : x → h として緩和される。 ω と f は、超函数空間 x → h 上の核回帰と結び、核リッジ回帰によって α が与えられる j=1 α j(xi) φ(yi) を解くことができる(ciliberto et al., 2016)。 0.78
minimization with respect to 𝑔 as 𝑔(𝑥𝑖) =𝑛 g を g(xi) = n として最小化する 0.81
and to obtain a disambiguation algorithm written as 曖昧さのアルゴリズムを 入手するために 0.57
𝑛∑︁ 𝑖=1 (cid:13)(cid:13) 𝑛∑︁ 𝑛∑︁ 𝑖=1 (cid:13)(cid:13) 0.62
𝑗=1 𝛼 𝑗(𝑥𝑖)𝜑(𝑦 𝑗) − 𝜑(𝑦𝑖)(cid:13)(cid:13)2. 𝑗=1 α j(xi)φ(y j) − φ(yi)(cid:13)(cid:13) 2。 0.77
arg min 𝑦𝑖∈𝑆𝑖 アルグミン 𝑦𝑖∈𝑆𝑖 0.44
This IQP is a special case of the one we will detail. このIQPは、私たちが詳しく説明する特別なケースです。 0.73
As such, our IQP is a generalization of the Diffrac algorithm, and this paper provides, to our knowledge, the first consistency result for Diffrac. このように、我々のIQPはDiffracアルゴリズムの一般化であり、本論文は我々の知る限り、Diffracの最初の一貫性結果を提供する。 0.72
B.3 Link with an other determinism measure While we have considered the measure of determinism given by Eq. B.3 他の決定論尺度とリンクする Eq による決定論の尺度を検討した。 0.74
(2), we could have considered its quadratic variant (2)その二次変種を考えることは可能でしたが 0.65
𝜇★ ∈ arg min μ★ ∈ arg min 0.98
𝜇(cid:96)𝜈 μ(cid:96)ν 0.88
inf 𝑓 :X→Y inf f :X→Y 0.84
E𝑋∼𝜈X (cid:2)E𝑌 ,𝑌(cid:48)∼𝜇|𝑥 [ℓ(𝑌 , 𝑌 (cid:48))](cid:3) . エキシνX (cid:2)EY、Y(cid:48) μ|x [l(Y , Y(cid:48))](cid:3) 。 0.63
This correspond to the right drawing of Figure 4. これは図4の右図に相当します。 0.76
We could arguably translate it experimentally as 実験的に翻訳できます。 0.58
and still derive Theorem 4 when substituting Eq. Eq の代わりに Theorem 4 を導出します。 0.79
(4) by Eq. (4) Eqによる。 0.82
(14). When the loss is a correlation loss ℓ(𝑦, 𝑧) = −𝜑(𝑦)(cid:62)𝜑(𝑧). (14). 損失が相関損失 l(y, z) = −φ(y)(cid:62)φ(z) であるとき。 0.85
This leads to the quadratic problem これは二次問題に繋がる 0.61
( ˆ𝑦𝑖) ∈ arg min (𝑦𝑖)∈𝐶𝑛 (yi) ∈ arg min (yi)∈Cn 0.91
𝛼𝑖(𝑥 𝑗)ℓ(𝑦𝑖, 𝑦 𝑗), 𝛼𝑖(𝑥 𝑗)ℓ(𝑦𝑖, 𝑦 𝑗), 0.79
(14) ( ˆ𝑦𝑖) ∈ arg min (𝑦𝑖)∈𝐶𝑛 (14) (yi) ∈ arg min (yi)∈Cn 0.88
𝛼𝑖(𝑥 𝑗)𝜑(𝑦𝑖)(cid:62)𝜑(𝑦 𝑗). αi(x j)φ(yi)(cid:62)φ(y j)。 0.94
𝑛∑︁ − 𝑛∑︁ 𝑖, 𝑗=1 𝑛∑︁ − 𝑛∑︁ 𝑖, 𝑗=1 0.69
𝑖, 𝑗=1 IQP Implementation 𝑖, 𝑗=1 IQP の実装 0.79
B.4 In order to make our implementation possible for any symmetric loss ℓ : Y × Y → R, on a finite space Y, we introduce the following decomposition. B.4 任意の対称損失 l : Y × Y → R に対して実装を可能にするために、有限空間 Y 上で、次の分解を導入する。 0.83
Proposition 10 (Quadratic decomposition). Proposition 10 (Quadratic decomposition) の略。 0.74
When Y is finite, any proper symmetric loss ℓ admits a decomposition with two mappings 𝜑 : Y → R𝑚, 𝜓 : Y → R𝑚, for a 𝑚 ∈ N and a 𝑐 ∈ R, reading Y が有限であるとき、任意の適切な対称損失 l は、m ∈ N と c ∈ R に対して 2 つの写像 φ : Y → Rm, y : Y → Rm を持つ分解を認め、読み取る。 0.84
constraint set 𝐶𝑛 = 𝑆𝑖 by a set of the type 𝐶𝑛 = arg max(𝑦𝑖)∈Y 𝑛𝑛 Cn = arg max(yi)∈Y n*n 型の集合による制約集合 Cn = → Si 0.81
(15) 6The Diffrac algorithm was first introduced for clustering, which is a classical approach to unsupervised learning. (15) 6 diffracアルゴリズムは、教師なし学習に対する古典的なアプローチであるクラスタリングのために初めて導入された。 0.69
In practice, it consists to change the 𝑖, 𝑗=1 1𝑦𝑖 ≠𝑦 𝑗 in Eqs. 実際には、それは Eqs の i, j=1 1yi,y j を変更する。 0.78
(4) and (14), meaning that (𝑦𝑖) should be disambiguated into different (4)及び(14)とは、(yi)を別々に区別すべきという意味である 0.75
with ℓ(𝑦, 𝑧) = 𝜓(𝑦)(cid:62)𝜓(𝑧) − 𝜑(𝑦)(cid:62)𝜑(𝑧) と l(y, z) = ψ(y)(cid:62)ψ(z) − φ(y)(cid:62) φ(z) 0.78
(cid:107)𝜑(𝑦)(cid:107) = (cid:107)𝜓(𝑦)(cid:107) = 𝑐 (cid:107)φ(y)(cid:107) = (cid:107)(y)(cid:107 ) = c 0.90
∀ 𝑦, 𝑧 ∈ Y, y, z ∈ y である。 0.61
classes. 7Since (cid:107)𝜑(𝑦) (cid:107) is constant. クラス。 7Since (cid:107)φ(y) (cid:107) は定数である。 0.70
18 18 0.85
We build the decomposition 私たちは分解を構築します 0.55
orthonormal basis of R𝑚, and 𝜆𝑖 ∈ R its eigen values. Rm と λi ∈ R の正則基底は固有値である。 0.76
We have, with (𝑒𝑖) the Cartesian basis of R𝑚, 我々は(ei) rm のデカルト基底を持つ。 0.46
Proof. Consider Y = 𝑦1, ·, 𝑦𝑚 and 𝐿 = (ℓ(𝑦𝑖, 𝑦 𝑗))𝑖, 𝑗 ≤𝑚 ∈ R𝑚×𝑚. 証明。 Y = y1, ·, ym および L = (l(yi, y j))i, j ≤m ∈ Rm×m を考える。 0.75
𝐿 is a symmetric matrix, diagonalizable as 𝐿 =𝑚 (𝜆𝑖)−(cid:10)𝑒 𝑗 , 𝑢𝑖(cid:11) (cid:104)𝑒𝑘 , 𝑢𝑖(cid:105) . L は対称行列で、L = (λi)−(cid:10)e j , ui(cid:11) (cid:104)ek , ui(cid:105) として対角化できる。 0.73
(cid:16)√︁(𝜆𝑖)− (cid:104)𝑒𝑘 , 𝑢𝑖(cid:105)(cid:17) √︃ 𝐶 −(cid:13)(cid:13) ˜𝜓(𝑦)(cid:13)(cid:13)2𝑒𝑖 . (cid:16)(λi)− (cid:104)ek , ui(cid:105)(cid:17) > C −(cid:13)(cid:13)(cid :13)(cid:13)2ei である。 0.82
And consider 𝜑 =(cid:0) ˜𝜑 φ =(cid:0) φ を考える。 0.75
ℓ(𝑦 𝑗 , 𝑦𝑘) = 𝐿 𝑗 𝑘 =(cid:10)𝑒 𝑗 , 𝐿𝑒𝑘(cid:11) = (cid:16)√︁(𝜆𝑖)+ (cid:104)𝑒𝑘 , 𝑢𝑖(cid:105)(cid:17) 𝑖=1(𝜆𝑖)+ (cid:104)𝑢𝑖, 𝑒𝑘(cid:105)2 ≤ 𝐶𝑚 l(y j , yk) = L j k =(cid:10)e j , Lek(cid:11) = (cid:16)\(λi)+ (cid:104)ek , ui(cid:105)(cid:17) i=1(λi)+ (cid:104)ui, ek(cid:105)2 ≤ C m 0.89
𝐶 = max𝑖 |𝜆𝑖|, we have(cid:13)(cid:13) ˜𝜓(𝑦𝑘)(cid:13)(cid:13)2 =𝑚 C = maxi |λi|, we has(cid:13)(cid:13) , (yk)(cid:13)(cid:13) 2 = ym 0.81
It satisfies ℓ(𝑦 𝑗 , 𝑦𝑘) = ˜𝜓(𝑦)(cid:62) ˜𝜓(𝑧) − ˜𝜑(𝑦)(cid:62) ˜𝜑(𝑧). l(y j , yk) = s(y)(cid:62) s(z) − sφ(y)(cid:62) sφ(z) を満たす。 0.85
We only need to show that we can consider 𝜑 of constant norm. 定数ノルムのφを考えることができることだけを示す必要があります。 0.59
For this, first consider 𝑖=1 (cid:104)𝑢𝑖, 𝑒𝑘(cid:105)2 = 𝐶 (cid:107)𝑒𝑘(cid:107)2 = 𝐶 The last equalities being due to the fact that このためには、まず i=1 (cid:104)ui, ek(cid:105)2 = C (cid:107)ek(cid:107) 2 = C を考える。 0.89
(𝑢𝑖) is orthonormal. (ui)は正則である。 0.61
Now, introduce the correction vector 𝜉 : Y → R𝑚, 𝜉(𝑦𝑖) = construction, 𝜓 is of constant norm being equal to 𝐶 and that ℓ(𝑦, 𝑧) = 𝜓(𝑦)𝑇 𝜓(𝑧) − 𝜑(𝑦)𝑇 𝜑(𝑧). ここで、補正ベクトル t : Y → Rm, s(yi) = construction, s は C に等しい定数ノルムであり、l(y, z) = s(y)T s(z) − φ(y)T φ(z) である。
訳抜け防止モード: ここでは、補正ベクトル t : Y → Rm を導入する。 は(yi ) = 構築。 C に等しくなる定数ノルムである and that ℓ(𝑦, 𝑧 ) = 𝜓(𝑦)𝑇 𝜓(𝑧 ) − 𝜑(𝑦)𝑇 𝜑(𝑧 ) .
Finally, because ℓ(𝑦, 𝑧) = 0, we also have 𝜑 (cid:3) of constant norm. 最後に、 l(y, z) = 0 であるため、定数ノルムの φ (cid:3) も持つ。 0.77
(cid:1), 𝜓 =(cid:0) ˜𝜓 (cid:1), > =(cid:0) > 0.81
(𝜆𝑖)+(cid:10)𝑒 𝑗 , 𝑢𝑖(cid:11) (cid:104)𝑒𝑘 , 𝑢𝑖(cid:105) − 𝑚∑︁ (λi)+(cid:10)e j , ui(cid:11) (cid:104)ek , ui(cid:105) − m* 0.80
𝑖=1 𝜆𝑖𝑢𝑖 ⊗ 𝑢𝑖, with (𝑢𝑖) a i=1 λiui > ui, with (ui) a 0.85
(cid:1). By (cid:1)。 ところで 0.67
˜𝜓(𝑦𝑘) = ˜𝜑(𝑦𝑘) = ˜𝜓(𝑦𝑘) = ˜𝜑(𝑦𝑘) = 0.85
𝑚∑︁ 𝑖=1 , 𝑖≤𝑚 𝑚∑︁ 𝑖=1 , 𝑖≤𝑚 0.65
. 𝑖≤𝑚 and 𝑖=1 . 𝑖≤𝑚 そして 𝑖=1 0.69
𝜉 𝜉 Using the decomposition Eq. 𝜉 𝜉 分解 Eq を使用する。 0.82
(15), Eq. (14) reads, with y = (𝑦𝑖) (15),Eq。 (14) y = (yi) で読みます。 0.73
𝑛∑︁ 𝑖=1 𝛼𝑖(𝑥 𝑗)𝜓(𝑦𝑖)𝜓(𝑦 𝑗) − 𝑛∑︁ Tr(cid:0)𝐴Ψ(y)Ψ(y)(cid:62)(cid:1) − Tr(cid:0)𝐴Φ(y)Φ(y)(cid:62)(cid:1) . 𝑛∑︁ 𝑖=1 αi(x j)ψ(yi)ψ(y j) − n tr(cid:0)aψ(y)ψ(y)(cid:62)(cid:1) − tr(cid:0)aφ(y) φ(y)(cid:62)(cid:1) である。 0.66
𝑖=1 𝛼𝑖(𝑥 𝑗)𝜑(𝑦𝑖)𝜑(𝑦 𝑗). 𝑖=1 𝛼𝑖(𝑥 𝑗)𝜑(𝑦𝑖)𝜑(𝑦 𝑗). 0.72
ˆy ∈ arg min y∈𝐶𝑛 y ∈ arg min y∈Cn 0.84
ˆy ∈ arg min y∈𝐶𝑛 y ∈ arg min y∈Cn 0.84
By defining the matrix 𝐴 = (𝛼𝑖(𝑥 𝑗))𝑖 𝑗 ≤𝑛 ∈ R𝑛×𝑛, Ψ(y) = (𝜓(𝑦𝑖))𝑖≤𝑛 ∈ R𝑛×𝑚 and Φ(y) = (𝜑(𝑦𝑖))𝑖≤𝑛 ∈ R𝑛×𝑚, we cast it as 行列 A = (αi(x j))i j ≤n ∈ Rn×n, >(y) = (\(yi))i≤n ∈ Rn×m, >(y) = (φ(yi))i≤n ∈ Rn×m を定義することにより、我々はそれを Rn×m としてキャストする。 0.88
Objective convexification. As 𝛼𝑖(𝑥 𝑗) is a measure of similarity between 𝑥𝑖 and 𝑥 𝑗, 𝐴 is usually symmetric positive definite, making this objective convex in Ψ and concave in Φ. 目的の凝縮。 αi(x j) は xi と x j の類似性の尺度であるため、a は通常対称正定値であり、この対象凸を ψ で、凸を φ で表す。 0.68
However, recalling Eq. しかし、Eqを思い出す。 0.75
(15), we have Tr ΦΦ(cid:62) = Tr ΨΨ(cid:62) = 𝑛𝑐, therefore considering the spectral norm of 𝐴, we convexify the objective as (15) は Tr >(cid:62) = Tr >(cid:62) = nc であるため、A のスペクトルノルムを考えると、目的を凸化する。 0.78
ˆy ∈ arg min y∈𝐶𝑛 y ∈ arg min y∈Cn 0.84
Considering allow to simplify this objective as 考える この目的を単純化し 0.59
𝐵 = Tr(cid:0)((cid:107) 𝐴(cid:107)∗ 𝐼 + 𝐴)Ψ(y)Ψ(y)(cid:62)(cid:1) + Tr(cid:0)((cid:107) 𝐴(cid:107)∗ 𝐼 − 𝐴)Φ(y)Φ(y)(cid:62)(cid:1) . 𝐵 = Tr(cid:0)((cid:107)) A(cid:107)∗ I + A)シュ(y)(cid:62)(cid:1) + Tr(cid:0)((cid:107)A (cid:107)∗ I − A)シュ(y)(cid:62)(cid:1)。 0.88
(cid:18) (cid:107) 𝐴(cid:107)∗ 𝐼 + 𝐴 (cid:18) (cid:107) A(cid:107)∗ I + A 0.88
(cid:18)Ψ(y) (cid:18)ψ(y) 0.94
(cid:19) 0 (cid:19) 0 0.82
and Ξ(y) = 0 と は(y) = 0 0.79
(cid:107) 𝐴(cid:107)∗ 𝐼 − 𝐴 (cid:107)A(cid:107)∗ I − A 0.94
Φ(y) , (cid:19) Tr(cid:0)𝐵Ξ(y)Ξ(y)(cid:62)(cid:1) . ~(y) , (cid:19) Tr(cid:0)By(y)(cid:6 2)(cid:1) 。 0.81
ˆy ∈ arg min y∈𝐶𝑛 y ∈ arg min y∈Cn 0.84
When parametrized by 𝜉 = Ξ(y), this is an optimization problem with a convex quadratic objective and “integer-like” constraint 𝜉 ∈ Ξ(𝐶𝑛), identifying to an integer quadratic program (IQP). これは凸二次目的(convex quadratic objective)と "integer-like"(integer-like)制約を持つ最適化問題であり、整数二次計画 (IQP) と同一視される。 0.63
Relaxation. IQP are known to be NP-hard, several tools exists in literature and optimization library implementing them. リラックス。 IQPはNPハードであることが知られており、文献や最適化ライブラリにいくつかのツールが存在する。 0.62
The most classical approach consists in relaxing the integer constraint 𝜉 ∈ Ξ(𝐶𝑛) into the convex constraint 𝜉 ∈ Conv(Ξ(𝐶𝑛)), solving the resulting convex quadratic program, and projecting back the solution towards an extreme of the convex set. 最も古典的なアプローチは、整数の制約(英語版)(integeral constraints)を凸(convex)の制約(英語版)(convex)に緩和し、結果として得られる凸二次プログラムを解き、凸集合の極端に向かって解を投影する。 0.73
Arguably, our alternative minimization approach is a better grounded heuristic to solve our specific disambiguation problem. おそらく、我々の代替の最小化アプローチは、特定の曖昧さ問題を解決するためのより基礎的なヒューリスティックである。 0.52
C Example with graphical illustrations To ease the understanding of the disambiguation principle (2), we provide a toy example with a graphical illustration, Figure 4. C 図形図形の例 曖昧さの原則を理解するのを容易にするために、図形図形を使ったおもちゃの例を図 4 に示します。
訳抜け防止モード: 図形図形を用いたC例 曖昧さの原則(2)の理解を容易にする。 グラフィカルなイラストレーションを備えたおもちゃの例を図4に示します。
Since Eq. (2) decorrelates inputs, we will consider X to be a singleton, in order to remove the dependency to X . Eq以降。 (2) 入力を非相関化するため、x への依存性を取り除くために、x をシングルトンとみなす。 0.67
In the following, we consider Y = {𝑎, 𝑏, 𝑐}, with the loss given by 以下では、Y = {a, b, c} を考える。
訳抜け防止モード: 以下では、Y = { a, b, を考える。 c } , によって与えられる損失と。
𝐿 = (ℓ(𝑦, 𝑧))𝑦,𝑧∈Y =(cid:169)(cid:173)(c id:171) 0 L = (l(y, z))y,z∈Y =(cid:169)(cid:173)(c id:171) 0 0.89
1 1 1 0 2 1 2 0 1 1 1 0 2 1 2 0 0.85
(cid:170)(cid:174)(c id:172) . (cid:170)(cid:174)(c id:172)。 0.70
19 19 0.85
This problem can be represented on a triangle through the embedding of probability measures reading 𝜉 : ΔY → R3; 𝜇 → この問題は ΔY → R3; μ → と読む確率測度の埋め込みを通して三角形上で表すことができる。 0.78
𝜇(𝑎)𝑒1 + 𝜇(𝑏)𝑒2 + 𝜇(𝑐)𝑒3, and onto the triangle(cid:8)𝑧 ∈ R3+(cid:12)(cid:12) 𝑧(cid:62)1 = 1(cid:9). μ(a)e1 + μ(b)e2 + μ(c)e3, そして三角形(cid:8)z ∈ R3+(cid:12)(cid:12) z(cid:62)1 = 1(cid:9)。 0.88
Note that 𝜉 can be extended from any signed measure of total mass normalized to one onto the plane(cid:8)𝑧 ∈ R3(cid:12)(cid:12) 𝑧(cid:62)1 = 1(cid:9), as well as the drawings Figure 4 can be extended onto the affine R3 → R; 𝑧 → 𝑧(cid:62)𝐿𝑧 to the definition domain(cid:8)𝑧 ∈ R3(cid:12)(cid:12) 𝑧(cid:62)1 = 1(cid:9) is concave, as suggested by the right drawing of Figure 4. 図4はアフィン R3 → R; z → z(cid:62)Lz から定義領域 (cid:8)z ∈ R3(cid:12)(cid:12) z(cid:62)1 = 1(cid:9) へと拡張することができる。
訳抜け防止モード: なお、全質量正規化の符号付き測度から平面(cid:8)z ∈ r3(cid:12)(cid:12)z( cid:62)1 = 1(cid:9)に拡張できる。 図4はアフィン r3 → r ; z → z(cid:62)lz から定義領域(cid:8)z ∈ r3(cid:12)(cid:12 ) z(cid:62)1 = 1(cid:9 ) への拡張が可能である。 図4の右図に示すように。
span of the represented triangles. 代表される三角形の幅です 0.67
The objective (2) reads pointwise as ΔY → R; 𝜇 → min𝑖≤3 𝑒(cid:62) 𝑖 𝐿𝜉(𝜇), while its quadratic version reads ΔY → Y; 𝜇 → 𝜉(𝜇)(cid:62)𝐿𝜉(𝜇). 目的 (2) は ΔY → R; μ → mini≤3 e(cid:62) i L'(μ) と読み、その二次版は ΔY → Y; μ → >(μ)(cid:62)L'(μ) と読む。 0.88
Note that while 𝐿 is not definite negative, one can check that the restriction of L は確定的な負ではないが、その制限がチェックできることに注意してください。 0.59
b 𝑅𝑏 𝑅𝑎 𝑅𝑐 b 𝑅𝑏 𝑅𝑎 𝑅𝑐 0.85
b 𝑅𝜈 b b a b 𝑅𝜈 b b あ... 0.71
c a c a c あ... c あ... 0.51
c a c Figure 4: Exposition of a pointwise problem in the simplex ΔY, with Y = {𝑎, 𝑏, 𝑐} and a proper symmetric loss defined by c あ... c 図4: Y = {a, b, c} と定義される適切な対称損失を持つ単純体 ΔY における点方向問題の存在。 0.68
ℓ(𝑎, 𝑏) = ℓ(𝑎, 𝑐) = ℓ(𝑏, 𝑐)/2. ℓ(𝑎, 𝑏) = ℓ(𝑎, 𝑐) = ℓ(𝑏, 𝑐)/2. 0.89
(Left) Representation of the decision regions 𝑅𝑧 =(cid:8)𝜇 ∈ ΔY(cid:12)(cid:12) 𝑧 ∈ arg min𝑧(cid:48)∈Y E𝑌∼𝜇[ℓ(𝑧, 𝑦)](cid:9) . (Left) 決定領域 Rz =(cid:8)μ ∈ ΔY(cid:12)(cid:12)z ∈ arg minz(cid:48)∈Y EY μ[l(z, y)](cid:9) の表現。 0.85
for 𝑧 ∈ Y. z ∈ Y に対して。 0.77
(Middle Left) Representation of 𝑅𝜈 =(cid:8)𝜇 ∈ ΔY(cid:12)(cid:12) 𝜇 (cid:96) 𝜈(cid:9) for 𝜈 = (5𝛿{𝑎,𝑏,𝑐} + 𝛿{𝑐} + 𝛿{𝑎,𝑐} + 𝛿{𝑏,𝑐})/8 (Middle Right) Level curves of (左) rν = (cid:8)μ ∈ δy(cid:12)(cid:12) μ (cid:96) ν(cid:9) for ν = (5δ{a,b,c} + δ{c} + δ{a,c} + δ{b,c})/8 (中右) レベル曲線の表現 0.91
the piecewise function ΔY → R; 𝜇 → min𝑧∈Y E𝑌∼𝜇[ℓ(𝑧, 𝑌)] corresponding to Eq. Eq に対応する部分関数 ΔY → R; μ → minz∈Y EY*μ[l(z, Y)]。 0.88
(2). (Right) Level curves of the quadratic function ΔY → R; 𝜇 → E𝑌 ,𝑌(cid:48)∼𝜇[ℓ(𝑌 , 𝑌(cid:48))]. (2). (右) 二次函数 ΔY → R; μ → EY , Y(cid:48) =μ[l(Y , Y(cid:48))] のレベル曲線。 0.84
Our disambiguation (2) corresponds to minimizing the concave function represented on the middle right drawing on the convex domain represented on the middle left drawing. 私たちの曖昧さ(2)は、中央左図で表される凸領域の中央右図で表される凹関数の最小化に相当します。 0.74
It should be noted that (ℓ, 𝜈) being a well-behaved partial labelling problem can be understood graphically, as having the intersection of the decision regions ∩𝑧∈𝑆 𝑅𝑧 non-empty for any set 𝑆 in the support of 𝜈. また、(l, ν) は、(l, ν) が ν の支持において任意の集合 s に対して空でない決定領域の交わりを持つものとして、図式的に理解可能であることに注意する必要がある。
訳抜け防止モード: 注意すべきなのは ( l, ν ) うまく振る舞う部分的ラベリング問題である 任意の集合 s に対して ν のサポートが空であるような、決定領域の交わりを持つものとして、図式的に理解することができる。
As such, it is easy to see that our toy problem is well-behaved for any distribution 𝜈. したがって、我々のおもちゃ問題は任意の分布 ν に対してよく理解されていることが容易にわかる。 0.62
Formally, to match Definition 5, we can define 𝜇{𝑒} = 𝛿𝑒 for 𝑒 ∈ {𝑎, 𝑏, 𝑐} and 正式には、定義5に一致するように、e ∈ {a, b, c} に対して μ{e} = δe を定義できる。 0.81
𝜇{𝑎,𝑏} = .5𝛿𝑎 + .5𝛿𝑏, 𝜇{𝑎,𝑏} = .5𝛿𝑎 + .5𝛿𝑏, 0.88
𝜇{𝑎,𝑐} = .5𝛿𝑏 + .5𝛿𝑐, 𝜇{𝑎,𝑐} = .5𝛿𝑏 + .5𝛿𝑐, 0.88
𝜇{𝑏,𝑐} = 𝛿𝑏 + 𝛿𝑐 − 𝛿𝑎, 𝜇{𝑏,𝑐} = 𝛿𝑏 + 𝛿𝑐 − 𝛿𝑎, 0.85
𝜇{𝑎,𝑏,𝑐} = .5𝛿𝑏 + .5𝛿𝑐. 𝜇{𝑎,𝑏,𝑐} = .5𝛿𝑏 + .5𝛿𝑐. 0.92
Graphically 𝜉(𝜇{𝑎,𝑏}) can be chosen as any points on the horizontal dashed line on the middle right drawing of Figure 4 (similarly for 𝜉 𝜇{𝑎,𝑐}), while 𝜉(𝜇{𝑎,𝑏,𝑐}) has to be chosen has the intersection .5𝑒2 + .5𝑒3, and while 𝜉(𝜇{𝑏,𝑐}) has to be chosen outside the simplex on the half-line leaving .5𝑒2 + .5𝑒3 supported by the perpendicular bisector of [𝑒2, 𝑒3] and not containing 𝑒1. 図4の中央右図の水平線上の任意の点(μ{a,b})が選択可能であり(同様に μ{a,c} の略)、 μ{a,b,c} は .5e2 + .5e3 の交点を持つように選択され、 μ{b,c} は .5e2 + .5e3 の垂直二元線によって支持され、e1 を含まない半線上の単純集合の外側から選択されなければならない。 0.82
D Experiments While our results are much more theoretical than experimental, out of principle, as well as for reproducibility, comparison and usage sake, we detail our experiments. D実験の結果は実験よりも理論的ですが、再現性、比較性、使用方法については原則外ですが、実験について詳しく説明します。 0.75
Interval regression - Figure 1 インターバル回帰 - 図1。 0.70
D.1 Figure 1 corresponds to the regression setup consisting of learning 𝑓 ∗ : [0, 1] → R; 𝑥 → sin(𝜔𝑥), with 𝜔 = 10 ≈ 3𝜋. D.1図1は、学習 f ∗ : [0, 1] → R; x → sin(ωx) と ω = 10 > 3π からなる回帰集合に対応する。 0.85
The dataset represented on Figure 1 is collected in the following way. 図1に示すデータセットは、以下の方法で収集される。 0.83
We sample (𝑥𝑖)𝑖≤𝑛 with 𝑛 = 10, uniformly at random on X = [0, 1], after fixing a random seed for reproducibility. 再現性のためにランダムシードを固定した後、X = [0, 1] 上でランダムにn = 10で(xi)i≤nをサンプリングする。 0.82
We collect 𝑦𝑖 = 𝑓 (𝑥𝑖). yi = f (xi) を集めます。 0.74
We create (𝑠𝑖) by sampling 𝑢𝑖 uniformly on [0, 1], defining 𝑟𝑖 = 𝑟 − 𝛾 log(𝑢𝑖), with 𝑟 = 1 and 𝛾 = 3−1, sampling 𝑐𝑖 uniformly at random on [0, 𝑟𝑖], and defining 𝑠𝑖 = 𝑦𝑖 + sign(𝑦𝑖) · 𝑐𝑖 + [−𝑟𝑖, 𝑟𝑖]. 0, 1] 上で ui を均一にサンプリングし、r = 1 と γ = 3−1 で ri = r − γ log(ui) を定義し、[0, ri] 上でランダムに ci をサンプリングし、si = yi + sign(yi) · ci + [−ri, ri] を定義することで (si) を作成する。 0.89
The corruption is skewed on purpose to showcase disambiguation instability of the baseline (13) compared to our method. 腐敗は,本手法と比較してベースライン(13)の曖昧さの不安定さを示す目的で歪められた。 0.62
We solve Eq. (4) with alternative minimization, initialized by taking 𝑦(0) at the center of 𝑠𝑖, and | < 𝜀 for 𝜀 a stopping criterion fixed to 10−6. eqを解決します (4) si の中心に y(0) を、ε に対して | < ε を 10−6 に固定して初期化する別の最小化を伴う。 0.72
For 𝑥 ∈ X , the inference Eqs. x ∈ X の場合、推論 Eqs である。 0.86
(5) and (13) is done through grid search, considering, for 𝑓𝑛(𝑥), 1000 guesses dividing uniformly [−6, 6] ⊂ Y = R. We consider weights 𝛼 given by kernel ridge regression with Gaussian kernel, defined as (5) と (13) はグリッド探索によって行われるが、fn(x) の場合、[−6,6] と y = r で一様に割った1000の推測を考えると、重み α はガウス核を持つ核リッジ回帰によって与えられる。 0.74
stopping the minimization scheme when𝑖≤𝑛 |𝑦(𝑡+1) i≤n |y(t+1) が最小化スキームを停止する 0.58
− 𝑦(𝑡) 𝑖 𝑖 − 𝑦(𝑡) 𝑖 𝑖 0.85
𝑖 𝛼(𝑥) = (𝐾 + 𝑛𝜆𝐼)−1𝐾𝑥 ∈ R𝑛, 𝐾 = (𝑘(𝑥𝑖, 𝑥 𝑗))𝑖, 𝑗 ≤𝑛 ∈ R𝑛×𝑛, 𝐾𝑥 = (𝑘(𝑥𝑖, 𝑥))𝑖≤𝑛 ∈ R𝑛, 𝑖 𝛼(𝑥) = (𝐾 + 𝑛𝜆𝐼)−1𝐾𝑥 ∈ R𝑛, 𝐾 = (𝑘(𝑥𝑖, 𝑥 𝑗))𝑖, 𝑗 ≤𝑛 ∈ R𝑛×𝑛, 𝐾𝑥 = (𝑘(𝑥𝑖, 𝑥))𝑖≤𝑛 ∈ R𝑛, 0.91
𝑘(𝑥, 𝑥(cid:48)) = exp k(x, x(cid:48)) = exp 0.99
20 (cid:18) 20 (cid:18) 0.82
−(cid:107)𝑥 − 𝑥(cid:48)(cid:107)2 2𝜎2 −(cid:107)x − x(cid:48)(cid:107)2 2σ2 0.78
(cid:19) , (cid:19) , 0.82
with 𝜆 a regularization parameter, and 𝜎 a standard deviation parameter. λ は正規化パラメータであり、σ は標準偏差パラメータである。 0.82
In our simulation, we fix 𝜎 = .1 based on simple considerations on the data, while we consider 𝜆 ∈ [10−1, 10−3, 10−6]. シミュレーションでは、データに関する単純な考察に基づいてσ = .1 を修正し、λ ∈ [10−1, 10−3, 10−6] を考える。 0.77
The evaluation of the mean square error between 𝑓𝑛 and 𝑓 ∗, which is equivalent to evaluating the risk with the regression loss ℓ(𝑦, 𝑧) = (cid:107)𝑦 − 𝑧(cid:107)2, is done by considering 200 points dividing uniformly X = [0, 1] and evaluating 𝑓𝑛 and 𝑓 ∗ on it. 回帰損失 l(y, z) = (cid:107)y − z(cid:107)2 でリスクを評価することと同等である fn と f s の間の平均二乗誤差の評価は、X = [0, 1] を均一に分割する 200 点を考慮に入れて fn と f s を評価することによって行われる。 0.86
The best hyperparameter 𝜆 is chosen by minimizing this error. 最良のハイパーパラメータλは、この誤差を最小化することで選択される。 0.62
It leads to 𝜆 = 10−1 for the baseline (13), and 𝜆 = 10−6 for our algorithm (4) and (5). これは基底線 (13) に対して λ = 10−1 となり、アルゴリズム (4) と (5) に対して λ = 10−6 となる。 0.82
This difference in 𝜆 is normal since both methods are not estimating the same surrogate quantities. どちらの方法も同じサーロゲート量を見積もっていないため、λのこの差は正常である。 0.61
The fact that 𝜆 is smaller for our algorithm is natural as our disambiguation objective (4) already has a regularization effect on the solution.8 Note that we used the same weights 𝛼 for Eq. λ が我々のアルゴリズムでより小さいという事実は、我々の曖昧さ目標 (4) が既に解に対する正規化効果を持っているため自然である。 0.64
(4) and Eq. (5), which is suboptimal, but fair to the baseline, as, consequently, both methods have the same number of hyperparameters. (4)およびEq。 (5) は準最適であるが、ベースラインに公平であり、その結果、両方のメソッドは同じ数のハイパーパラメータを持つ。 0.77
D.2 Classification - Figure 2 Figure 2 corresponds to classification problems, based on real dataset from the LIBSVM datasets repository. D.2 分類 - 図2 図2は LIBSVM データセットリポジトリの実際のデータセットに基づいた分類問題に対応します。 0.81
At the time of writing, the datasets are available at https://www.csie.ntu .edu.tw/~cjlin/libsv mtools/datasets/mult iclass.html. データセットはhttps://www.csie.ntu .edu.tw/~cjlin/libsv mtools/datasets/mult iclass.htmlで入手できる。 0.47
We present results on the “Dna” and “Svmguide2” datasets, that both have 3 classes (𝑚 = 3), and respectively have 4000 samples with 180 features (𝑛 = 4000,𝑑 = 180) and 391 samples with 20 features (𝑛 = 391, 𝑑 = 20). dna” と “svmguide2” データセットでは,それぞれ3つのクラス (m = 3) を持ち,それぞれ 180 個の特徴を持つ 4000 個のサンプル (n = 4000,d = 180) と 20 個の特徴を持つ 391 個のサンプル (n = 391,d = 20) がある。 0.87
In term of complexity, when Y = (cid:200)1, 𝑚(cid:201) = {1, 2, · · · , 𝑚}, and weights based on kernel ridge regression with Gaussian kernel as described in the last paragraph the complexity of performing inference for Eqs. 複雑性の観点では、Y = (cid:200)1, m(cid:201) = {1, 2, · · · · · , m} と、前段落で述べたように、ガウス核によるカーネルリッジ回帰に基づく重みは、Eqsに対する推論を実行する複雑さである。 0.74
(5) and (13) can be done in 𝑂(𝑛𝑚) in time and 𝑂(𝑛 + 𝑚) in space, where 𝑛 is the number of training samples (Nowak-Vila et al., 2019; Cabannes et al., 2020). (5) と (13) は時間内の o(nm) と空間での o(n + m) で行われ、そこで n はトレーニングサンプルの数である(nowak-vila et al., 2019; cabannes et al., 2020)。 0.83
The disambiguation (4) performed with alternative minimization is done in 𝑂(𝑐𝑛2𝑚) in time and in 𝑂(𝑛(𝑛 + 𝑚)) in space, with 𝑐 the number of steps in the alternative minimization scheme. 代替最小化で実行される曖昧さ (4) は、時間において O(cn2m) と空間において O(n(n + m)) で行われ、c は代替最小化スキームのステップ数である。 0.80
In practice, 𝑐 is really small, which can be understood since we are minimizing a concave function and each step leads to a guess on the border of the constraint domain. 実際には、c は本当に小さく、concave 関数を最小化しており、各ステップは制約領域の境界で推測されるので理解できます。 0.71
Based on the dataset (𝑥𝑖, 𝑦𝑖), we create (𝑠𝑖) by sampling it accordingly to 𝛾𝛿{𝑦𝑖 } + 1 − 𝛾𝛿{𝑦,𝑦𝑖 }, with 𝑦 the most present labels in the dataset (indeed we choose the two datasets because they were not too big and presenting unequal labels proportion), and 𝛾 ∈ [0, 1] the corruption parameter represented in percentage on the 𝑥-axis of Figure 2. データセット (xi, yi) に基づいて, γδ{yi } + 1 − γδ{y,yi } にそれに応じてサンプリングすることによって (si) を生成する。y はデータセットで最も存在するラベルである (図2の x 軸のパーセンテージで表される汚職パラメータは, 2 つのデータセットが大きすぎず,不等ラベルの割合を示すために選択されている)。 0.78
This skewed corruption allows to distinguish methods and invalidate the simple approach consisting to averaging candidate (AC) in set to recover 𝑦𝑖 from 𝑠𝑖, which works well when data are missing at random (Heitjan and Rubin, 1991). この歪んだ汚職は、データをランダムに欠いているときにうまく機能するsiからyiを回収するために、平均的候補(AC)からなる単純なアプローチを区別し、無効化することができる(Heitjan and Rubin, 1991)。 0.75
We separate (𝑥𝑖, 𝑠𝑖) in 8 folds, consider 𝜎 ∈ 𝑑 · [1, .1, .01], where 𝑑 is the dimension of X , and 𝜆 ∈ 𝑛−1/2 · [1, 10−3, 10−6], where 𝑛 is the number of data. 8つの折り目で (xi, si) を分離し、d が X の次元であるσ ∈ d · [1, .1, .01] と、n がデータの数であるλ ∈ n−1/2 · [1, 10−3, 10−6] を考える。 0.85
We test the different hyperparameter setup and reported the best error for each corruption parameter on Figure 2. 異なるハイパーパラメータの設定をテストし、図2の腐敗パラメータごとに最善のエラーを報告します。 0.76
Those errors are measured with the 0-1 loss, computed as averaged over the 8 folds, i.e. これらの誤差は0-1の損失で測定され、8倍平均で計算される。 0.80
cross-validated, which standard deviation represented as errorbars on the figure. 標準偏差が図のエラーバーとして表されるクロスバリデーション。 0.73
The best hyperparameter generally corresponds to 𝜎 = .1 and 𝜆 = 10−3 when the corruption is small and 𝜎 = 1, 𝜆 = 10−3 when the corruption is big. 最高のハイパーパラメータは一般にσ = .1 と λ = 10−3 に対応し、汚職が小さいときは σ = 1, λ = 10−3 となる。 0.84
Differences between cross-validated error and testing error were small, and we presented the first one out of simplicity. クロス検証されたエラーとテストエラーの差は小さく,単純さから最初のものを提示した。 0.76
In term of energy cost, the experiments were run on a personal laptop that has two processors, each of them running 2.3 billion instructions per second. エネルギーコストの面では、実験は2つのプロセッサを備えたパーソナルラップトップ上で行われ、それぞれが毎秒230億の命令を実行する。 0.78
During experiments, all the data were stored on the random access memory of 8GB. 実験中、すべてのデータは8GBのランダムアクセスメモリに保存された。 0.82
Experiments were run on Python, extensively relying on the NumPy library (Harris et al., 2020). 実験はPython上で行われ、NumPyライブラリ(Harris et al., 2020)に広く依存している。 0.80
The heaviest computation is Figure 2. 最も重い計算は図2です。 0.80
Its total runtime, cross-validation included, was around 70 seconds. クロスバリデーションを含む全ランタイムは約70秒であった。 0.71
This paper is the results of experimentations, we evaluate the total cost of our experimentations to be three orders of magnitude higher than the cost of reproducing the final computations presented on Figure 1, 2 and 3. 本稿では,実験結果として,実験の総コストを,図1,2,3に示す最終計算を再現するコストよりも3桁高く評価する。 0.70
The total computational energy cost is very negligible. 計算エネルギーの総コストは非常に無視できる。 0.79
(cid:8)𝑥 = (𝑥1, 𝑥2) ∈ R2(cid:12)(cid:12) 𝑥2 (cid:8)x = (x1, x2) ∈ R2(cid:12)(cid:12) x2 0.78
2 ∈ N∗(cid:9) and the solution 𝑓 ∗ : X → Y being defined almost everywhere as 𝑓 ∗(𝑥) = 𝑥2 2 ∈ N∗(cid:9) と解 f ∗ : X → Y はほぼどこでも f ∗(x) = x2 として定義される。 0.85
D.3 Semi-supervised learning - Figure 3 On Figure 3, we review a semi-supervised classification problem with Y = (cid:200)1, 4(cid:201), X = [−4.5, 4.5]2, 𝜇X only charging 2. D.3 半教師付き学習 - 図3 図3では、Y = (cid:200)1, 4(cid:201), X = [−4.5, 4.5]2, μX の半教師付き分類問題について検討する。 0.71
We collect a dataset (𝑥𝑖, 𝑠𝑖), by sampling 2000 points 𝜃𝑖 uniformly at random on [0, 1], as well as 𝑟𝑖 uniformly at random in (cid:200)1, 4(cid:201) = {1, 2, 3, 4}, before building 𝑥𝑖 = 𝑟𝑖 · (cos(2𝜋𝜃𝑖), sin(2𝜋𝜃𝑖)) ∈ X , and 𝑠𝑖 = Y. xi = ri · (cos(2πθi), sin(2πθi) ∈ x , si = y を構築する前に、 [0, 1] 上でランダムに 2000 点 θi をサンプリングし、また (cid:200)1, 4(cid:201) = {1, 2, 3, 4} でランダムに ri をサンプリングしてデータセット (xi, si) を収集する。 0.86
We add four labelled points to this 3,−1) with 𝑠2003 = {2} and dataset 𝑥2001 = (−2 𝑥2001 = (−1, 0) with 𝑠2004 = {1}. この3,−1) を s2003 = {2} とし、データセット x2001 = (−2 x2001 = (−1, 0) を s2004 = {1} とする。 0.84
We designed the weights 𝛼 in Eq. 我々はeqで重量αを設計した。 0.75
(4) with 𝑘-nearest neighbors, with 𝑘 = 20, and solve this equation with a variant of alternative minimization, leading to the optimal solution ˜𝑦𝑖 = 𝑦∗ 𝑖 . (4) k の近傍で、k = 20 で、この方程式を代替最小化の変量で解くと、最適解 yyi = y*i となる。 0.67
In order to be able to compute the 8Moreover, the analysis in Cabannes et al. 8Moreoverを計算するために、Cabannes et alでの分析を行った。 0.68
(2020) suggests that the baseline is estimating a surrogate function in X → 2R, while our method is estimating a function in X → R, which is a much smaller function space, hence needing less regularization. (2020) は、ベースラインが x → 2r のサーロゲート関数を推定していることを示唆し、一方、我々の手法は、より小さい函数空間である x → r の関数を推定している。 0.76
However, those reflections are based on upper bounds, that might be sub-optimal, which could invalidate those considerations. しかし、これらの反射は上界に基づいており、それは準最適であり、そのような考察を無効にする可能性がある。
訳抜け防止モード: しかし、これらの反射は上界に基づいています。 これらの考慮を無効にできます。
1 + 𝑥2 √ 3, 2) with 𝑠2001 = {4}, 𝑥2001 = (1,−2 1 + 𝑥2 √ 3, 2) with 𝑠2001 = {4}, 𝑥2001 = (1,−2 0.93
√ 2) with 𝑠2002 = {3}, 𝑥2001 = (−√ √ 2) with 𝑠2002 = {3}, 𝑥2001 = (−√ 0.96
1 + 𝑥2 21 1 + 𝑥2 21 0.90
(cid:16)(cid:107)𝑥 − 𝑥𝑖(cid:107)2 /ℎ (cid:16)(cid:107)x − xi(cid:107)2 /h 0.80
(cid:17) baseline (13), we design weights 𝛼 for the inference task based on Nadaraya-Watson estimators with Gaussian kernel, defined as 𝛼𝑖(𝑥) = exp , with ℎ = .08. (cid:17) ベースライン (13) は、ガウス核を持つnadaraya-watson推定子に基づく推論タスクの重み付けαを設計し、h = .08 で αi(x) = exp と定義する。 0.77
We solve the inference task on a grid of X composed of 2500 points, and artificially recreate the observation to make them neat and reduce the resulting pdf size. 2500点からなるXの格子上の推論タスクを解くとともに,観測結果を人工的に再現し,その結果のpdfサイズを低減させる。 0.80
Note that it is possible to design weights 𝛼 that capture the cluster structure of the data, which, in this case, will lead to a nice behavior of the baseline as well as our algorithm. データのクラスター構造をキャプチャする重みαを設計することは可能であり、この場合、我々のアルゴリズムと同様にベースラインの優れた振る舞いをもたらすことに注意してください。 0.72
Arguably, this experiment showcase a regularization property of our algorithm (4). この実験はアルゴリズムの正規化特性((4))を示すものと思われる。 0.72
D.4 Ranking with partial ordering To conclude this experiment section, we look at ranking with partial ordering. D.4 部分順序でランク付け この実験セクションを締めくくるために、部分順序でランク付けする。 0.68
We refer to Section 5.4 for a clear description of this instance of partial labelling. 部分的ラベリングのこの例の明確な説明については、第5.4節を参照。 0.60
We provide to the reader eager to use our method, an implementation of our algorithm, available online at https://github.com/V ivienCabannes/partia l_labelling/. 私たちは、アルゴリズムの実装である私たちの方法を使いたい読者に、https://github.com/V ivienCabannes/partia l_labelling/でオンラインで提供しています。
訳抜け防止モード: 本アルゴリズムの実装である本手法の利用を希望する読者に提供した。 https://github.com/v iviencabannes/partia l_labelling/。
It is based on LP relaxation of the NP-hard minimum feedback arcset problem. これはNP-hard最小フィードバック節集合問題のLP緩和に基づいている。 0.68
This relaxation was proven exact when 𝑚 ≤ 6 by Cabannes et al. この緩和は、カバンヌらによって m ≤ 6 で正確に証明された。 0.58
(2020). The LP implementation relies on CPLEX (IBM, 2017). (2020). LP実装はCPLEX(IBM, 2017)に依存している。 0.79
As complementary experiments, we will not provide much reproducibility details, those details would be really similar to the previous paragraphes, and the curious reader could run our code instead. 補完的な実験として、私たちは多くの再現性の詳細を提供しません。これらの詳細は前の段落と本当に似ていて、好奇心のある読者は代わりにコードを実行できます。 0.57
We present our ranking setup on Figure 5 and our results on Figure 6. 我々は、図5のランキング設定と、図6の結果を提示する。 0.84
Figure 5: Ranking setting. 図5: ランキング設定。 0.70
We consider X an interval of R, and Y = S𝑚 with 𝑚 = 4 on the figure. X を R の区間とし、Y = Sm で m = 4 であるとする。
訳抜け防止モード: 我々は X を R の区間と考える。 そして、図形上の m = 4 の Y = Sm である。
(Right) To create a ranking dataset, we sample randomly 𝑚 lines in R2, embedding a value, or equivalently a score, associated to each items as a function of the input 𝑥. (右) ランキングデータセットを作成するために、r2 にランダムに m 行をサンプリングし、入力 x の関数として各項目に関連付けられた値またはスコアを埋め込みます。 0.81
(Left) By ordering those lines, we create preferences between items as a function of 𝑥. (左)これらの直線を順序づけることで、x の関数として項目間の選好を作成する。 0.65
On the figure, when 𝑥 is small, the “red” item is prefered over the “orange” item, itself prefered over the “blue” item, itself prefered over the “green” item. 図1では、x が小さい場合、"red" 項目は "orange" 項目よりも好まれ、それ自体は "blue" 項目よりも好まれ、それ自体は "green" 項目よりも好まれる。 0.76
While when 𝑥 is big, “green” is prefered over “blue”, prefered over “orange”, prefered over “red”. xが大きいときは「青」よりも「緑」が好まれ、「オレンジ」よりも好まれ、「赤」よりも好まれる。 0.73
We create a partial labelling dataset by sampling (𝑥𝑖) ∈ X 𝑛, and providing only partial ordering that the (𝑦𝑖) follow. 我々は (xi) ∈ X n をサンプリングして部分ラベリングデータセットを作成し、 (yi) が従う部分順序のみを提供する。 0.85
For example, for a small 𝑥, we might only give the partial information that “red” is prefered over “blue”. 例えば、小さなxの場合、「赤」が「青」よりも好まれる部分的な情報だけを与えるかもしれません。 0.81
Figure 6: Performance of our algorithm for ranking with partial ordering. 図6:部分順序付けによるランク付けアルゴリズムの性能。 0.77
This figure is similar to Figure 2, but is based on the ranking problem illustrated on Figure 5. この図は図2に似ていますが、図5に示すランキング問題に基づいています。 0.82
For this figure, we consider 𝑚 = 10, as it is arguably the limit where the LP relaxation provided by Cabannes et al. この数値に対し、m = 10 を考えると、カバネスらによって与えられるlp緩和の限界であることは確かである。 0.65
(2020) of the NP-hard minimum feedback arcset problem still performs well. NPハード最小フィードバックアークセット問題の(2020)はまだうまく機能します。 0.71
The corruption parameter corresponds to the proportion of coordinates lost in the Kendall embedding when creating 𝑠𝑖 from 𝑦𝑖. 腐敗パラメータはyiからsiを生成する際、ケンドール埋め込みで失われた座標の比率に対応する。 0.64
Because the Kendall embedding satisfies transitivity constraints, a corruption smaller than 50% is almost ineffective to remove any information. Kendall埋め込みは過渡性制約を満たすため、50%未満の腐敗は情報を削除するのにほとんど効果的ではありません。 0.59
In this figure, we observe a similar behavior for ranking to the one observed for classification on Figure 2, suggesting that those empirical findings are not spurious. この図では、図2の分類で観察されたものと同様のランク付け行動を観察し、これらの経験的発見は疑わしいものではないことを示唆する。 0.65
22 XScoresUnderlyingsco resXItemspreferences Groundtruth506070809 0100Corruption(p.d.u . 22 XScoresUnderlyingsco resXItemspreferences Groundtruth506070809 0100Corruption(p.d.u .) 0.50
)LossRanking,m=10DFILAC )LossRanking,m=10DFILAC 0.74

翻訳にはFugu-Machine Translatorを利用しています。