# (参考訳) 非線形メトリック学習のための次元自由一般化境界 [全文訳有]

Dimension Free Generalization Bounds for Non Linear Metric Learning ( http://arxiv.org/abs/2102.03802v1 )

ライセンス: CC BY 4.0
Mark Kozdoba and Shie Mannor(参考訳) 本研究では,データのニューラルネットワーク型埋め込みによってメトリックが誘導される計量学習問題に対する一般化保証について検討する。 具体的には、2つのレジーム - スパースレジーム、および \emph{bounded amplification} と呼ばれる非スパースレジームに対して一様一般化境界を与える。 スパース規則境界は、パラメータの$\ell_1$-typeノルムが小さい状況に対応する。 分類の状況と同様に、そのような境界を満たす解は問題の適切な正則化によって得られる。 一方、メトリック学習損失の非正規化SGD最適化は、典型的にはスパースソリューションを生成しません。 このような疎性の欠如にもかかわらず、解の異なる新しい性質を頼りにすることで、次元自由一般化保証を提供することが可能であることを示す。 したがって、これらの境界は非スパース実実験的状況における一般化を説明することができる。 mnistおよび20newsgroupsデータセット上での研究現象について述べる。

In this work we study generalization guarantees for the metric learning problem, where the metric is induced by a neural network type embedding of the data. Specifically, we provide uniform generalization bounds for two regimes -- the sparse regime, and a non-sparse regime which we term \emph{bounded amplification}. The sparse regime bounds correspond to situations where $\ell_1$-type norms of the parameters are small. Similarly to the situation in classification, solutions satisfying such bounds can be obtained by an appropriate regularization of the problem. On the other hand, unregularized SGD optimization of a metric learning loss typically does not produce sparse solutions. We show that despite this lack of sparsity, by relying on a different, new property of the solutions, it is still possible to provide dimension free generalization guarantees. Consequently, these bounds can explain generalization in non sparse real experimental situations. We illustrate the studied phenomena on the MNIST and 20newsgroups datasets.
公開日: Sun, 7 Feb 2021 14:47:00 GMT

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


    Page: /      
1 2 0 2 b e F 7 1 2 0 2 b e F 7 0.85
] G L . ] G L。 0.79
s c [ 1 v 2 0 8 3 0 sc [ 1 v 2 0 8 3 0 0.68
. 2 0 1 2 : v i X r a . 2 0 1 2 : v i X r a 0.85
Dimension Free Generalization Bounds for Non Linear Metric 非線型計量に対する次元自由一般化境界 0.82
Learning Mark Kozdoba1 学習 Mark Kozdoba 0.75
Shie Mannor1 Shie Mannor1 0.88
markk@technion.ac.il markk@technion.ac.il 0.59
shie@ee.technion.ac. il shie@ee.technion.ac. il 0.47
1 Technion, Israel Institute of Technology 1 イスラエル工科大学 テクニオン 0.76
Abstract In this work we study generalization guarantees for the metric learning problem, where the metric is induced by a neural network type embedding of the data. 概要 本研究では,データのニューラルネットワーク型埋め込みによってメトリックが誘導される計量学習問題に対する一般化保証について検討する。 0.62
Specifically, we provide uniform generalization bounds for two regimes – the sparse regime, and a non-sparse regime which we term bounded amplification. 具体的には、スパース・レジームと非スパース・レジームという2つのレジームに対して統一的な一般化境界を提供する。
訳抜け防止モード: 具体的には、スパース政権とスパース政権の2つの体制に統一的な一般化境界を提供します。 そして私たちが境界増幅と呼ぶ非スパース体制。
The sparse regime bounds correspond to situations where (cid:96)1-type norms of the parameters are small. スパース規則境界は(cid:96)1型のパラメータのノルムが小さい状況に対応する。 0.77
Similarly to the situation in classification, solutions satisfying such bounds can be obtained by an appropriate regularization of the problem. 分類の状況と同様に、そのような境界を満たす解は問題の適切な正則化によって得られる。 0.68
On the other hand, unregularized SGD optimization of a metric learning loss typically does not produce sparse solutions. 一方、メトリック学習損失の非正規化SGD最適化は、典型的にはスパースソリューションを生成しません。 0.74
We show that despite this lack of sparsity, by relying on a different, new property of the solutions, it is still possible to provide dimension free generalization guarantees. このような疎性の欠如にもかかわらず、解の異なる新しい性質を頼りにすることで、次元自由一般化保証を提供することが可能であることを示す。 0.63
Consequently, these bounds can explain generalization in non sparse real experimental situations. したがって、これらの境界は非スパース実実験的状況における一般化を説明することができる。 0.52
We illustrate the studied phenomena on the MNIST and 20newsgroups datasets. mnistおよび20newsgroupsデータセット上での研究現象について述べる。 0.68
1 Introduction [Bellet et al., 2015], 1 はじめに [Bellet et al., 2015] 0.70
Metric Learning, is the problem of finding a metric ρ on the space of features, such that ρ reflects some semantic properties of a given task. メトリックラーニング(英: Metric Learning)とは、あるタスクのセマンティックな性質を ρ が反映するような、特徴空間上の計量 ρ を見つける問題である。 0.74
Generally, the input can be thought of as a set of labeled pairs {((xi, x(cid:48) i=1, where i ∈ Rd are the features, and yi is the label, inxi, x(cid:48) dicating whether xi and x(cid:48) i should be close in the 一般に、入力はラベル付きペア {((xi, x(cid:48) i=1, ここで i ∈ Rd は特徴であり、 yi はラベル、 inxi, x(cid:48) であり、 xi と x(cid:48) i が近づかなければならないかどうかを示す。 0.86
i), yi)}n metric or far apart. i), yi)}n メートルまたは遠く離れて。 0.66
For instance, in face identification, [Schroff et al., 2015], features xi and x(cid:48) i corresponding to the same face should be close in ρ, while different faces should be far apart. 例えば、顔の識別において、[Schroff et al., 2015] は、同じ顔に対応する xi と x(cid:48) i は ρ に近く、異なる顔は遠く離れるべきである。 0.75
Note that the above metric learning formulation is fairly general and one can convert supervised clustering, or even standard classification problems into metric learning simply by setting yi = 1 if xi and x(cid:48) i have the same original label and yi = 0 otherwise [Davis et al., 2007, Weinberger and Saul, 2009, Cao et al., 2016, Khosla et al., 2020, Chicco, 2020]. 上記の計量学習の定式化は比較的一般的であり、 xi と x(cid:48) i が同じ元ラベルを持ち、yi = 0 がなければ yi = 0 となるような場合、単に yi = 1 を設定するだけで、標準的な分類問題や標準分類問題を計量学習に変換することができる(Davis et al., 2007, Weinberger and Saul, 2009, Cao et al., 2016, Khosla et al., 2020, Chicco, 2020]。 0.77
The metric ρ is typically assumed to be the Euclidean metric taken after a linear or non-linear embedding of the features. 計量 ρ は一般に、その特徴の線型あるいは非線形埋め込みの後に取られるユークリッド計量であると仮定される。
訳抜け防止モード: メートル法 ρ は一般に仮定される 特徴の線型あるいは非線型埋め込みの後に取られるユークリッド計量である。
That is, we consider a parametric family F∗ of embeddings into a k-dimensional space, f∗ : Rd → Rk, and set 1 すなわち、k-次元空間への埋め込みのパラメトリック族 F∗, f∗ : Rd → Rk, そして集合 1 を考える。 0.73
ρ(x, x(cid:48)) = ρk,f∗ (x, x(cid:48)) = ρ(x, x(cid:48)) = ρk,f∗(x, x(cid:48)) = 0.96
(cid:107)f∗(x) − f∗(x(cid:48))(cid:107) 2 2 . (cid:107)f∗(x) − f∗(x(cid:48))(cid:107) 2 2 。 0.88
(1) 1 k As an example, Figure 1 shows tSNE plots, [Maaten and Hinton, 2008], of the classical 20newsgroups dataset. (1) 1k 例えば、図1は、古典的な20newsgroupsデータセットのtsneプロット、[maaten and hinton, 2008]を示している。 0.77
Figure 1a was generated using the regular bag of words representation of the data (see Section 6 for additional details) while Figure 1b was generated by applying tSNE to an embedding of the data (of the form (3) below) learned by minimizing a loss based on labels, as described above. 図1aはデータの正規表現の袋を用いて生成され(詳細は第6節を参照)、図1bは、上記のようにラベルに基づく損失を最小化して学習したデータ(以下の形式(3))の埋め込みにtsneを適用して生成されます。 0.84
Clearly, there is no discernible relation between the label and the metric in the raw representation, but there is a strong relation in the learned metric. 明らかに、生の表現ではラベルとメトリックの間には識別可能な関係はありませんが、学習されたメトリックには強い関係があります。 0.66
One can also 1Note that ρ in (1) is not strictly a metric. これもできる。 1 の ρ は厳密な計量ではないことに注意。 0.68
Nevertheless, this terminology is common. それでも この用語は一般的です 0.72
1 1 0.85
(a) Raw features, after normalization and 500 dim. (a) 正常化および500ディムの後で生の特徴。 0.71
PCA. (b) Learned embedding, k=50, test set. PCA。 (b)学習埋め込み,k=50,テストセット。 0.82
Figure 1: tSNE plot of the 20newsgroup data, restricted to the first 10 labels. 図1: 最初の10ラベルに制限された20newsgroupデータのtSNEプロット。 0.81
Points are colored according to the label. ポイントはラベルによって色付けされる。 0.75
obtain similar conclusions, and quantify them, by, for instance, replacing tSNE with spectral clustering. 同様の結論を得て、例えば、tSNEをスペクトルクラスタリングに置き換えることで、それらを定量化する。 0.60
The uniform generalization problem for metric learning is the following: Given a family of embeddings F∗, provide bounds, that hold uniformly for all f∗ ∈ F∗, on the difference between the expected value of the loss and the average value of the loss on the train set; see Section 2 for a formal definition. 計量学習のための一様一般化問題は次のものである: 埋め込み f∗ の族が与えられたとき、すべての f∗ ∈ f∗ に対して一様に保たれる境界は、列車集合における損失の期待値と損失の平均値との差に基づいて与えられる。 0.76
Such bounds guarantee, for instance, that the train set would not be overfitted. このような境界は、例えば、列車セットがオーバーフィットしないことを保証する。 0.62
Given a family of embeddings F∗, consider the family F of functions f : Rd × Rd → R of the form 埋め込み F∗ の族が与えられたとき、函数 f : Rd × Rd → R の族 F を考える。 0.73
F = {f (x, x(cid:48)) = ρk,f∗ (x, x(cid:48)) | f∗ ∈ F∗} . F = {f (x, x(cid:48)) = ρk,f∗ (x, x(cid:48)) | f∗ ∈ F∗} 。 0.94
(2) between F∗,F,Rn (F), and generalization bounds. (2) F∗,F,Rn (F) と一般化境界の間の。 0.83
1.1 Sparsity Based Bounds 1.1スパーシティに基づく境界 0.50
In this paper our goal is to provide generalization bounds for neural network type non-linear embeddings f∗. 本論文では,ニューラルネットワーク型非線形埋め込みの一般化バウンダリを提供する。
訳抜け防止モード: この論文の目標は ニューラルネットワーク型非線形埋め込みf∗の一般化境界を提供する。
Specifically, we will be interested in embeddings f∗ : Rd → Rk of the form f∗(x) = φ(Atx) 具体的には、f∗(x) = φ(Atx) という形の f∗ : Rd → Rk の埋め込みに興味を持つ。 0.80
(3) where A ∈ Rd×k is a matrix and φ : R → R is a Lipschitz non-linearity which acts on Atx coordinatewise. (3) A ∈ Rd×k を行列とし、φ : R → R を Ax 上で座標的に作用するリプシッツ非線型性とする。 0.80
Equivalently, these embeddings are given by a single layer of a neural network. 同様に、これらの埋め込みはニューラルネットワークの単一層によって与えられる。 0.73
We note that the single layer case is the essential hard case for the metric learning problem. メトリクス学習問題では,単層の場合が本質的なハードケースであることに留意する。 0.66
It is interesting in its own right, and moreover, multi-layer guarantees can easily be obtained by combining the single layer case with the methods used in the derivation of the existing neural network bounds. さらに、単一層の場合と既存のニューラルネットワーク境界の導出に使用する方法を組み合わせることで、多層保証を容易に得ることができる。 0.57
Additional details are provided in Remark 6. 詳細についてはRemark 6を参照。 0.65
In view of this, in most parts of this paper we will concentrate on the single layer case. これを考慮して、この論文のほとんどの部分では、我々は単一の層ケースに集中します。 0.70
Let (cid:107)A(cid:107)o p denote the spectral norm, and set i=1 (cid:107)A·i(cid:107)2, where A·i is the i-th column of A. スペクトルノルムを(cid:107)A(cid:107)o pとし、i=1(cid:107)A·i(cid:107)2とする。 0.74
Let F∗ be the set of embedding of the form (3) induced by some set of matrices G. In what follows we identify G and F∗ and refer to F∗ directly as the set of matrices, where the embeddings are assumed to be of the form (3). 次は、G と F を識別し、F を直接行列の集合と呼び、埋め込みが (3) の形式であると仮定する。
訳抜け防止モード: F∗ をある種の行列 G によって誘導される形式 (3 ) の埋め込みの集合とする。 F∗ を直接行列の集合と呼びます。 埋め込みは (3 ) の形式であると仮定される。
We further assume that input feature norms are bounded by some b > 0, (cid:107)x(cid:107)2 ≤ b. さらに、入力特徴ノルムは b > 0, (cid:107)x(cid:107)2 ≤ b で有界であると仮定する。 0.77
Recall that n is the number of samples. n がサンプル数であることを思い出してください。 0.70
(cid:107)A(cid:107)2 ,1 =(cid:80)k (cid:107)A(cid:107)2 ,1 =(cid:80)k 0.75
Our first result is the following generalization 最初の結果は次の一般化です 0.79
bound (up to constants and logarithmic terms): 束縛(定数と対数項まで) 0.45
Rn (F) ≤ b2 (cid:107)φ(cid:107)2 Rn (F) ≤ b2 (cid:107)φ(cid:107)2 0.88
Lip supA∈F∗ (cid:107)A(cid:107)o p supA∈F∗ (cid:107)A(cid:107)2 ,1 Lip supA∈F. (cid:107)A(cid:107)o p supA∈F. (cid:107)A(cid:107)2 ,1 0.64
√ k n . We refer to these as the distance functions, which map a pair of features into their distance after the embedding. √ k n . 我々はこれらを距離関数と呼び、埋め込み後の2つの特徴をそれらの距離にマッピングする。 0.85
Well known arguments imply that one can obtain generalization bounds for F∗ by providing upper bounds on the Rademacher complexity Rn (F) of the family of the scalar functions F. Therefore in what follows, we discuss directly the upper bounds on Rn (F) for various families F∗. よく知られた議論は、スカラー函数 F の族のラデマチャー複雑性 Rn (F) 上の上界を提供することによって、F の一般化境界を得ることができることを意味する。
訳抜け防止モード: よく知られた議論は、スカラー函数 F の族のラデマチャー複雑性 Rn (F ) 上の上界を提供することによって、F の一般化境界を得ることができることを意味する。 我々は、様々な家族のためのRn(F)上の上限を直接議論する。
We refer to Sections 2 and 4 for formal definitions and details on the relation 正式な定義と関係の詳細については、セクション2および4を参照してください。 0.66
(4) The full statement and proof of this result are given as Theorem 1. (4) この結果の完全な声明および証明は Theorem 1 として与えられます。 0.86
This bound is the direct analog, in the metric learning setting, of the strongest currently known uniform bounds for neural network classification, [Bartlett et al., 2017], which are also formulated in terms of (cid:107)·(cid:107)op and (cid:107)·(cid:107)2,1 norms. この境界は、(cid:107)·(cid:107)opおよび(cid:107)·(cid:107)2,1ノルムの観点からも定式化されている、ニューラルネットワーク分類のための最強の現在知られている均一境界の直接アナログである。 0.65
Bounds using these norms may generally be regarded as sparsity type bounds – if we control the sum of the norms これらのノルムを用いた境界は一般にスパーシティ型境界と見なされる-ノルムの総和を制御すれば 0.70
2 −100−75−50−250255075100−100−75−50−250255075100−60−40−200204060−40−2002040 2 −100−75−50−250255075100−100−75−50−250255075100−60−40−200204060−40−2002040 0.47
of coordinate functionals, then we control generalization. 座標関数を制御し 一般化を制御します 0.70
In particular, this bound will be small iff only a small number of output coordinate functionals (i.e. 特に、この境界は、少数の出力座標関数(すなわち、)のみの小さな iff となる。 0.70
columns of A) have large norms. a)の列には大きな規範がある。 0.71
This is similar to the standard (cid:96)1 regularized logistic regression, where we want only a small number of coefficients to be large. これは標準の (cid:96)1 正規化ロジスティック回帰(英語版)と似ており、ここでは少数の係数だけが大きいことを望んでいる。
訳抜け防止モード: これは標準(cid:96)1正規化されたロジスティック回帰に似ています。 小さい数の係数だけを 大きくしたいのです
1.2 Bounded Amplification Based Bounds 1.2 有界増幅法 境界 0.63
If the (cid:107)A(cid:107)2 ,1 is forced to be small, for instance by adding an appropriate regularization term to the loss, then the learned A will be sparse and (4) may explain generailzation. 例えば、損失に適切な正規化項を加えると、(cid:107)A(cid:107)2 ,1 は小さくなり、学習された A は小さくなり、(4) は遺伝子分解を説明する。 0.73
However, solutions obtained by stochastic gradient descent without regularization are not sparse. しかし、規則化なしに確率勾配降下によって得られる解は乏しいものではない。 0.51
We illustrate this in Section 6 using standard datasets. 標準データセットを使用して、セクション6でこれを説明します。 0.50
In these experiments an embedding is learned by minimizing the loss with SGD without any regularization (or at least, without (cid:107)A(cid:107)2 ,1 regularization), and we observe the behavior of the norms for a range of values of k. We find that on the one hand, even for large values of k the generalization gap stays bounded, there is no overfitting. これらの実験では、正規化なしでSGDによる損失を最小限に抑えること(または少なくとも(cid:107)A(cid:107)2 ,1正規化なし)によって埋め込みを学び、kの値の範囲のノルムの挙動を観察します。
訳抜け防止モード: これらの実験では、埋め込みが学習される。 正規化なしでSGDによる損失を最小限に抑える(少なくとも (cid:107)A(cid:107)2 ,1 正規化なしで) 我々はkの値の範囲のノルムの振舞いを観察します。 kの大きい値であっても 一般化ギャップは 束縛されている。 過度に適合することはない
On √ the other hand, for the learned matrices A the norm (cid:107)A(cid:107)2 ,1 grows linearly with k while (cid:107)·(cid:107)op grows as k. This in particular means that the left handside of (4) grows as k, which suggests that it can not explain the observed generalization. 一方、学習した行列 A に対して、ノルム (cid:107)A(cid:107)2 ,1 は k とともに直線的に成長し、(cid:107)·(cid:107)op は k として成長する。
訳抜け防止モード: 一方、学習行列 A に対してノルム (cid:107)A(cid:107)2 ,1 は k while () で線型に成長する。 cid:107)·(cid:107)op は k として成長する。 つまり (4 ) の左手は k として成長する。 これは観測された一般化を説明できないことを示唆しています
Consequently, to explain the above generalization, we introduce a different bound. したがって、上記の一般化を説明するために、異なる境界を導入する。 0.66
Denote (cid:107)A(cid:107)2 ,∞ = maxi≤k (cid:107)A·i(cid:107)2. 注記 (cid:107)A(cid:107)2 ,∞ = maxi≤k (cid:107)A·i (cid:107)2 0.80
Then (again, up to logarithmic terms) we have: その後(さらに、対数項まで)、次のようになります。 0.57
√ Rn (F) ≤ b2 supA∈F∗ (cid:107)A(cid:107)2 √ Rn (F) ≤ b2 supA∈F\ (cid:107)A(cid:107)2 0.82
√ n 2,∞ . (5) √ n 2,∞ . (5) 0.81
This will be shown in Theorem 4. これは Theorem 4 で示されます。 0.82
In the experiments we observe that (cid:107)A(cid:107)2 ,∞ remains roughly constant as a function of k, and therefore this bound does explain the generalization. 実験では (cid:107)A(cid:107)2 ,∞ は k の関数としてほぼ一定であり、したがってこの境界は一般化を説明する。 0.77
Even more importantly, however, the bound (5) is remarkable because there is no sparsity control term for columns and yet it is still dimension free. しかし、さらに重要なことに、境界 (5) は列のスパーシティ制御項がなく、それでも次元自由であるため、注目すべきである。 0.70
That is, the feature and embedding dimensions, d and k, do not enter the bound. すなわち、d と k という特徴と埋め込み次元は境界には入らない。 0.54
Put differently, typically sparsity implies generalization because while the problem may have many 問題は多数あるかもしれないが、典型的にはスパース性は一般化を意味する。 0.43
3 parameters, only few of them will be non-zero at each instance of the problem, and thus “effective” number of parameters is low, [Hastie et al., 2015, Bartlett et al., 2017, Zhou et al., 2019]. 3 パラメータは、問題の各インスタンスでゼロではないだけであり、したがって「効果的な」パラメータの数は低いです[Hastie et al., 2015 Bartlett et al., 2017 Zhou et al., 2019]。 0.78
In contrast, in (5), all k columns can have the same non zero Euclidean norm a, the “effective” number of parameters can be arbitrarily high, and yet the bound will not deteriorate when the number of samples n is fixed and k is growing. 対照的に、(5) では、すべての k 列が同じ非零ユークリッドノルム a を持つことができ、パラメータの「有効」個数は任意に高くなり得るが、サンプル n の個数が固定され k が成長すると境界が低下しない。 0.77
We refer to situations where only (cid:107)A(cid:107)2 ,∞ is bounded as the bounded amplification regime, as distinguished from the sparse regime. 我々は、(cid:107)A(cid:107)2 ,∞のみを、スパース系と区別されるような有界増幅系として有界な状況を指す。 0.67
The boundedness here refers to the fact that each column individually still should be (cid:96)2 bounded. ここでの有界性は、各列が(cid:96)2 の有界であることを指す。 0.61
It is important to note that the normalization by k in (1) is crucial to the fact that (5) is dimension free. 注意すべきことは、(1) の k による正規化は (5) が次元自由であるという事実に不可欠である。 0.77
In Remark 7 we discus in detail why this is an appropriate normalization for this case. Remark 7では、このケースが適切な正規化である理由を詳細に説明します。 0.67
It is also worth noting that among the bounds (4) and (5) none is stronger than the other, i.e., it is not true that (4) implies (5) or vice versa. また、境界 (4) と (5) の間に他のものよりも強いものはなく、すなわち (4) が (5) または その逆を意味することは事実ではない。 0.78
Rather, they apply to genuinely different types of embeddings f∗, those that minimize the (cid:107)·(cid:107)2,1-regular ized loss, and those that minimize the unregularized one. むしろ、真に異なる種類の埋め込み f∗、(cid:107)·(cid:107)2,1-正規化損失を最小化するもの、および非正規化損失を最小化するものに適用する。 0.63
1.3 Methods We now briefly describe the ideas underlying the proofs. 1.3方法 証拠の根底にあるアイデアを簡潔に説明します。 0.64
To prove (4) we take the classical approach of bounding the covering numbers of the set of (cid:107)·(cid:107)2,1 bounded matrices, using an estimate from [Bartlett et al., 2017], which in turn is an extension of estimates in [Zhang, 2002], [Bartlett, 1998]. (4) を証明するために、(cid:107)·(cid:107)2,1 有界行列の集合の被覆数を [bartlett et al., 2017] から推定し、[zhang, 2002], [bartlett, 1998] における推定の延長とする古典的なアプローチをとる。 0.75
The Rademacher bound then follows from the Dudley entropy bound. その後、ラデマッハ境界はダドリーエントロピー境界から続く。 0.38
However, this method does not seem √ to yield (5), and provides bounds that are off by a k factor. しかし、この方法では (5) が成り立つようには見えず、k 因子によってオフとなる境界を与える。
訳抜け防止モード: しかし、この方法では (5 ) を収まるようには見えない。 K因子によってオフとなる境界を提供する。
Thus, to prove (5) we take a different したがって (5) を証明するには 0.60
approach. We give two proofs for (5), both of which exploit the particular structure of the metric (1) as an average over the coordinates. 近づいた (5) に対して二つの証明を与えるが、どちらも座標上の平均として計量(1) の特定の構造を利用する。 0.56
Equivalently, the distance ρk,f can be viewed as a voting outcome by an ensemble of individual coordinates. 同様に、距離 ρk,f は個々の座標の集合による投票結果と見なすことができる。 0.80
The first argument is based on the sub-additivity of Rademacher complexities and makes a direct use of the average structure as above. 最初の引数は、ラデマチャー複素数の部分加法に基づいており、上記の平均構造を直接利用する。 0.59
The second argument is a dimension reduction scheme. 2番目の引数は、寸法削減スキームです。 0.66
This argument gives a somewhat この議論は幾らかの理由を与える 0.50
weaker, although still dimension independent result, but has the advantage of making it much clearer why there is dimension independent generalization. より弱いが、次元独立な結果でありながら、次元独立な一般化が存在する理由をより明確にする利点がある。 0.72
We also believe this argument has greater potential in generalizing to other situations. 我々はまた、この議論が他の状況に一般化する可能性が大きいと信じている。 0.53
This dimension reduction was inspired by [Schapire et al., 1998], where a related approach was used to analyze ensemble learning. この次元の縮小は[Schapire et al., 1998]に触発され, 関連するアプローチを用いてアンサンブル学習を分析した。 0.83
1.4 Contributions To conclude this Section we summarize the contributions of this work: (i) For metric learning with non linear embeddings, we prove generalization bounds which depend only on the norms (cid:107)·(cid:107)2,1, (cid:107)·(cid:107)op of the embedding matrix, similarly to the recent neural network classification bounds. 1.4 貢献 i) 非線形埋め込みによる計量学習において、(cid:107)·(cid:107)2,1,(cid:10 7)·(cid:107)最近のニューラルネットワーク分類境界と同様に、埋め込み行列の標準(cid:107)のみに依存する一般化境界を証明します。
訳抜け防止モード: 1.4 貢献 本節をまとめるために,本研究の貢献を要約する。 : (i)非線形埋め込みによる計量学習について 埋め込み行列のノルム(cid:107)·(cid:107)2,1,(cid:10 7)·(cid:107)op)のみに依存する一般化境界を証明する。 最近のニューラルネットワークの分類と似ています。
(ii) We introduce a new type of bounds, the bounded amplification type bounds, with dependence only on the (cid:107)·(cid:107)2,∞ norm. (ii)新しいタイプの境界である有界増幅型境界を導入し、(cid:107)·(cid:107)2,∞ノルムのみに依存する。 0.66
Such bounds have not been studied before, in metric learning, or in statistical learning theory in general. このような境界は、計量学習や一般の統計学習理論ではこれまで研究されていない。 0.66
The methods of proof here are also new. ここでの証明方法も新しいものです。 0.76
(iii) We observe empirically that the above bounded amplification regime of matrix weights occurs naturally in basic experiments on standard datasets. (iii)上記の行列重みの有界増幅レジームが標準データセットに関する基礎実験で自然に発生することを実証的に観察する。 0.75
Our new bounds therefore can explain, in standard situations, dimension independence that can not be explained by the more common types of bounds. したがって、我々の新しい境界は、標準的な状況では、より一般的なタイプの境界によって説明できない次元独立性を説明できる。 0.62
The rest of this paper is organized as follows: In Section 2 we overview the necessary background on metric learning and generalization. 第2節では,メトリクス学習と一般化に関する必要な背景について概説する。
訳抜け防止モード: 本論文の残りは以下のとおり整理される。 第2節では,計量学習と一般化に必要な背景について概説する。
Literature and related work are discussed in Section 3. 文学と関連作品は第3節で議論されている。 0.61
In Section 4 we provide the notation required for the formal discussion of the results. セクション4では、結果の正式な議論に必要な表記を提供します。 0.75
Section 5 contains the statements of the results and overviews of the proofs. 第5節には、結果の記載と証明の概要が含まれている。 0.65
Some of full proofs are deferred to the Supplementary Material due to space constraints. 完全な証明のいくつかは、空間の制約により補助材料に延期される。 0.61
Experiments are described in Section 6. 実験は第6節で述べられている。 0.63
In Section 7 we conclude the paper and discuss future work. 第7節では、論文をまとめ、今後の作業について論じる。 0.57
2 Metric Learning Background 2 メトリクス学習の背景 0.85
As discussed in Section 1, we assume that the training data is given as a set {((xi, x(cid:48) i=1 of labeled feature pairs, which we assume to be sampled inde- 第1節で述べたように、トレーニングデータはラベル付きフィーチャーペアのセット {((xi, x(cid:48) i=1 として与えられると仮定します。 0.68
i), yi)}n pendently form some distribution D on Rd × Rd × Y , where Y is some set of label values. i), yi)}n Rd × Rd × Y 上のある分布 D をペンデントに形成し、Y はラベル値の集合である。 0.74
It is usually sufficeint to take Y = {0, 1}. 通常、Y = {0, 1} を取るのに十分である。 0.80
Note that there may be dependence within the pair, i.e. ペア内に依存がある可能性があることに注意してください。 0.55
x(cid:48) i may depend on xi. x(cid:48) i は xi に依存します。 0.77
The quality of the embedding f∗ on a data point ((x, x(cid:48)), y) is measured via a loss function (cid:96), which usually depends on ((x, x(cid:48)), y) only through the metric ρk,f∗ . データポイント ((x, x(cid:48)), y) 上の埋め込み f∗ の品質は損失関数 (cid:96) によって測定されるが、これは通常、計量 ρk,f∗ を通してのみ ((x, x(cid:48)), y に依存する。 0.85
That is, we assume that there is a fixed function (cid:96) : R × Y → [0, 1], such that the loss of f∗ ∈ F∗ on a data point ((x, x(cid:48)), y) is given by Lf∗ ((x, x(cid:48)), y) = (cid:96)(ρk,f∗ (xi, x(cid:48) i), yi). すなわち、あるデータ点 ((x, x(cid:48)), y) 上の f∗ ∈ F∗ の損失が Lf∗ ((x, x(cid:48)), y) = (cid:96)(ρk,f∗ (xi, x(cid:48) i), yi) によって与えられるような固定函数 (cid:96) : R × Y → [0, 1] が存在すると仮定する。 0.90
A typical example of a loss (cid:96) is the following version of the margin loss: 損失の典型的な例(cid:96)は、マージン損失の次のバージョンである。 0.83
(cid:40) (cid:96)λ S,D(ρ, y) = (cid:40) (cid:96)λ S,D(ρ, y) = 0.88
min (1, λ · ReLU (ρ − S)) min (1, λ · ReLU (D − ρ)) min (1, λ · ReLU (ρ − S)) min (1, λ · ReLU (D − ρ)) 0.85
if y = 1 otherwise, y = 1 でなければ 0.74
where ReLU (x) = max (0, x). ここで ReLU (x) = max (0, x)。 0.84
As discussed in Section 1, this loss embodies the principle that (x, x(cid:48)) should be close iff y = 1, by penalizing distances above S when y = 1 and penalizing distances below D otherwise. 第1節で述べたように、この損失は、(x, x(cid:48)) が s 上の距離を y = 1 でペナルティし、それ以外は d 以下の距離をペナルティ化するという原理を具現化している。 0.68
The overall loss on the data, or the empirical risk, データに対する全体的な損失、または経験的リスク。 0.71
is given by ˆRf∗ = が与えられます ~Rf∗ = 0.61
1 n n(cid:88) 1n n(cid:88) 0.79
i=1 Lf∗ ((xi, x(cid:48) i=1 Lf∗((xi, x(cid:48)) 0.74
i), yi). (6) i)、yi)。 (6) 0.72
risk given expected リスク ですから 期待 0.62
The is = E((x,x(cid:48)),y)∼DLf∗ ((x, x(cid:48)), y). a = E((x,x(cid:48)),y) DLf((x,x(cid:48)), y) である。 0.81
The uniform generalization problem of metric learning is similar to the generalization problem of classification: One is interested in conditions on the family F∗ under which the gap between expected and empirical risks, Rf∗ − ˆRf∗ , is small for all f∗ ∈ F∗. 計量学習の統一一般化問題は、分類の一般化問題に類似している: 1 つは、予想されるリスクと経験的リスクのギャップ Rf がすべての f ∈ F に対して小さいファミリー F 上の条件に興味がある。 0.75
by Rf∗ i), yi)}n Rf∗による i), yi)}n 0.62
Finally, since {((xi, x(cid:48) 最後に、 {((xi, x(cid:48)) 0.84
i=1 are independent, standard results imply that to control the uniform generalization bounds of the risk, it is sufficient to control the Rademacher complexity of the family F of distance value functions induced by F∗, as defined in (2). i=1 は独立であり、標準的な結果は、リスクの均一な一般化境界を制御するためには、F∗ によって誘導される距離値関数の族 F のラデマッハ複雑性を制御するのに十分であることを意味する。 0.69
Specifically, we have that (see [Mohri et al., 2018] Theorem 3.3 and Lemma 5.7) , 具体的には、[Mohri et al., 2018] Theorem 3.3 と Lemma 5.7 を参照してください。 0.76
(cid:114) log δ−1 (cid:114) log δ−1 0.75
2n Rf∗ − ˆRf∗ ≤ 2(cid:107)(cid:96)(c id:107)Lip Rn (F) + 2n Rf∗ − >Rf∗ ≤ 2(cid:107)(cid:96)(c id:107)Lip Rn (F) + 0.79
sup f∈F 4 sup f∈F 4 0.78
holds with probability at least 1 − δ. 少なくとも 1 − δ の確率で保持する。 0.80
Here Rn (F) is the Rademacher complexity of F and (cid:107)(cid:96)(ci d:107)Lip is the Lipschitz constant of (cid:96) as a function of its first coordinate. ここで Rn (F) は F と (cid:107)(cid:96)(ci d:107)(リップは最初の座標関数として (cid:96) のリプシッツ定数である。 0.81
3 Literature A general survey of the field of metric learning can be found in [Bellet et al., 2015]. 3文学 計量学習の分野に関する一般的な調査は[Bellet et al., 2015]で見ることができる。 0.80
See also [Chicco, 2020] for a survey of recent applications in deep learning contexts. ディープラーニングのコンテキストにおける最近の応用に関する調査も [Chicco, 2020] ご覧ください。 0.71
In these situations, the metric learning loss is sometimes referred to as a Siamese network. このような状況では、メトリック学習の損失をシャムネットワークと呼ぶことがある。 0.77
Up to now, generalization guarantees in metric learning were only studied in the linear setting, i.e. これまで、距離学習における一般化の保証は線形設定でのみ研究されてきた。 0.70
for embeddings of the form (3) where φ(x) = x. φ(x) = x であるような形式 (3) の埋め込みに対して。 0.81
In particular, all literature cited in this Section deals with the linear case. 特に、この節で引用されるすべての文献は、線形の場合を扱う。 0.65
As discussed in Sections 1 and 2, 第1節と第2節で述べたとおり。 0.49
in this paper we use the formal setting introduced in [Verma and Branson, 2015], where we assume that the data comes as a set of iid feature pairs with a label per pair, ((xi, x(cid:48) i=1. 本稿では,[Verma and Branson, 2015] で導入された形式設定を用いて,iid 特徴ペアの集合として,ラベルごとに ((xi, x(cid:48) i=1) のセットとしてデータが来ることを仮定する。 0.81
In this setting, the empirical risk is given by (6). この設定では、(6)により経験的リスクが与えられる。 0.71
In the special case where the data comes with a label per feature, (xi, li)n i=1, one can use an alternative notion of empirical risk, given by データが特徴ごとのラベル、(xi, li)n i=1が付属する特別なケースでは、経験的リスクの代替概念を使用できます。 0.66
i), yi)n (cid:0)(xi, xj), 1{li(cid:54)=lj}(cid:1) , i), yi)n (cid:0)(xi, xj), 1{li(cid:54)=lj}(cid:1) , 0.83
Lf (7) ˜Rf = Lf (7) ~Rf= 0.81
1 n(n − 1) 1 n(n − 1) 0.85
n(cid:88) (cid:88) n(cid:88) (cid:88) 0.81
i=1 j(cid:54)=i i=1 j(cid:54)=i 0.69
which is viewed as a second order U-statistic, see [Cao et al., 2016]. 2次U統計として表示されている[Cao et al., 2016]を参照してください。 0.65
That is, instead of considering the input as a set of independently sampled pairs, which can be obtained from the (xi, li)n i=1 by, for instance, creating pairs out of consecutive samples, in (7) one considers all possible pairs. つまり、入力を(xi, li)n i=1から得ることができる独立サンプリングペアの集合として考慮するのではなく、例えば連続サンプルからペアを作成することで、(7)すべての可能なペアを検討する。 0.75
On one hand, compared to the risk ˆRf defined by (6), for small datasets ˜Rf might make a somewhat better use of the data. 一方、 (6) で定義されているリスク >Rf と比較すると、小さなデータセット >Rf はデータの利用を多少改善する可能性がある。 0.73
On the other hand, ˜Rf is less general, since the data does not necessarily have to be generated by the label-perfeature setting, and moreover, even evaluating (7) may be computationally difficult since the number of terms in the sum is quadratic in dataset size. 一方、rfはラベル・パーフィーチャー設定によってデータを生成する必要はなく、また、合計の項数がデータセットサイズで2倍であるので、7)の評価も計算困難である。
訳抜け防止モード: というのも、データは必ずしもラベルによって生成される必要はなく、永続的な設定である。 さらに (7 ) の評価も 計算が難しいかもしれません 総和における項の数はデータセットサイズで2次である。
In practice, the empirical loss used is somewhere between ˆRf and ˜Rf . 実際には、使用した経験的損失は「Rf」と「Rf」の間にある。 0.49
5 The setting that of 5 あらすじ 設定 というか 0.62
considered Alternatively, generalization 考慮 または 一般化 0.64
[Mohri et al., 2018]. [Mohri et al., 2018] 0.71
here the uniform generalization bounds, is see in [Wang et al., 2019], [Lei et al., 2020], the linear case of metric learning was studied in the framework of algorithmic stability ([Bousquet and Elisseeff, 2002], [Feldman and Vondrak, 2019], [Bousquet et al., 2020]). ここで、一様一般化境界は、[wang et al., 2019], [lei et al., 2020]において、計量学習の線形の場合をアルゴリズム安定性の枠組みで研究した([bousquet and elisseeff, 2002], [feldman and vondrak, 2019], [bousquet et al., 2020])。 0.69
stability, and consequently generalization bounds, were obtained for an appropriately regularized empirical risk minimization (ERM) procedure. 適度に正規化された経験的リスク最小化 (erm) の手順では安定性と一般化限界が得られた。 0.66
We note that these methods rely strongly on the (uniform) convexity of the underlying problem, and are unlikely to be generalized to non linear settings. これらの手法は基礎となる問題の(一様)凸性に強く依存しており、非線型な設定に一般化する可能性は低い。 0.77
In [Bellet and Habrard, 2015],[Christmann and Zhou, 2016], linear metric learning was studied in the framework of algorithmic robustness, [Xu and Mannor, 2012]. 線形メトリック学習は, [bellet and habrard, 2015] [christmann and zhou, 2016] において, [xu and mannor, 2012] アルゴリズム的ロバストネスの枠組みで研究された。 0.79
In these works, Finally, uniform bounds for the linear case were studied in [Verma and Branson, 2015], and similar results for the version of risk as in (7) were obtained in [Cao et al., 2016]. これらの作品では 最後に, [verma and branson, 2015] において線形ケースの一様境界について検討し, [cao et al., 2016] において (7) のリスクバージョンについても同様の結果を得た。 0.70
In particular it was shown in [Verma and Branson, 2015] that 特に[Verma and Branson, 2015]に掲載されました。 0.73
Rn (F) ≤ b2 supA∈F∗ (cid:107)AAt(cid:107 )F Rn (F) ≤ b2 supA∈F\ (cid:107)AAt(cid:107 )F 0.78
√ k n . (8) √ k n . (8) 0.85
One can show that both (4) and (5) can be derived from this bound using known matrix norm inequalities. (4) と (5) の両方が既知の行列ノルムの不等式を用いてこの境界から導出できることが示せる。 0.75
The bound (8) itself is derived in [Verma and Branson, 2015] using a relatively short elegant argument involving only the Cauchy Schwartz inequality. 8) 自身は[Verma and Branson, 2015] においてコーシー・シュワルツの不等式のみを含む比較的短いエレガントな議論を用いて導かれる。 0.70
However, this argument can be applied only when φ is the identity. ただし、この引数は φ が ID である場合にのみ適用できます。 0.77
Similarly to the situation in classification, for the non-linear settings other arguments are required. 分類の状況と同様に、非線形の設定では他の引数も必要となる。 0.73
j=1 |vj|p(cid:17)1/p (cid:16)(cid:80)m (cid:13)(cid:13)(cid :13)(cid:16)(cid:107 )A·1(cid:107)p , . j=1 |vj|p(cid:17)1/p (cid:16)(cid:80)m (cid:13)(cid:13)(cid :13)(cid:16)(cid:107 )A·1(cid:107)p , 0.66
. . ,(cid:107)A·k(cid:107)p (cid:17)(cid:13)(cid :13)(cid:13)s . . ,(cid:107)A·k(cid:107)p (cid:17)(cid:13)(cid :13)(cid:13)s 0.82
4 Notation For a vector v = (v1, . 4 表記 ベクトル v = (v1, .) の場合。 0.81
. . , vm) ∈ Rm, the (cid:96)p norm is denoted by (cid:107)v(cid:107)p = . . . , vm) ∈ Rm, (cid:96)pノルムは (cid:107)v(cid:107)p = で表される。 0.83
For a matrix A ∈ Rd×k, and 1 ≤ p, s ≤ ∞, denote (cid:107)A(cid:107)p ,s = . 行列 A ∈ Rd×k と 1 ≤ p, s ≤ ∞ に対して (cid:107)A(cid:107)p ,s = . と表す。 0.86
That is, one first computes the p-th norm of the columns and then the s-th norm of the vector of these norms. すなわち、まず列の p 番目のノルムを計算し、次にこれらのノルムのベクトルの s 番目のノルムを計算する。 0.60
Note that 注意 0.42
(cid:107)A(cid:107)2 ,2 = (cid:107)A(cid:107)2 is the Frobenius norm. (cid:107)A(cid:107)2 ,2 = (cid:107)A(cid:107)2 はフロベニウスノルムである。 0.71
Denote by (cid:107)A(cid:107)o p the spectral norm of A. A のスペクトルノルムは (cid:107)A(cid:107) で表される。 0.78
Throughout φ : R → R will denote the non-linearity, with Lipschitz constant (cid:107)φ(cid:107)Lip and such that φ(0) = 0. φ : r → r は、リプシッツ定数 (cid:107) φ(cid:107)lip を持つ非線形性を表し、 φ(0) = 0 となる。 0.86
The ε covering number of a set A ⊂ Rn, denoted N (A, ε) is the minimal size of a set B ⊂ A such that for every x ∈ A there is y ∈ B s.t. 集合 A (A, ε) の ε 被覆数 N (A, ε) は、すべての x ∈ A に対して y ∈ B s.t が存在するような集合 B (A, ε) の最小サイズである。 0.86
(cid:107)x − y(cid:107)2 ≤ ε. (cid:107)x − y(cid:107)2 ≤ ε。 0.88
The Rademacher complexity of a set F ⊂ Rn is defined by 集合 F > Rn のラデマッハ複雑性は、定義される。 0.64
R (F) = 1 n R (F) = 1n 0.80
Eε sup f∈F Eε sup f∈F 0.67
εifi (9) n(cid:88) εifi (9) n(cid:88) 0.82
i=1 we set Rn (F) := R(cid:0)F|x,x(cid:48)(cid:1) where F|x,x(cid:48) ⊂ Rn is the i=1 Rn (F) := R(cid:0)F|x,x(cid:48)(cid:1) を F|x,x(cid:48) とする。 0.71
where εi are independent Bernoulli variables with If F is a family of P (εi = 1) = P (εi = −1) = 1 2 . εi を独立ベルヌーイ変数とし、F を P (εi = 1) = P (εi = −1) = 1 2 の族とする。 0.75
functions rather than a subset of Rn, as in (2), then restriction of F to the training set (see also Section 5.1). Rn の部分集合ではなく、(2) の場合のように、F を訓練集合に制限する(節 5.1 も参照)。 0.70
We use the standard notation O(·) and Ω(·) for upper bounded and equivalent, respectively, up to absolute constants. 標準表記法 O(·) と Ω(·) は、それぞれ上界および同値に対して絶対定数まで用いられる。 0.69
O(·) will denote upper boundedness up to absolute constants and logarithmic terms. o(·) は絶対定数と対数項まで上の有界性を表す。 0.70
5 Results In Section 5.1 we sate the sparse regime bound, Theorem 1, and provide an overview of the proof. 5結果 第5.1節では、スパース状態境界である定理1を測り、証明の概要を述べる。 0.72
The full proof is given in Supplementary Material Section A. 完全な証明は補助材料セクションAで与えられる。 0.64
We also derive Corollary 3, which is a version of the bounded amplification bound, but with an additional k factor. また、有界増幅境界(bounded amplification bound)のバージョンであるが、追加のk因子を持つcorollary 3も導出する。 0.67
Both proofs of the non sparse bound apply Corollary 3 with smaller values of k. 二つの非スパース境界の証明は、より小さい k の値を持つ共役 3 を適用できる。 0.56
√ In Section 5.2 we state the bounded amplification result, Theorem 4. √ 第5.2節では、有界増幅結果、定理4を述べる。 0.72
As discussed in Section 1.3, we give two proofs for Theorem 4, the first of which is given in Supplementary Material Section C. We then discuss the dimension reduction argument and prove the fundamental underlying approximation result, Lemma 5. 第1.3節で述べたように、第4章の2つの証明を与える。第1章は補足物質セクションCで与えられる。その後、寸法減少論を議論し、基本となる近似結果であるLemma 5を証明する。 0.64
The derivation of the Rademacher complexity bound from Lemma 5 is given in Supplementary Material Section D. Lemma 5 から結合した Rademacher の複雑さの導出は、補足物質セクション D で与えられる。 0.73
5.1 Sparse Case 5.1 スパースケース 0.64
We use the setting described in Section 1. 第1節で述べた設定を使用する。 0.69
Assume that we are given feature pairs {(xi, x(cid:48) i=1 ∈ Rd × 特徴対 {(xi, x(cid:48) i=1 ∈ rd × と仮定する。 0.80
i)}n J k a = i)}n J k a = 0.85
6 Rd, where each pair was sampled independently from some distribution on such pairs. 6 Rdは、各ペアがそのようなペアのいくつかの分布から独立してサンプリングされた。 0.69
Note that there may be dependence inside pairs, i.e. ペアの内部に依存性があるかもしれないことに注意。 0.60
xi may depend on x(cid:48) i, only the pairs themselves are assumed independent. xi は x(cid:48) i に依存し、ペア自身のみが独立であると仮定される。 0.68
These inputs are organized as two matrices, X, X(cid:48) ∈ Rn×d, with rows xi and x(cid:48) i respectively. これらの入力は2つの行列 X, X(cid:48) ∈ Rn×d で、それぞれ列 xi と x(cid:48) i で表される。 0.76
Define a shorthand for the normalized squared Euclidean norm on Rk, ζk(x, x(cid:48)) = 1 2 for x, x(cid:48) ∈ Rk. Rk 上の正規化二乗ユークリッドノルムのショートハンドを定義する、x, x(cid:48) ∈ Rk を x, x(cid:48) = 1 2 とする。 0.77
Let G ⊂ Rd×k be a set of matrices. G を Rd×k を行列の集合とする。 0.67
We will be interested in the family of vectors Fk(G) = FX,X(cid:48),k(G) 我々はベクトル Fk(G) = FX,X(cid:48),k(G) の族に関心を持つ。 0.72
i)(cid:1)n =(cid:8)(cid:0)ζk(φ(Atxi), φ(Atx(cid:48) i=1 | A ∈ G(cid:9) ⊂ Rn, i)(cid:1)n = (cid:8)(cid:0) φ(Atxi), φ(Atx(cid:48) i=1 | A ∈ G(cid:9) ^ Rn, 0.94
k (cid:107)x − x(cid:48)(cid:107)2 k (cid:107)x − x(cid:48)(cid:107)2 0.84
sets G of matrices. i)}n G を行列とする。 i)}n 0.75
for various In words, Fk(G) is the set of distance functions f (x, x(cid:48)) = ζk(φ(Atx), φ(Atx(cid:48)) induced by A ∈ G, restricted to the input {(xi, x(cid:48) i=1. 言い換えると、fk(g) は a ∈ g によって誘導される距離関数 f (x, x(cid:48)) = sk(φ(atx), φ(atx(cid:48)) の集合であり、入力 {(xi, x(cid:48) i=1 に制限される。 0.86
As discussed in Section 2, bounds on R (Fk(G)) imply generalization bounds for metric learning with matrices in G. Theorem 1. 第2節で議論されているように、R (Fk(G)) 上の境界は G の行列による計量学習の一般化を暗示する。 0.66
Given a, a(cid:48) > 0, set J k a,a(cid:48) = a, a(cid:48) > 0, set j k a,a(cid:48) = 0.90
(cid:110) A | A ∈ Rd×k,(cid:107)A(cid:107 )2,1 ≤ a,(cid:107)A(cid:107 )op ≤ a(cid:48)(cid:111) a,a(cid:48))(cid:1) ≤ O (cid:110) A | A ∈ Rd×k,(cid:107)A(cid:107 )2,1 ≤ a,(cid:107)A(cid:107 )op ≤ a(cid:48)(cid:111) a,a(cid:48))(cid:1) ≤ O 0.86
Assume that (cid:107)xi(cid:107) ≤ b for all i ≤ n. Then aa(cid:48)b2 (cid:107)φ(cid:107)2 n すべての i ≤ n に対して (cid:107)xi(cid:107) ≤ b と仮定すると、aa(cid:48)b2 (cid:107)φ(cid:107)2 n となる。 0.69
R(cid:0)Fk(J k R(cid:0)Fk(J k) 0.86
(cid:32) (cid:33) (cid:32) (cid:33) 0.78
(10) (11) √ (10) (11) √ 0.85
k Lip 1 n + . k 唇 1n + . 0.81
. We now briefly sketch the proof of Theorem 1. . 現在、我々はTheorem 1の証明を手短にスケッチしている。 0.74
The full proof is given in Supplementary Material Section A. 完全な証明は補助材料セクションAで与えられる。 0.64
As discussed in Section 1.3, to prove Theorem 1, we bound the covering numbers N (Fk(J k a,a(cid:48)), ε). 第1.3節で議論されているように、定理 1 を証明するために被覆数 N (Fk(J k a,a(cid:48)), ε) を束縛する。 0.68
The Rademacher complexity bound then follows using standard considerations, via the Dudley entropy integral bound. Rademacherの複雑性境界は、Dudleyエントロピー積分境界(英語版)を介して、標準的な考察を用いて従う。 0.48
To bound N (Fk(J k to bound N (Fk(J k)) 0.93
a,a(cid:48)), ε) we will use following covering lemma from [Bartlett et al., 2017], stated for the case of (cid:107)A(cid:107)2 ,1 norms. a,a(cid:48)), ε) (cid:107)A(cid:107)2 ,1 のノルムの場合、[Bartlett et al., 2017] の補題をカバーして使用します。 0.75
Lemma 2 ([Bartlett et al., 2017]). Lemma 2 ([Bartlett et al., 2017])。 0.61
For any a > 0, set 任意の a > 0 に対して set 0.80
(cid:110) A | A ∈ Rd×k,(cid:107)A(cid:107 )2,1 ≤ a (cid:110) A | A ∈ Rd×k,(cid:107)A(cid:107 )2,1 ≤ a 0.87
(cid:111) ⊂ Rd×k, (落語111) > Rd×k, 0.76
(12) (12) 0.85
and for any X ∈ Rn×d and a set of matrices G ⊂ Rd×k set XG = {XA | A ∈ G} ⊂ Rn×k. そして任意の X ∈ Rn×d および行列 G の集合に対して、Rd×k 集合 XG = {XA | A ∈ G} は Rn×k である。 0.89
Then for any ε > 0, 任意の ε > 0 に対して。 0.72
log N (XJ k log N (XJ k) 0.98
a , ε) ≤ a2 (cid:107)X(cid:107)2 a , ε) ≤ a2 (cid:107)X(cid:107)2 0.88
2 ε2 log (2dk) . 2 ε2 log (2dk)。 0.84
(13) (cid:8)(XA, X(cid:48)A) | A ∈ J k (13) (cid:8)(XA, X(cid:48)A) | A ∈ J k 0.91
The proof of this Lemma in [Bartlett et al., 2017] is based on Maurey’s Lemma, similarly to the arguments in [Zhang, 2002],[Bartlett, 1998]. この Lemma in [Bartlett et al., 2017] の証明は、[Zhang, 2002],[Bartlett, 1998] の議論と同様、Maureyの Lemma に基づいている。 0.71
We note that one can instead directly estimate the supremum of the Rademacher process indexed by XJ k a . 代わりに、XJ k a {\displaystyle XJk} でインデックス付けされた Rademacher プロセスの上限を直接推定できる。 0.72
Then Sudakov minoration, [Vershynin, 2018], would yield a slight improvement upon (13), with no d dependence inside the logarithm. そして、[vershynin, 2018]のスダコフのマイノリゼーションは、対数内部にd依存せずに(13)に対してわずかに改善する。 0.68
Next, define a set of n × 2k matrices Z by Z = {φ(z) | z ∈ Z} where φ is applied coordinatewise, and let ˆζk : Rd×2k → Rn be the mapping that applies ζk to the rows of elements in Rd×2k. 次に、n × 2k 行列 Z の集合を Z = {φ(z) | z ∈ Z} で定義し、φ を座標的に適用し、 φk : Rd×2k → Rn を Rd×2k の要素の列に sk を適用する写像とする。 0.86
Observe that by definition, Fk(J k a,a(cid:48)) = ˆζk (φZ). 定義では Fk(J k a,a(cid:48)) = φZ である。 0.68
Now, using Lemma 2, we can bound N (Z, ε). 現在、Lemma 2 を使って N (Z, ε) をバインドすることができる。 0.72
Then using Lipschitzity of the mappings Z (cid:55)→ φZ and ˆζk, this translates to a bound on N (Fk(J k すると、写像 Z (cid:55) → φZ および φk のリプシッツ性を用いて、これは N (Fk(J k) 上の有界となる。 0.67
a,a(cid:48)(cid:9) ⊂ Rn×2k. a,a(cid:48)(cid:9) = Rn×2k。 0.74
Let φZ := a,a(cid:48)), ε). φZ := a,a(cid:48)), ε) である。 0.80
We now consider the bounded amplification case 現在我々は有界増幅事件を考える 0.60
Corollary: Given a > 0, set Corollary: a > 0 をセットします。 0.78
(cid:110) (cid:111) A | A ∈ Rd×k,(cid:107)A(cid:107 )2,∞ ≤ a (cid:110) (cid:111) A | A ∈ Rd×k,(cid:107)A(cid:107 )2,∞ ≤ a 0.95
Gk a = (14) Corollary 3. Gk a = (14)第3巻。 0.78
Assume that (cid:107)xi(cid:107) ≤ b for all i ≤ n. Then for the set Gk すべての i ≤ n に対して (cid:107)xi(cid:107) ≤ b と仮定する。 0.88
a defined by (14) we have 定義されている(14) 0.65
. R(cid:0)Fk(Gk . R(cid:0)Fk(Gk) 0.85
a )(cid:1) ≤ O a )(cid:1) ≤ O 0.94
(cid:32) a2b2 (cid:32) a2b2 0.63
1 n + √ k (cid:107)φ(cid:107)2 √ n 1n + k (cid:107)φ(cid:107)2 ^ n 0.79
Lip . (15) The proof is given in Supplementary Material Sec- 唇 . (15) 補足資料 sec で証明が与えられる- 0.77
tion B. 5.2 Bounded Amplification Case Theorem 4. 背番号B。 5.2 Bounded Amplification Case Theorem 4 0.67
Assume that (cid:107)xi(cid:107) ≤ b for all i ≤ n. Then for the set Gk すべての i ≤ n に対して (cid:107)xi(cid:107) ≤ b と仮定する。 0.88
a defined by (14) we have 定義されている(14) 0.65
R(cid:0)Fk(Gk R(cid:0)Fk(Gk) 0.84
a )(cid:1) ≤ O a )(cid:1) ≤ O 0.94
(cid:32) 1/n + (cid:32) 1/n+ 0.73
a2b2 (cid:107)φ(cid:107)2 n a2b2 (cid:107)φ(cid:107)2 n 0.72
√ Lip (cid:33) √ 唇 (cid:33) 0.80
(cid:33) The proof of this result is given in Section C of the supplementary material. (cid:33) この結果の証明は補足資料のC節に記載されている。 0.75
We will now discuss a dimension reduction proof, which yields a somewhat weaker, but still dimension independent bound: 次元還元証明(英語版)について議論し、これは幾分弱いが次元独立な境界を与える。
訳抜け防止モード: ここでは次元還元証明について論じる。 より弱く、しかしまだ次元の独立な境界を産み出します
R(cid:0)Fk(Gk R(cid:0)Fk(Gk) 0.84
a )(cid:1) ≤ O a )(cid:1) ≤ O 0.94
(cid:32) (cid:33) (cid:32) (cid:33) 0.78
1/n + a2b2 (cid:107)φ(cid:107)2 n1/4 1/n+ a2b2 (cid:107)φ(cid:107)2 n1/4 0.65
Lip . (17) √ 唇 . (17) √ 0.83
l. ≤ √ (cid:16) l. ≤ √ (cid:16) 0.83
≤ 1/ (cid:17)2 √ ≤ 1/ (cid:17)2 0.90
(cid:13)(cid:13)(cid :13)f − ˆf (cid:13)(cid:13)(cid :13)∞ (cid:13)(cid:13)(cid :13)f−1(cid:13)(cid:13)(ci d:13)∞ 0.73
To make notation more compact, for any l > 0 denote Fl = Fl(Gl a). 表記をよりコンパクトにするために、任意の l > 0 に対して fl = fl(gl a) を表す。 0.67
The main step of the proof of (17), Lemma 5, is to show that every f ∈ Fk can be approximated by ˆf ∈ Fl for any l ≤ k, such that, roughly, l. This can be equivalently restated as follows: The set Fl, of l-dimensional dis√ tance functions, approximates any Fk up to 1/ l, independently of k. We refer to this property as luniform approximability, with rate 1/ Lemma 5. (17) リーマ 5 の証明の主ステップは、すべての f ∈ Fk が任意の l ≤ k に対して任意の f ∈ Fl によって近似できることを示すことである。これは次のように等しく補うことができる: l-次元離散関数の集合 Fl は、k から独立して任意の Fk を 1/l まで近似する。
訳抜け防止モード: 17 ) Lemma 5 の証明の主なステップは、すべての f ∈ Fk が任意の l ≤ k, に対して任意の f ∈ Fl によって近似できることを示すことである。 これは次のように等価に補える: 集合 Fl, である。 l の次元離散距離関数、任意の Fk を 1/l まで近似します。 kから独立して、この性質をルニフォーム近似性と呼びます。 レート1/レマ5で。
For any l ≤ k, for any f ∈ Fk, there is ˆf ∈ Fl such that 任意の l ≤ k に対して、任意の f ∈ fk に対して、f ∈ fl が存在する。 0.79
ab(cid:107)φ(cid:107)Lip √ ab(cid:107)φ(cid:107)Lip ? 0.73
(cid:13)(cid:13)(cid :13)f − ˆf (cid:13)(cid:13)(cid :13)∞ a . (cid:13)(cid:13)(cid :13)f − sf (cid:13)(cid:13)(cid :13)∞ a。 0.74
For j ≤ k set rj = Proof. j ≤ k に対して rj = Proof をセットする。 0.73
Fix i ≤ n, and A ∈ Gk (cid:80)k (φ(Atxi)j − φ(Atx(cid:48) i)j)2 and denote r = (r1, . i ≤ n と A ∈ Gk (cid:80)k (φ(Atxi)j − φ(Atx(cid:48) i)j)2 を固定し、r = (r1, ) とする。 0.92
. . , rk) ∈ Rk. . . rk) ∈ Rk である。 0.84
Set ¯r = 1 j=1 rj. r = 1 j=1 rj をセットする。 0.61
We have by definition that ζk(φ(Atxi), φ(Atx(cid:48) i)) = ¯r. 定義によれば、 φ(φ(Atxi), φ(Atx(cid:48) i)) = ~r である。 0.81
To obtain an approximation in Rl, we will choose l coordinates rj at random and consider the restriction to these coordinates. Rl の近似を得るために、l 座標 rj をランダムに選択し、これらの座標に対する制限を考える。 0.76
For l > 0 let π : Rk → Rl be a random coordinate projection. l > 0 に対して π : Rk → Rl をランダム座標射影とする。 0.79
That is, choose indices i1, . つまり、インデックスi1, を選択する。 0.78
. . , il independently at random from {1, . . . il は {1, il から独立してランダムである。 0.80
. . , k} and set π(v) = (vi1 , . . . , k} とセット π(v) = (vi1 , .) である。 0.82
. . , vil) for all v ∈ Rk. . . すべての v ∈ Rk に対して , vil)。 0.84
Denote by ˆr the empirical average ˆr = πr = 1 l Note that for every j ≤ k, φ((cid:104)A·j, xi(cid:105)) ≤ ab(cid:107)φ(cid:107)Lip Lip. j ≤ k に対して、任意の j ≤ k に対して φ((cid:104)a·j, xi(cid:105)) ≤ ab(cid:107) φ(cid:107)lip lip と記す。 0.77
Therefore by Bern- したがって、bern- 0.48
and thus (cid:107)r(cid:107)∞ ≤ a2b2 (cid:107)φ(cid:107)2 (cid:18) stein’s inequality, [Boucheron et al., 2013], そして(cid:107)r(cid:107)∞ ≤ a2b2(cid:107)φ(cid:107)2(cid:18) steinの不等式である[Boucheron et al., 2013] 0.75
j=1(πr)j. (cid:80)l j=1(πr)j。 (cid:80)l 0.82
log 4n (18) log 4n (18) 0.87
l k . (cid:16) l k . (cid:16) 0.83
Pπ (|ˆr − ¯r| > t) ≤ 2exp t ≤ 2exp の Pπ である。 0.72
−l · t2/ ab(cid:107)φ(cid:107)Lip -l·t2/ ab(cid:107)φ(cid:107)Lip 0.69
(cid:17)4(cid:19) (cid:17)4(cid:19) 0.78
. . (16) (19) Finally, recall that r depends on i. . . (16) (19) 最後に、r が i に依存することを思い出す。 0.80
Repeating this for 7 これを繰り返す 7 0.72
every i ≤ n and using the union bound, すべての i ≤ n と 結合結合を使って 0.75
(cid:19) (cid:18) (cid:19) (cid:18) 0.78
(cid:18) (cid:16) (cid:18) (cid:16) 0.78
(cid:17)4(cid:19) (cid:17)4(cid:19) 0.78
ab(cid:107)φ(cid:107)Lip (20) ab(cid:107)φ(cid:107)Lip (20) 0.90
particular, we would still have k factor improvement over Theorem 1. 特に、Theorem 1.1よりもkファクタが改善されるでしょう。 0.68
On the other hand, it seems unlikely that the special properties of ρ can be pushed . 一方、ρ の特別な性質が押し出される可能性は低いようだ。 0.63
further, to have only (cid:107)·(cid:107)2,∞ dependence also in lower layers. さらに、下層層にも(cid:107)·(cid:107)2,∞依存性のみを持つ。 0.80
√ Pπ max i≤n √ Pπ マックスi≤n 0.75
|ˆr − ¯r| > t t > t である。 0.47
≤ 2nexp −l · t2/ ≤ 2nexp -l·t2/ 0.71
(ab(cid:107)φ(cid:107)Lip)2√ (ab(cid:107)φ(cid:107)Lip)2 0.86
√ log 4n l √ log 4n l 0.86
Choosing t0 = , the right handside of (20) is strictly smaller than 1. t0 = を選択すると、(20) の右辺は 1 より厳密に小さい。 0.86
Therefore there is a choice π such that for all i ≤ n, |ˆr − ¯r| ≤ t0. したがって、すべての i ≤ n に対して |r − s r| ≤ t0 となる選択 π が存在する。 0.80
Finally, given A ∈ Rd×k and π = (i1, . 最後に、A ∈ Rd×k と π = (i1, ) が与えられる。 0.71
. . , il), denote by Aπ ∈ Rd×l the restriction of A to π, Aπ = a then Aπ ∈ Gl (A·i1 , . . . Aπ ∈ Rd×l は A to π, Aπ = a then Aπ ∈ Gl (A·i1 , .) の制限を表す。 0.87
. . , A·il). . . A・il)。 0.81
Note that if A ∈ Gk a. A ∈ Gk a であれば注意。 0.81
If one denotes fA(i) = ζk(φ(Atxi), φ(Atx(cid:48) i)), then we have shown that for the particular π found above maxi≤n |fA(i) − fAπ(i)| ≤ t0, thereby completing the proof. fA(i) = ~k(φ(Atxi), φ(Atx(cid:48) i) と書くと、maxi≤n |fA(i) − fAπ(i)| ≤ t0 上の特定の π に対して証明が完了することを示した。 0.84
To prove (17) from Lemma 5, Lemma 5 から (17) を証明する。 0.75
to note that R(cid:0)Fk(Gk (cid:110) f − ˆf | f ∈ F(cid:111) 注意すべきなのは R(cid:0)Fk(Gk (cid:110) f − sf | f ∈ F(cid:111) 0.61
a )(cid:1) ≤ R(cid:0)Fl(Gl a )(cid:1) ≤ R(cid:0)Fl(Gl) 0.86
it is suffices for any l < k one can write 書くことができる任意の l < k に対して十分である 0.71
a)(cid:1)+R (∆Fk,l) where ∆Fk,l = a)(cid:1)+R(sFk,l) ここで sFk,l = 0.87
. The first term can be bounded by Corollary 3, the second by Lemma 5, and an appropriate choice of l yields (17). . 第1項は Corollary 3 で、第2項は Lemma 5 で、 l の適切な選択は (17) である。
訳抜け防止モード: . 第1項は Corollary 3 で、第2項は Lemma 5 で区切ることができる。 そして l yields (17 ) の適切な選択。
The full details are given in Supplementary Material Section D. 詳細は補足資料節Dに記載されている。 0.63
We conclude this Section with a brief discussion of the multi-layer networks and of the role of the normalization by k in (1). このセクションでは、多層ネットワークとkによる正規化の役割について簡単に説明します(1)。 0.66
Remark 6. The special feature of metric learning compared to a regular classification problem is the particular structure of the loss. 備考6。 正規分類問題と比較して、メトリック学習の特別な特徴は、損失の特定の構造である。 0.67
That is, that the loss depends on the features only through the metric ρ. つまり、損失は計量ρによってのみ特徴に依存する。 0.67
In Theorem 1, however, we have only exploited the Lipschitzity of ρ. しかし、Theorem 1 では、ρ のリプシッツ性しか利用していない。 0.72
We therefore note that it is possible to obtain a multi-layer version of Theorem 1 simply by replacing in our proof the single layer covering numbers bound (13) with a multi-layer bound ([Bartlett et al., 2017], Theorem 3.3). したがって、定理 1 の多層バージョンは、この証明において、(13) に束縛された数をカバーする単層を多層束縛([bartlett et al., 2017], theorem 3.3)に置き換えるだけで得られることに注意する。 0.80
Moreover, since both our proofs of Theorem 4 eventually invoke Theorem 1 for low k, it is clearly possible to also extend Theorem 4 to the multilayer case. さらに、どちらの証明も最終的に低 k に対して Theorem 1 を呼び出すので、明らかに Theorem 4 を多層体の場合へ拡張することも可能である。 0.80
In that case, the bound would depend on the (cid:107)·(cid:107)op and (cid:107)·(cid:107)2,1 norms of all the layers except the last one, in a way similar to Theorem 1.1, [Bartlett et al., 2017]. その場合、境界は (cid:107)·(cid:107)op と (cid:107)·(cid:107)2,1 norms of all the layers without the last one, in a similar such to theorem 1.1, [bartlett et al., 2017] に依存する。 0.87
The dependence on the last layer, however, would be only through (cid:107)·(cid:107)2,∞. しかし、最後の層への依存は (cid:107)·(cid:107)2,∞ のみである。 0.78
In 8 Remark 7. As noted earlier, the normalization by k in (1) (or in the definition of ζk) is crucial to the fact that (5) is dimension free. 内 8 第7話。 先に述べたように、(1) における k による正規化は (5) が次元自由であるという事実にとって重要である。 0.68
However, this is a natural normalization, ensuring that the values of ρk,f∗ are of the same magnitude ( 0 ≤ ρk,f∗ ≤ 4(cid:107)A(cid:107) 2 2,∞ b2) independently of k, rather than explode with k. Note that if one normalized by anything of larger order than k, then the situation would have been degenerate, since ρk,f∗ values would simply be vanishing as k grows. しかし、これは自然正規化であり、ρk,f の値が k で爆発するのではなく、k から独立して同じ大きさ (0 ≤ ρk,f ≤ 4(cid:107)A(cid:107) 2 2,∞ b2) であることを保証する。
訳抜け防止モード: しかし、これは自然な正規化であり、ρk, f∗ の値が同じ大きさであることを保証する。 (0 ≤ ρk, f∗ ≤ 4(cid:107)A(cid:107) 2,∞ b2 ) kで爆発するよりむしろkで独立して。 kより大きい順序で正規化されたもの それ以来 状況は悪化していたでしょう ρk, f∗ の値は、k が成長するにつれて単に消える。
However, with normalization by k this is not the case. しかし、k による正規化では、これは当てはまらない。 0.68
The values of ρk,f∗ stay bounded but non-vanishing, while the number of parameters grows with k. Equivalently, while the magnitude of the values of ρk,f∗ stays bounded, the family of functions Fk(Gk a ) becomes strictly larger as k grows. ρk,f∗ の値は有界だが非有界であり、パラメータの数は k と共に増加するが、ρk,f∗ の値の大きさは有界であり、関数 fk(gk a ) の族は k が成長するにつれて厳密に大きくなる。 0.74
Thus the fact that the Rademacher complexity (5) is bounded independently of k is non-trivial. したがって、ラデマチャー複雑性(5) が k から独立に有界であるという事実は、非自明である。 0.51
6 Experiments In this Section we empirically make the following observations: (a) The bounded amplification regime introduced in this paper, where (cid:107)A(cid:107)2 ,∞ is bounded while (cid:107)A(cid:107)2 ,1 and (cid:107)A(cid:107)o p grow with k, occurs naturally in practice. 6 実験 このセクションでは、(a)本論文で導入された有界増幅機構(cid:107)A(cid:107)2 ,∞は(cid:107)A(cid:107)2 ,1および(cid:107)A(cid:107)A (cid:107)opはkと共に自然に成長する。 0.77
For instance, we observe this on the MNIST data, trained without any regularization terms. 例えば、正規化条件なしで訓練されたMNISTデータでこれを観察します。 0.72
(b) The generalization gap, i.e. (b)一般化ギャップ、すなわち 0.61
the difference between train and test loss, does not grow with k, for k in the range from 1 to 5000, as suggested by the theory. 列車と試験損失の違いは k では増加しない 理論で示唆されているように 1 から 5,000 の範囲で k では 0.82
In other words, we can increase k arbitrarily, without risking overfitting. 言い換えれば、過度に適合するリスクを冒さずに k を任意に増加させることができる。 0.52
(c) The non-linear embeddings, even with a single layer, can perform better than the linear ones. (c) 単層であっても、非線形埋め込みは線形埋め込みよりも優れた性能を発揮する。 0.81
Note that this point is not necessarily completely obvious. この点は必ずしも完全には明らかではない。 0.76
The linear embeddings are fairly powerful, and can, for instance, do things such as removing coordinates that are irrelevant to the label, thereby improving the relation between the metric and the label. 線形埋め込みはかなり強力であり、例えば、ラベルと無関係な座標を取り除いて、メートル法とラベルの関係を改善するといったことができる。 0.63
Nevertheless, we find that on both our datasets, a sigmoid non-linearity improves the performance of the embedding. それにもかかわらず、両方のデータセットにおいて、シグモイド非直線性は埋め込みの性能を向上させる。 0.60
(a) Losses (b) (cid:107)A(cid:107)2 ,∞, (cid:107)A(cid:107)2 ,1 /k and (cid:107)A(cid:107)o p / Weight Norms, Sigmoid Embedding. (a)損失 b) (cid:107)A(cid:107)2 ,∞, (cid:107)A(cid:107)2 ,1 /k, (cid:107)A(cid:107)o p / Weight Norms, Sigmoid Embedding。 0.79
√ k Figure 2: MNIST Experiment ‐k 図2:MNIST実験 0.68
(c) Same/Different Class Components of the Loss (c) 損失の同一/異なるクラスコンポーネント 0.89
We consider two classical datasets, the MNIST dataset of handrwitten digits [mnist Dataset, ], and the 20newsgroups dataset [20newsgoups Dataset, ], which consists of newsgroups emails, labeled according to the group. 私たちは、2つの古典的なデータセット、手書き数字のMNISTデータセット[mnist Dataset, ]、およびグループに従ってラベル付けされたニュースグループ電子メールで構成される20newsgroupsデータセット[20newsgoups Dataset, ]を検討します。
訳抜け防止モード: 我々は、2つの古典的データセット、手書き桁のMNISTデータセット[mnist Dataset]を考える。 20newsgoupsデータセット [20newsgoups Dataset, ]。 グループによってラベル付けされた ニュースグループによるメールです
To make illustrations simpler, we restrict the 20newsgroups to the first 10 labels. イラストを簡単にするために、20Newsgroupsを最初の10のラベルに制限します。 0.70
While MNIST is generally nicely behaved, the 20newgroups is not. MNISTは一般的に素晴らしく振る舞うが、20Newgroupsはそうではない。 0.68
In particular, it consists of about n = 7500 samples in dimension d = 15000 > n, and this would require explicitly regularizing (cid:107)A(cid:107)2 ,∞. 特に、次元 d = 15000 > n の約 n = 7500 のサンプルからなり、(cid:107)a(cid:107)2 ,∞ を明示的に正規化する必要がある。 0.87
In all cases, we consider a single layer fully connected embedding, as in (3), where the activation function φ is either φ(x) = x (linear case) or φ(x) = σ(x) = 1 すべての場合において、活性化関数 φ は φ(x) = x (線型の場合) か φ(x) = σ(x) = 1 のいずれかである(3) のように、単層完全連結埋め込みを考える。 0.88
1+e−x . To perform the optimization, we sample feature/label pairs (x, l), (x(cid:48), l(cid:48)) independently from the train set, and minimize the loss using SGD on batches of such pairs, until convergence. 1+e−x。 最適化を行うために,列車セットから独立して特徴対 (x, l), (x(cid:48), l(cid:48)) をサンプリングし,そのような組のバッチにおけるsgdによる損失を収束まで最小化する。 0.61
The loss that we use is (cid:96)(x, x(cid:48), l, l(cid:48)) =9 · ReLU (ρ(x, x(cid:48))) · 1{l=l(cid:48)} 私たちが使う損失は (cid:96)(x, x(cid:48), l, l(cid:48)) = 9 · ReLU(ρ(x, x(cid:48)) · 1{l=l(cid:48)} 0.83
+ ReLU (D − ρ(x, x(cid:48))) · 1{l(cid:54)=l(cid:48)}, (21) where ρ(x, x(cid:48)) is the distance after the embedding, given by (1). + ReLU (D − ρ(x, x(cid:48)) · 1{l(cid:54)=l(cid:48)}, (21) ここで ρ(x, x(cid:48)) は、(1) で与えられる埋め込みの後の距離である。 0.94
This loss is a version of the loss (cid:96)λ S,D(ρ, y) introduced in Section 2, where the same class case is weighted by 9. この損失は、セクション2で導入された損失 (cid:96)λ S,D(ρ, y) のバージョンであり、同じクラスの場合の重み付けは9である。 0.80
Our datasets have 10 roughly balanced labels, and therefore the probability of the event l = l(cid:48) is about 1/10. 我々のデータセットはおよそ10のバランスの取れたラベルを持っているので、イベント l = l(cid:48) の確率は約1/10である。 0.64
Thus the multiplier 9 helps in giving similar weights to the separation l (cid:54)= l(cid:48) and the compression l = l(cid:48) conditions, enforced by the respective terms in (21). したがって、乗算器9は、分離l(cid:54)=l(cid:48)および圧縮l=l(cid:48)条件に類似した重みを与え、(21)の各項によって強制される。 0.74
For train or test evaluation, we sample the pairs (x, l), (x(cid:48), l(cid:48)) 列車評価または試験評価のために、ペア (x, l), (x(cid:48), l(cid:48) をサンプリングする。 0.78
9 from the train or test set, respectively, and compute the mean value of (cid:96)(x, x(cid:48), l, l(cid:48)) on these samples. 9 列車またはテスト セットからそれぞれ、およびこれらのサンプルの平均値 (cid:96)(x, x(cid:48), l, l(cid:48)) を計算します。 0.85
For MNIST we use the upper threshold D = 0.5, while for 20newsgroups we set D = 0.1. MNIST では上限 D = 0.5 を使用し、20newsgroup では D = 0.1 を設定する。 0.77
Each experiment was repeated 6 times, and every value in Figures 2, 3 is a mean over 6 outcome values. 各実験は6回繰り返され、図2、3のすべての値は6以上の結果値である。 0.74
Every value also has an error bar which indicates the magnitude of the standard deviation around the mean. すべての値には、平均の周りの標準偏差の大きさを示すエラーバーもあります。 0.73
However, in most cases, these bars are so small compared to the magnitude of the mean, that they are not visible in the figures. しかし、ほとんどの場合、これらのバーは平均の大きさと比較して非常に小さいため、数字には見えません。
訳抜け防止モード: しかし、ほとんどの場合、これらのバーは平均の大きさと比較して非常に小さいです。 それらは図で見えないこと。
Additional details on the experimental setting are given in Supplementary Material Section E. The full code that was used for the experiments is also provided as Supplementary Material. 実験設定のさらなる詳細は補足材料セクションeで述べられ、実験に使用された完全なコードも補足材料として提供される。 0.84
We now discuss each dataset separately. 各データセットを別々に議論します。 0.65
6.1 MNIST For MNIST, the feature dimension is d = 28 · 28 = 784. 6.1 MNIST MNIST の場合、特徴次元は d = 28 · 28 = 784 である。 0.88
As mentioned earlier, in this experiment we do not use any regularization terms on the embedding weight matrix A. 先に述べたように、この実験では埋め込み重み行列 A の正規化項は一切使用しない。 0.70
The results are shown in Figure 2. 結果は図2に示されています。 0.80
First, Figure 2b shows the norms of A after the convergence of the optimization, for the sigmoid embeddings. 第一に、図 2b は最適化の収束後の A のノルムを示し、シグモイド埋め込みである。 0.78
The (cid:107)A(cid:107)2 ,∞ is given by the green solid line, for values of k ranging from 1 to 5000. cid:107)A(cid:107)2, ∞ は 1 から 5000 までの k の値に対して緑色のソリッドラインによって与えられる。 0.85
The values of (cid:107)A(cid:107)2 ,1 /k and (cid:107)A(cid:107)o p / k are given by the dashed red and purple lines, respectively. (cid:107)A(cid:107)2 ,1 /k)と(cid:107)A(cid:107)o p/k)の値は、それぞれ赤線と紫線で与えられる。 0.78
The fact that all three lines remain of the same magnitude throughout the whole range of k means that the standard non reguilarized SGD optimization works in this case in the bounded amplification regime. すべての3行が k の範囲全体で同じ大きさのままであるという事実は、標準の非正規化 SGD 最適化がこの場合、有界増幅系で機能することを意味する。 0.72
That is, the √ 12345105010050010005 000K0. Train LossTest LossTrain Loss, LinearTest Loss, Linear12345105010050 010005000K3.54.04.55 .,i nfty) normL(2,1) norm / KL(op) norm / sqrt(K)1234510501005 0010005000K0.050.100 .150.200.25LossSame Class Loss, TestDiff. つまり... √ 1234510501005005000K 0.280.30LossTrain LossTest LossTrain Loss, LinearTest Loss, Linear12345105010050 05000K3. 06.5NormL(2,infty) normL(2,1) norm / KL(op) norm / sqrt(K)1234510100100 05000K0.050.100.200. 25LosSame Class Loss, TestDiff 0.60
Class Loss, TestSame Class Loss, Test, LinearDiff. Class Loss, TestSame Class Loss, Test, LinearDiff 0.73
Class Loss, Test, Linear クラス損失、テスト、線形。 0.74
(a) Losses (b) (cid:107)A(cid:107)2 ,∞, (cid:107)A(cid:107)2 ,1 /k and (cid:107)A(cid:107)o p / Weight Norms, Sigmoid Embedding. (a)損失 b) (cid:107)A(cid:107)2 ,∞, (cid:107)A(cid:107)2 ,1 /k, (cid:107)A(cid:107)o p / Weight Norms, Sigmoid Embedding。 0.79
√ k Figure 3: Newsgroups Experiment ‐k 図3:ニュースグループの実験 0.69
(c) Same/Different Class Components of the Loss (c) 損失の同一/異なるクラスコンポーネント 0.89
(cid:107)A(cid:107)2 ,∞ norm remains roughly bounded while (cid:107)A(cid:107)2 ,1 grows linearly with k and (cid:107)A(cid:107)o p grows linearly with √ k. The situation for the linear case is similar (see (cid:107)a(cid:107)2 ,∞ノルムは大まかに有界であり、一方 (cid:107)a(cid:107)2 ,1 は k で線型に成長し (cid:107)a(cid:107)o p は s k で線型に成長する。 0.75
Figure 4a in the Supplementary Material). Next, we consider the losses on train and test sets, Figure 2a. 補足資料の図4a) 次に、列車とテストセットの損失、図2aを検討します。 0.66
For the sigmoid embedding, the blue solid line is the loss evaluated on the train set, while the blue dashed line is the test loss. シグモイドの埋め込みでは、青い固体線は列車セットで評価された損失であり、青い破断線は試験損失である。 0.66
Observe that the lines are practically identical as k grows. 実数直線は k が成長するのと実質的に同じである。 0.59
There is no deterioration of the generalization gap as k grows. k が成長するにつれて一般化ギャップは悪化しない。 0.68
This may appear somewhat counterintuitive at first. これは最初はやや直感的に見えるかもしれない。 0.53
However, according to Figure 2b, we are in the nonsparse, bounded (cid:107)A(cid:107)2 ,∞ norm regime. しかし、図2bによると、我々は非スパース有界(cid:107)A(cid:107)2 ,∞ノルム状態にある。 0.73
Therefore our results, in particular Theorem 4, suggest that indeed the generalization gap should be independent of k. Similar picture occurs for the linear case, as shown by the orange lines. したがって、この結果、特に定理4は、実のところ一般化ギャップは k とは独立であるべきであることを示唆している。
訳抜け防止モード: したがって、この結果、特に Theorem 4 は、実際、一般化ギャップは k から独立であるべきであることを示唆している。 オレンジ色の線が示すように
Note that the non-linear loss is considerably lower than the linear one. 非線型損失は線形損失よりもかなり小さいことに注意。 0.73
Finally, since the loss expression (21) is rather involved, it may be unclear from the raw values of the loss whether there is actually any good separation of the labels in the learned metric. 最後に、損失表現(21)がかなり関係しているため、学習されたメトリクスにラベルが適切に分離されているかどうかの損失の生値から不明確である可能性がある。 0.76
In Figure 2c we show explicitly the same class and different class components of the loss. 図2cでは、損失の同じクラスと異なるクラスコンポーネントを明確に示します。 0.82
That is, for the sigmoid embedding, the solid blue line in Figure 2c is the average of the quantity ReLU (ρ(x, x(cid:48))) over pairs of features (x, x(cid:48)) on test set for which l = l(cid:48) (that is, conditioned on the fact that labels are equal), while the dashed blue line is the average of ReLU (0.5 − ρ(x, x(cid:48))) on pairs with l (cid:54)= l(cid:48). つまり、図2cのソリッドブルーラインは、l(cid:54)= l(cid:48) のペア上の l = l(cid:48) (すなわち、ラベルが等しくなるという事実を条件とする) のテストセット上の特徴 (x, x(cid:48)) のペア上の量 ReLU (ρ(x, x(cid:48)) の平均であり、ダッシュブルーラインは l(cid:54)= l(cid:48) のペア上の ReLU (0.5 − ρ(x, x(cid:48)) の平均である。 0.82
Thus for instance, for k = 10, at least on average, points with the same label are at distance したがって、例えば k = 10 の場合、少なくとも平均すると、同じラベルを持つ点が距離である。 0.86
0.07 while points with different labels are at distance 0.5 − 0.12 = 0.38. 0.07 異なるラベルを持つ点が0.5 − 0.12 = 0.38 である。 0.70
6.2 Newsgroups 6.2ニュースグループ 0.55
As mentioned earlier, the 20newsgrous dataset [20newsgoups Dataset, ] was restricted to the first 10 labels. 前述のように、20newsgrousデータセット[20newsgoups Dataset, ]は、最初の10ラベルに制限されていた。 0.73
Each email was represented as a bag-of-words vector over d = 15000 most common tokens in the dataset. 各電子メールは、データセットの一般的なトークンのd = 15000に対して、単語の袋のベクトルとして表現された。 0.55
Each vector was then normalized to have Euclidean norm 1. 各ベクトルはユークリッドノルム 1 を持つように正規化された。 0.67
This dataset contains 9640 samples, of which 20% were taken at random as the test set, leaving n = 7700 train samples. このデータセットには9640のサンプルが含まれており、うち20%はテストセットとしてランダムに撮られ、n = 7700の列車サンプルを残している。 0.64
Since d > n, one can in principle severely overfit the data even with k = 1. d > n なので、k = 1 でもデータを重大にオーバーフィットすることができる。 0.72
Thus one has to control the (cid:107)A(cid:107)2 ,∞ norm, which was achieved by adding the term 0.1 2,∞ to the loss (21) in the sigmoid case, and 1.0 2,∞ in the linear case. したがって、(cid:107)a(cid:107)2 ,∞ノルムを制御しなければならないが、これはシグモイドの場合の損失(21)に0.1 2,∞、線型の場合では1.0 2,∞を加えることで達成された。 0.78
The regularization values 0.1 and 1.0 above where chosen such as to yield the best test performance at k = 10 in their respective cases. 上述の正規化値0.1と1.0は、それぞれの場合においてk = 10で最高のテスト性能を得るように選択される。 0.72
d (cid:107)A(cid:107)2 d (cid:107)A(cid:107)2 d (cid:107)A(cid:107)2 d (cid:107)A(cid:107)2 0.83
The experiment results are shown in Figure 3, with plots similar to those of the MNIST dataset. 実験結果は図3に示され、MNISTデータセットのプロットに似ています。 0.76
In particular, we see in Figure 3b that while we enforce the bounded (cid:107)A(cid:107)2 ,∞ norm constraint with the regularization term, there was no sparsity, i.e. 特に図3bでは、正規化項で有界 (cid:107)a(cid:107)2 ,∞ のノルム制約を強制するが、スパーシティは存在しなかった。 0.63
(cid:107)A(cid:107)2 ,1 and (cid:107)A(cid:107)o p grew with k, as in the MNIST case. (cid:107)A(cid:107)2 ,1および(cid:107)A(cid:107)o pはMNISTの場合と同様にkで成長した。 0.71
The generalization gap, Figure 3a was considerable, but it was the same gap throughout the larger values of k (k ≥ 5). 一般化のギャップである図3aは相当であったが、 k (k ≥ 5) の大きい値全体で同じギャップがあった。 0.78
This can also be seen in Figure 3c – the values of the same class/different class expectations on the test set remain relatively constant over the これは図3cにも見られます – 同じクラス/異なるクラスの期待値がテストセット上でも比較的一定です。 0.77
10 12345105010050010005 000K0. 0.07LossTrain LossTest LossTrain Loss, LinearTest Loss, Linear12345105010050 010005000K20304050No rmL(2,infty) normL(2,1) norm / KL(op) norm / sqrt(K)1234510501005 0010005000K0.010.020 . ossSame Class Loss, TestDiff. 10 12345105010050050050 00K0. .07LossTrain LossTest LossTrain Loss, LinearTest Loss, Linear 12345501005005000K20 30404050NormL(2,inft y) normL(2,1) norm / KL(op) norm / sqrt(K)1234510505005 0010005000K0.010.020 . ossSame Class Loss, TestDiff 0.72
Class Loss, TestSame Class Loss, Test, LinearDiff. Class Loss, TestSame Class Loss, Test, LinearDiff 0.73
Class Loss, Test, Linear クラス損失、テスト、線形。 0.74
range of k. Recall that the test set for k = 50 was shown in Figure 1b, and corresponds to fairly good label separation, as can be expected from the values in Figure 3c. k の範囲は、k = 50 のテストセットが図 1b に示され、図 3c の値から期待できるように、かなり良いラベル分離に対応していることを思い出してください。 0.79
[Bartlett and Mendelson, 2002] Bartlett, P. L. and Mendelson, S. (2002). Bartlett and Mendelson, 2002] Bartlett, P. L. and Mendelson, S. (2002). 0.90
Rademacher and gaussian complexities: Risk bounds and structural results. Rademacher と gaussian complexities: リスク境界と構造結果。 0.72
J. Mach. Learn. J. Mach 学ぶ。 0.72
Res., 3. 7 Conclusion In this work we have provided the first uniform generalization guarantees for metric learning with a nonlinear embedding. 3枚目。 7 結論 本研究では,非線形埋め込みによる計量学習のための最初の一様一般化保証を提供する。 0.60
In particular, we have shown that dimension free generalization is possible in the nonsparse regime. 特に,非スパース系では次元自由一般化が可能であることが示された。 0.72
We believe that further study of the non sparse regime, and in particular understanding better in which other situations the non sparse regime occurs, and what are the associated bounds, would significantly advance our understanding overparametrized systems. 非スパース体制のさらなる研究、特に他の状況における非スパース体制のさらなる理解、および関連する境界は、我々の過度なパラメータ化システムに対する理解を著しく前進させるであろうと我々は信じている。 0.76
In addition, observe that almost any family of sets Ul ⊂ Rn , l ≥ 1, (given, say, trivial compactness constraints) has the l-approximability property, as introduced in Section 5.2, for some, necessarily vanishing, rate. さらに、Ul , Rn , l ≥ 1 (例:自明なコンパクト性制約) のほとんどすべての族が、ある必然的消滅率に対してセクション5.2で導入されたような l-近似性を持つことを観察する。 0.70
We believe that the study of machine learning problems through the lens of such rates of their induced restrictions Ul is a very promising new research direction. このような制限の速度のレンズを通して機械学習の問題の研究Ulは非常に有望な新しい研究の方向であると信じています。 0.76
References [20newsgoups Dataset, ] 20newsgoups 参考文献 20newsgoups Dataset, ] 20newsgoups 0.78
Dataset. https://scikit-learn . データセット。 Scikit-learn.com。 0.67
20newsgoups dataset. 20newsgoupsデータセット。 0.68
org/stable/datasets/ real_world.html# newsgroups-dataset. html# newsgroups-dataset.o rg/stable/datasets/r eal_world 0.31
[Bartlett, 1998] Bartlett, P. (1998). [Bartlett, 1998] Bartlett, P. (1998) 0.82
The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. ニューラルネットワークによるパターン分類のサンプルの複雑さ:重みの大きさは、ネットワークのサイズよりも重要です。 0.78
IEEE Transactions on Information Theory, 44. IEEE Transactions on Information Theory, 44。 0.80
[Bartlett et al., 2017] Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. [Bartlett et al., 2017]Bartlett, P. L., Foster, D. J., and Telgarsky, M. J。 0.89
(2017). Spectrally-normalize d margin bounds for neural networks. (2017). ニューラルネットワークのスペクトル正規化マージン境界 0.79
In Advances in Neural Information Processing Systems, pages 6240–6249. In Advances in Neural Information Processing Systems, pages 6240–6249. 0.99
11 [Bellet and Habrard, 2015] Bellet, A. and Habrard, A. 11 Bellet and Habrard, 2015]Bellet, A. and Habrard, A. 0.84
(2015). Robustness and generalization for metric learning. (2015). 計量学習におけるロバスト性と一般化 0.72
Neurocomputing, 151:259–267. 神経計算, 151:259–267。 0.44
[Bellet et al., 2015] Bellet, A., Habrard, A., and Sebban, M. (2015). [Bellet et al., 2015] Bellet, A., Habrard, A., and Sebban, M. (2015). 0.89
Metric learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 9(1):1–151. メトリック学習。 人工知能と機械学習に関する合成講義、9(1):1–151。 0.74
[Boucheron et al., 2013] Boucheron, S., Lugosi, G., and Massart, P. (2013). [Boucheron et al., 2013]Boucheron, S., Lugosi, G., and Massart, P. (2013) 0.80
Concentration inequalities: a nonasymptotic theory of independence. 濃度不等式:独立性の非漸近理論。 0.79
Oxford University Press, Oxford, 1st ed edition. オックスフォード大学出版局(Oxford University Press) - 第1版。 0.69
[Bousquet and Elisseeff, 2002] Bousquet, O. [Bousquet and Elisseeff, 2002]Bousquet, O. 0.83
and Elisseeff, A. とElisseeff, A。 0.68
(2002). Stability and generalization. (2002). 安定性と一般化。 0.75
J. Mach. Learn. J. Mach 学ぶ。 0.72
Res. [Bousquet et al., 2020] Bousquet, O., Klochkov, Y., and Zhivotovskiy, N. (2020). Res! [Bousquet et al., 2020]Bousquet, O., Klochkov, Y., Zhivotovskiy, N. (2020) 0.74
Sharper bounds for uniformly stable algorithms. 一様に安定なアルゴリズムのよりシャープな境界。 0.54
In Conference on Learning Theory, pages 610–626. 学習理論に関する会議で、610-626ページ。 0.80
PMLR. [Cao et al., 2016] Cao, Q., Guo, Z.-C., and Ying, Y. PMLR。 [Cao et al., 2016]Cao, Q., Guo, Z.-C., Ying, Y。 0.82
(2016). Generalization bounds for metric and similarity learning. (2016). 計量と類似性学習のための一般化境界。 0.72
Machine Learning, 102(1):115–132. 機械学習 102(1):115–132。 0.88
[Chicco, 2020] Chicco, D. (2020). [Chicco, 2020]Chicco, D.(2020)。 0.87
Siamese neural networks: An overview. siamese neural networks: 概要。 0.67
Artificial Neural Networks, pages 73–94. 人工ニューラルネットワーク、73-94ページ。 0.74
[Christmann and Zhou, 2016] Christmann, A. and Zhou, D.-X. [Christmann and Zhou, 2016]Christmann, A. and Zhou, D.-X。 0.97
(2016). On the robustness of regularized pairwise learning methods based on kernels. (2016). カーネルに基づく正規化ペアワイズ学習手法の堅牢性について 0.76
Journal of Complexity, 37:1–33. Journal of Complexity, 37:1-33。 0.67
[Davis et al., 2007] Davis, J. V., Kulis, B., Jain, P., InformationSra, S., and Dhillon, I. S. (2007). (Davis et al., 2007) Davis, J. V., Kulis, B., Jain, P., InformationSra, S., and Dhillon, I. S. (2007) 0.86
theoretic metric learning. 理論的なメトリック学習。 0.59
In Proceedings of the 24th international conference on Machine learning, pages 209–216. 第24回機械学習国際会議の議事録209-216頁。 0.70
[Feldman and Vondrak, 2019] Feldman, V. and Vondrak, J. [Feldman and Vondrak, 2019]Feldman, V. and Vondrak, J. 0.81
(2019). High probability generalization (2019). 高確率一般化 0.84
[Wang et al., 2019] Wang, B., Zhang, H., Liu, P., Shen, Z., and Pineau, J. [Wang et al., 2019]Wang, B., Zhang, H., Liu, P., Shen, Z., Pineau, J. 0.77
(2019). Multitask metric learning: Theory and algorithm. (2019). マルチタスクメトリック学習:理論とアルゴリズム。 0.81
In Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research. Proceedings of Machine Learning Research, Volume 89 of Proceedings of Machine Learning Research 0.67
PMLR. [Weinberger and Saul, 2009] Weinberger, K. Q. and Saul, L. K. (2009). PMLR。 [Weinberger and Saul, 2009]Weinberger, K. Q. and Saul, L. K. (2009). 0.85
Distance metric learning for large margin nearest neighbor classification. 大縁最近傍分類における距離距離学習 0.65
J. Mach. Learn. J. Mach 学ぶ。 0.72
Res., 10. [Xu and Mannor, 2012] Xu, H. and Mannor, S. (2012). 背番号10。 [Xu and Mannor, 2012]Xu, H. and Mannor, S. (2012) 0.63
Robustness and generalization. Machine learning, 86(3):391–423. 堅牢性と一般化。 機械学習、86(3):391–423。 0.71
[Zhang, 2002] Zhang, T. (2002). [Zhang, 2002] Zhang, T. (2002) 0.82
Covering number bounds of certain regularized linear function classes. ある正規化線型関数クラスの被覆数境界。 0.66
Journal of Machine Learning Research, 2(Mar):527–550. Journal of Machine Learning Research, 2(Mar):527–550。 0.92
[Zhou et al., 2019] Zhou, W., Veitch, V., Austern, M., Adams, R. P., and Orbanz, P. (2019). [Zhou et al., 2019]Zhou, W., Veitch, V., Austern, M., Adams, R. P., and Orbanz, P. (2019)。 0.80
Nonvacuous generalization bounds at the imagenet scale: a pac-bayesian compression approach. imagenetスケールにおける空でない一般化:pac-ベイズ圧縮アプローチ。 0.66
In International Conference on Learning Representations. International Conference on Learning Representationsに参加。 0.87
bounds for uniformly stable algorithms with nearly optimal rate. ほぼ最適な速度で一様安定なアルゴリズムの境界。 0.72
COLT. [Hastie et al., 2015] Hastie, T., Tibshirani, R., and Wainwright, M. (2015). COLT [Hastie et al., 2015] Hastie, T., Tibshirani, R., and Wainwright, M. (2015) 0.68
Statistical learning with sparsity: the lasso and generalizations. sparsity: the lasso and generalizations による統計学習。 0.83
CRC press. [Khosla et al., 2020] Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. (2020). CRCプレス。 Khosla et al., 2020] Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. (2020) 0.79
Supervised contrastive learning. 教師付きコントラスト学習。 0.60
arXiv preprint arXiv:2004.11362. arXiv preprint arXiv:2004.11362 0.72
[Lei et al., 2020] Lei, Y., Ledent, A., and Kloft, M. (2020). [Lei et al., 2020]Lei, Y., Ledent, A., and Kloft, M. (2020) 0.83
Sharper Generalization Bounds for Pairwise Learning. ペア学習のためのよりシャープな一般化境界。 0.51
In Advances in Neural Information Processing Systems. 神経情報処理システムの進歩です 0.58
[Maaten and Hinton, 2008] Maaten, L. v. d. and Hinton, G. (2008). [Maaten and Hinton, 2008]Maaten, L. v. d. and Hinton, G. (2008) 0.96
Visualizing data using t-sne. t-sneによるデータの可視化 0.51
Journal of machine learning research. journal of machine learning researchの略。 0.72
[mnist Dataset, ] mnist Dataset. [mnistデータセット, ]mnistデータセット。 0.75
Mnist dataset. Mnistデータセット。 0.78
https://keras.io/api /datasets/mnist/. https://keras.io/api /datasets/mnist/ 0.38
[Mohri et al., 2018] Mohri, M., Rostamizadeh, A., and Talwalkar, A. [Mohri et al., 2018]Mohri, M., Rostamizadeh, A., Talwalkar, A。 0.77
(2018). Foundations of machine learning. (2018). 機械学習の基礎。 0.77
The MIT Press, second edition edition. MIT Press、第2版。 0.62
[Schapire et al., 1998] Schapire, R. E., Freund, Y., Bartlett, P., and Lee, W. S. (1998). [Schapire et al., 1998]Schapire, R. E., Freund, Y., Bartlett, P., and Lee, W. S. (1998). 0.93
Boosting the margin: a new explanation for the effectiveness of voting methods. マージンを高める:投票方法の有効性に関する新しい説明。 0.65
The Annals of Statistics, 26. The Annals of Statistics, 26。 0.82
[Schroff et al., 2015] Schroff, F., Kalenichenko, D., and Philbin, J. Schroff et al., 2015] Schroff, F., Kalenichenko, D., and Philbin, J. 0.76
(2015). Facenet: A unified embedding for face recognition and clustering. (2015). Facenet: 顔認識とクラスタリングのための統合型埋め込み。 0.83
In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815–823. Proceedings of the IEEE conference on computer vision and pattern recognition, page 815–823。 0.82
[Verma and Branson, 2015] Verma, N. and Branson, K. (2015). Verma and Branson, 2015] Verma, N. and Branson, K. (2015) 0.82
Sample complexity of learning mahalanobis distance metrics. マハラノビス距離メトリクスの学習のサンプル複雑さ。 0.68
In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 28. Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems, Volume 28。 0.80
[Vershynin, 2018] Vershynin, R. [Vershynin, 2018]Vershynin, R. 0.84
HighDimensional Probability: An Introduction with Applications in Data Science. High Dimensional Probability: データサイエンスにおけるアプリケーションの導入。 0.83
Cambridge University Press, 1 edition. ケンブリッジ大学出版局、1版。 0.67
(2018). 12 (2018). 12 0.85
Dimension Free Generalization Bounds for Non Linear Metric 非線型計量に対する次元自由一般化境界 0.82
Learning Supplementary Material A Proof of Theorem 1 学習 補足材料 定理の証明 1 0.68
We will require the following bound on the Lipschitz constant of ζk. K の Lipschitz 定数に次の境界が必要です。 0.54
Lemma 8. For x, x(cid:48), y, y(cid:48) ∈ Rk set γ = max{(cid:107)x(cid:107)2 ,(cid:107)x(cid:48)( cid:107)2 ,(cid:107)y(cid:107) 2 ,(cid:107)y(cid:48)( cid:107)2}. 第8回。 x, y, y(cid:48) ∈ rk set γ = max{(cid:107)x(cid:107)2 ,(cid:107)x(cid:48)( cid:107)2 ,(cid:107)y(cid:107) 2 ,(cid:107)y(cid:107) y(cid:48)(cid:107)2} である。 0.72
Then ((cid:107)x − y(cid:107)2 + (cid:107)x(cid:48) − y(cid:48)(cid:107)2) . 次に ((cid:107)x − y(cid:107)2 + (cid:107)x(cid:48) − y(cid:48)(cid:107)2) となる。 0.76
|ζk(x, x(cid:48)) − ζk(y, y(cid:48))| ≤ 8γ k k(x, x(cid:48)) − sk(y, y(cid:48))| ≤ 8γ k 0.91
Proof. Set ∆ = x − y, ∆(cid:48) = x(cid:48) − y(cid:48). 証明。 x − y, y(cid:48) = x(cid:48) − y(cid:48) を設定する。 0.72
Clearly (cid:107)x − x(cid:48)(cid:107)2 ≤ 2γ, and (cid:107)∆ − ∆(cid:48)(cid:107)2 ≤ 4γ. 明らかに (cid:107)x − x(cid:48)(cid:107)2 ≤ 2γ と (cid:107)> − (cid:48)(cid:107)2 ≤ 4γ である。 0.80
We have |ζk(x, x(cid:48)) − ζk(y, y(cid:48))| 我々は |\k(x, x(cid:48)) − \k(y, y(cid:48))| 0.82
(cid:12)(cid:12)(cid :12)(cid:107)x − x(cid:48)(cid:107)2 (cid:12)(cid:12)(cid :12) (cid:12)(cid:12)(cid :12)−2(cid:104)x − x(cid:48), ∆ − ∆(cid:48)(cid:105) − (cid:107)∆ − ∆(cid:48)(cid:107)2 (cid:12)(cid:12)(cid :12)(cid:12)(cid:107 )x − x(cid:48)(cid:107)2 (cid:12)(cid:12)(cid :12) (cid:12)(cid:12)(cid :12)−2(cid:104)x − x(cid:48) が成立する。 0.94
2 − (cid:107)x − x(cid:48) − ∆ + ∆(cid:48)(cid:107)2 2 − (cid:107)x − x(cid:48) − s + (cid:48)(cid:107)2 0.89
2 2 (cid:12)(cid:12)(cid :12) 2 2 (cid:12)(cid:12)(cid :12) 0.81
|−2(cid:104)x − x(cid:48), ∆ − ∆(cid:48)(cid:105) − (cid:104)∆ − ∆(cid:48), ∆ − ∆(cid:48)(cid:105)| (4γ ((cid:107)∆(cid:107)2 + (cid:107)∆(cid:48)(cid:107)2) + 4γ ((cid:107)∆(cid:107)2 + (cid:107)∆(cid:48)(cid:107)2)) . |−2(cid:104)x − x(cid:48) は、 (cid:105) − (cid:104) は、 (cid:107)| (4γ ((cid:107)) は、 (cid:107) 2 + (cid:107)2) + 4γ ((cid:107)2) は、 (cid:107) 2 + (cid:107) 2 + (cid:107) 2 + (cid:107) は、 (cid:107) は、 (cid:107) は、 (cid:48)(cid:107) である。
訳抜け防止モード: |−2(cid:104)x − x(cid:48 ) は、 x(cid:48)(cid:105 ) − ( cid:104) は、 x(cid:48 ) の略である。 4γ ( ( cid:107) + ( cid:107) 2 + ( cid:107) + (cid:48)(cid:107) 2 ) + 4γ ( ( cid:107)∆(cid:107)2 + ( cid:107)∆(cid:48)(cid:107)2 ) ) .
= = 1 k 1 k 1 = k ≤ 1 k = = 1 k 1 k 1 = k ≤ 1 k 0.85
(22) Proof of Theorem 1. (22) 定理 1 の証明。 0.76
Denote throughout of the proof F := Fk(J k a,a(cid:48)). 証明 F := Fk(J k a,a(cid:48)) の全体について注意。 0.83
Our plan is to bound the covering numbers log N (F, ε) and then to use the Dudley entropy bound for the Rademacher complexity. 我々の計画は被覆数 log n (f, ε) を束縛し、ラデマッハ複雑性に対してダドリーエントロピーを束ねることである。
訳抜け防止モード: 我々の計画は、被覆数 log N ( F, ε ) を束縛することである。 そして、ダドリーエントロピーをラデマチャー複雑性のために使う。
Fix a , such that log |M| and log |M(cid:48)| are a and X(cid:48)J k ε > 0. log |M| と log |M(cid:48)| が a と X(cid:48)J k ε > 0 であるような a を固定する。 0.82
Let M and M(cid:48) be ε-covers for the sets XJ k at most a2b2n 2ε-cover for the set M と M(cid:48) を集合 XJ k に対して最大 a2b2n 2ε 被覆とする。 0.68
a,a(cid:48)(cid:9) ⊂ Rn×2k. a,a(cid:48)(cid:9) = Rn×2k。 0.74
Note that the elements of M × M(cid:48) are not necessarily members M × M(cid:48) の要素は必ずしもメンバーではないことに注意してください。 0.68
log(2dk), as guaranteed by Lemma 2. log(2dk) は Lemma 2 で保証されている。 0.79
Then the set M × M(cid:48) is an すると、集合 M × M(cid:48) は a となる。 0.71
Z =(cid:8)(XA, X(cid:48)A) | A ∈ J k Z =(cid:8)(XA, X(cid:48)A) | A ∈ J k 0.98
2ε-cover of size at most |M| × |M(cid:48)| with Let φZ denote the image of Z under φ, acting coordinatewise, and denote by ˆζk : Rn×2k → Rn the map 2ε-cover of size at most |M| × |M(cid:48)| with Let φZ represent the image of Z under φ, act coordinatewise, andmarkmark by Rn×2k → Rn the map 0.92
of Z. However, by taking projections onto Z, we can find an 2 elements inside Z. Denote such a cover by P. that applies ζk on the rows. Zの。 しかし、射影を Z に取り込むことで、Z の内部に 2 つの元を見つけることができる。 0.57
In particular, for every A and every coordinate i ≤ n, we have 特に、すべての a と任意の座標 i ≤ n に対して、私たちは 0.83
√ √ ε2 (cid:0)φ(Atxi), φ(Atx(cid:48) i)(cid:1) . √ √ ε2 (cid:0)φ(Atxi), φ(Atx(cid:48) i)(cid:1)。 0.84
(23) ˆζk (φ ((XA, X(cid:48)A)))i = ζk Equivalently, by definition, we have that F = ˆζk (φ (Z)). (23) φ ((XA, X(cid:48)A)))i = φk 等価な定義では、F = φk (φ (Z)) である。 0.82
Finally, since φ(0) = 0, for any xi and A ∈ J k 最後に、任意のxi と A ∈ J k に対して φ(0) = 0 となる。 0.81
(cid:13)(cid:13)φ(Atxi)(cid:13)(cid:1 3)2 ≤ ba(cid:48) (cid:107)φ(cid:107)Lip . (cid:13)(cid:13)φ(Atxi)(cid:13)(cid:1 3)2 ≤ ba(cid:48) (cid:107)φ(cid:107)Lip 。 0.79
a,a(cid:48) we have a,a(cid:48) 0.70
It therefore follows by Lemma 8 that ˆζk is quently, a 2 したがって、Lemma 8 で yk は quently, a 2 である。 0.74
√ 2ε-cover P of Z is mapped by ˆζk ◦ φ into an 2 Z の 2ε-被覆 P は φ によって 2 に写像される 0.81
√ k 2 · √ 28ba(cid:48)(cid:107 )φ(cid:107)Lip √ k 2 · √ 28ba(cid:48)(cid:107 )φ(cid:107)Lip 0.83
k · (cid:107)φ(cid:107)Lip · ε-cover of F. k · (cid:107)φ(cid:107)Lip · ε-cover of F。 0.82
√ 28ba(cid:48)(cid:107 )φ(cid:107)Lip √ 28ba(cid:48)(cid:107 )φ(cid:107)Lip 0.81
(24) -Lipschitz as a function from φ(Z) to Rn. (24) - φ(Z) から Rn への関数としてのLipschitz。 0.87
Conse- 13 コンス 13 0.72
Combining the above statements, we have shown that there is an absolute constant c > 0 such that for 上記のステートメントを組み合わせると、c > 0 の絶対定数が存在することが示されています。 0.77
any ε > 0, log N (F, ε) ≤ c ε > 0 です。 log N (F, ε) ≤ c 0.78
Set D = diam(F) = supu,v∈F (cid:107)u − v(cid:107)2. D = diam(F) = supu,v∈F (cid:107)u − v(cid:107)2 とする。 0.83
Using (24) again, we have D ≤ 4b2a(cid:48)2(cid:10 7)φ(cid:107)2 D ≤ 4b2a(cid:48)2(cid:10 7)φ(cid:107)2 0.74
Lip k Dudley’s entropy bound, [Vershynin, 2018], and using (25), for any δ > 0, 唇 k Dudley's entropy bound, [Vershynin, 2018] and using (25, for any δ > 0, 0.79
(25) n. Next, by (25) n. 次は 0.77
· √ a2a(cid:48)2b4n(cid: 107)φ(cid:107)4 · √ a2a(cid:48)2b4n(cid: 107)φ(cid:107)4 0.75
Lip k2ε2 log(2dk). 唇 k2ε2 log(2dk)。 0.73
(cid:90) D/2 (cid:90)D/2 0.64
(cid:112)log N (F, ε)dε (cid:112)log N (F, ε)dε 0.94
aa(cid:48)b2 (cid:107)φ(cid:107)2 aa(cid:48)b2 (cid:107)φ(cid:107)2 0.78
Lip k log (D/δ) . 唇 k log (D/δ)。 0.79
R (F) ≤ 4δ√ n ≤ 4δ√ n R (F) ≤ 4δ ≤ n ≤ 4δ ≤ n 0.79
+ + δ 12 n √ c√ 12 n + + δ 12 n (複数形 12 ns) 0.83
Taking δ = 1√ δ = 1 を取る。 0.71
n and using the above bound on D completes the proof. 上の有界な D を用いて証明を完備化する。 0.67
B Proof of Corollary 3 Proof. B Corollary 3 Proofの証明。 0.71
For any A ∈ Rd×k, we have (cid:107)A(cid:107)2 ,1 ≤ k (cid:107)A(cid:107)2 ,∞ and (cid:107)A(cid:107)o p ≤ √ (cid:32) k(cid:88) 任意の A ∈ Rd×k に対して (cid:107)A(cid:107)2 ,1 ≤ k (cid:107)A(cid:107)2 ,∞ と (cid:107)A(cid:107)o p ≤ k(cid:32)k(cid:88) がある。 0.79
immediately from the definitions. For the second inequality observe that 定義からすぐに 2つ目の不平等は 0.59
(cid:107)A(cid:107)o p =(cid:13)(cid:13)At(c id:13)(cid:13)op = sup (cid:18) ≤ a ⊂ J k The two inequalities above imply that Gk (cid:107)a(cid:107)o p =(cid:13)(cid:13)at(c id:13)(cid:13)op = sup (cid:18) ≤ a である。 0.82
(cid:13)(cid:13)Atv( cid:13)(cid:13) = sup (cid:19) 1 (cid:13)(cid:13)Atv( cid:13)(cid:13) = sup (cid:19) 1 0.78
k max i≤k √ k max i≤k ? 0.74
(cid:107)v(cid:107)2 =1 √ (cid:107)v(cid:107)2 =1 0.74
(cid:107)A·i(cid:107)2 (cid:107)A·i(cid:107)2 0.71
(cid:107)v(cid:107)2 =1 (cid:107)v(cid:107)2 =1 0.71
= 2 2 ka, = 2 2 カ... 0.71
ka i=1 k (cid:107)A(cid:107)2 ,∞ . カ i=1 k (cid:107)A(cid:107)2 ,∞。 0.70
(cid:33) 1 2 (cid:33)1 2 0.82
(cid:104)A·i, v(cid:105)2 (cid:104)A·i,v(cid:105)2 0.75
and thus the Corollary follows from Theorem 1. したがって、Corollary は Theorem 1 から続く。 0.73
k (cid:107)A(cid:107)2 ,∞. k (cid:107)A(cid:107)2 ,∞。 0.95
The first inequality follows C First Proof of Theorem 4 Proof 1 of Theorem 4: For any set of families of functions Hi, i ≤ m, define the sum ⊕m 最初の不平等は C First Proof of Theorem 4 Proof 1 of Theorem 4: 関数 Hi, i ≤ m の任意の一群に対して、和 sm を定義する。 0.80
| hi ∈ Hi}. Hi ∈ Hi} である。 0.84
For a scalar α set also αH = {αh | h ∈ H}. スカラー α 集合についても αH = {αh | h ∈ H} である。 0.80
We observe the following: {g =(cid:80)m 以下を観察する。 {g =(cid:80)m 0.74
i=1Hi by ⊕m i=1Hi = i=1こんにちは。 i=1Hi= 0.57
i=1 hi (cid:0)⊕k i=1 hi (cid:0) 0.81
a)(cid:1) , a (cid:1) , 0.91
1 k a ) = Fk(Gk 1k a ) = Fk(Gk) 0.82
i=1F1(G1 where the expression on the right handside is the sum of F1(G1 equality is a consequence of the definition of ζk as an average, and of the fact that Gk individual columns. 右辺の式が F1(G1) の和である i=1F1(G1) は、平均として k の定義の結果であり、Gk が個々の列であるという事実である。 0.80
More explicitly, given A ∈ Gk (ζk(φ(Atxi), φ(Atx(cid:48) より明確には、A ∈ Gk ( φ(Atxi), φ(Atx(cid:48) が与えられる。 0.89
a , the vector in Fk(Gk i=1 ∈ Rn. a , Fk(Gk i=1 ∈ Rn のベクトル。 0.86
For a fixed coordinate i ≤ n we have k(cid:88) k(cid:88) 固定座標 i ≤ n に対して k(cid:88) k(cid:88) を持つ 0.81
(cid:0)φ((Atxi)j) − φ((Atx(cid:48) i)j)(cid:1)2 (cid:0)φ(At·jxi) − φ(At·jx(cid:48) i)(cid:1)2 (cid:0)φ((Atxi)j) − φ((Atx(cid:48) i)j)(cid:1)2 (cid:0)φ(At·jxi) − φ(At·jx(cid:48) i)(cid:1)2 0.88
ζk(φ(Atxi), φ(Atx(cid:48) シュク(φ(Atxi)、φ(Atx(cid:48) 0.85
i)) = i))n 1 k i) = i)n 1k 0.58
j=1 = , a) taken k times, normalized by 1 j=1 = , a) k 回取り、1 の正規化 0.73
k . This a is a product set of its a ) corresponding to A is, by definition, である。 この a は A に対応する a の積集合であり、定義上は、 0.64
(26) (27) 1 k (26) (27) 1k 0.80
j=1 14 j=1 14 0.72
Next, one can readily verify that for any set of families Hi, we have R (⊕mHm) = (cid:80)m 次に、任意の一組の族 Hi に対して R が (cid:80)m であることを容易に検証できる。 0.72
where (Atxi)j is the j-th coordinate of (Atxi) and At·jxi is the product of A restricted to its j-th column with xi. ここで (atxi)j は (atxi) の j-次座標であり、 at·jxi は xi の j-次列に制限された積である。 0.75
Since each term in the sum (27) is in G1 i=1 R (Hi), and R (αH) = αR (H) for α ≥ 0 (see [Bartlett and Mendelson, 2002], [Mohri et al., 2018] ). 和 (27) の各項は G1 i=1 R (Hi) であり、α ≥ 0 に対して R (αH) = αR (H) である([Bartlett and Mendelson, 2002], [Mohri et al., 2018] を参照)。 0.84
Therefore, using (26) we have したがって (26) を使って 0.75
a, the claim (26) follows. a,クレーム(26)は次のとおりである。 0.59
R(cid:0)Fk(Gk R(cid:0)Fk(Gk) 0.84
a )(cid:1) = R(cid:0)F1(G1 a)(cid:1) . a )(cid:1) = R(cid:0)F1(G1 a)(cid:1) 0.78
(28) The statement now follows from Corollary 3 applied with k = 1. (28) このステートメントは、k = 1 で適用される Corollary 3 から続く。 0.81
D Second Proof of Theorem 4 D Second Proof of Theorem 4 0.85
Proof 2 of Theorem 4, Dimension Reduction: Fix l < k, and set t0 = every f ∈ Fk one can write f = ˆf + (f − ˆf ) such that ˆf ∈ Fl and 定理 4 の証明 2 次元の縮小: l < k を固定し、t0 = すべての f ∈ fk を f = s f + (f − sf ) と書くことができ、f ∈ fl となる。 0.89
(ab(cid:107)φ(cid:107)Lip)2√ (ab(cid:107)φ(cid:107)Lip)2 0.86
log 4n √ ≤ t0. log 4n は ≤ t0 である。 0.71
It follows that l . その通りです l . 0.76
By Lemma 5, for Lemma 5(英語) 0.55
(cid:13)(cid:13)(cid :13)f − ˆf (cid:13)(cid:13)(cid :13)∞ n(cid:88) (cid:17)(cid:33) (cid:13)(cid:13)(cid :13)(cid:13)∞ n(cid:88) (cid:17)(cid:33) 0.94
i=1 l (cid:107)φ(cid:107)Lip i=1 l (cid:107)φ(cid:107)Lip 0.71
Eεsup(cid:107)f(cid:10 7)∞≤t0 Eεsup(cid:107)f(cid:10 7)∞≤t0 0.69
εifi (cid:16) εifi (cid:16) 0.78
√ na2 n(cid:88) √ na2 n(cid:88) 0.82
n(cid:88) i=1 n(cid:88) i=1 0.71
i=1 εifi + i=1 εifi + 0.74
1 n R (Fk) = 1n R (Fk) = 0.80
1 n Eεsupf∈Fk 1n Eεsupf∈Fk 0.57
εifi ≤ 1 Eεsupf∈Fl n ≤ R (Fl) + t0 ≤ εifi ≤ 1 Eεsupf∈Fl n ≤ R (Fl) + t0 ≤ 0.82
(cid:32) 1 n (cid:32) 1n 0.77
+ c · a2b2 (cid:16) ab(cid:107)φ(cid:107)Lip √ + c · a2b2 (cid:16) ab(cid:107)φ(cid:107)Lip 0.78
l + √ l (cid:107)φ(cid:107)2 √ n l + l (cid:107)φ(cid:107)2 ^ n 0.82
(cid:17)2 √ Lip (cid:17)2 唇 0.84
log log 4n , ログ log 4n , 0.82
where the last inequality follows by Corollary 3. 最後の不等式はCorollary 3で従う。 0.62
Minimizing the above expression in l yields (17). 上記の式を l で最小化する(17)。 0.74
E Additional Details on Experiments e. 実験のさらなる詳細 0.85
• The full code of the experiments is provided as a Supplementary Material. •実験の完全なコードは補足材料として提供されます。 0.87
The code is based on the コードは以下の通りです。 0.69
Tensorflow framework. Tensorflowフレームワーク。 0.72
Details on the invocation can be found in the README.md file. 呼び出しの詳細は README.md ファイルで確認できます。 0.75
• The precise process of sampling the pairs (x, x(cid:48)) was as follows: We fix two batch sizes Bx, By, typically Bx = By = 500. • ペア(x, x(cid:48))をサンプリングする正確なプロセスは以下の通りでした。2つのバッチサイズBx, By,通常Bx = By = 500を固定します。 0.81
We take a batch S1 of size Bx and another, independent batch, S2, of size By. 私たちは、サイズBxのバッチS1と、サイズBの独立したバッチS2を取ります。 0.71
Then the set S of all feature pairs (x, x(cid:48)) such that x ∈ S1 and x(cid:48) ∈ S2 is created, with corresponding labels y as described in Section 1. そして、x ∈ S1 と x(cid:48) ∈ S2 のすべての特徴対 (x, x(cid:48)) の集合 S が生成され、対応するラベル y がセクション 1 に記述されている。 0.83
This S is fed to the optimizer as a single batch. このSは、オプティマイザに単一のバッチとして供給される。 0.48
• An epoch is when first batch iterator, S1, finishes a single iteration over the whole data. • 時期は、最初のバッチイテレータであるS1がデータ全体の単一イテレーションを終了する時です。 0.80
The data is permuted at the end of the epoch. データは 時代が終わりに変わりました 0.49
• All experiments were run for 180 epochs. •全ての実験は180エポックで実行された。 0.74
Convergence typically occurred much earlier, around 30 to 50 収束は通常ずっと早く 約30~50で起こりました 0.70
epochs, depending on the value of k. epochs は k の値に依存します 0.73
15 15 0.85
√ (a) MNIST Experiment. MNIST実験(MNIST Experiment)。 0.61
and (cid:107)A(cid:107)o p / (cid:107)A(cid:107)2 ,1 /k Norms, Linear Embedding. そして(cid:107)A(cid:107)o p / (cid:107)A(cid:107)2 ,1 /k Norms、線形埋め込み。 0.71
(cid:107)A(cid:107)2 ,∞, k Weight (cid:107)A(cid:107)2 ,∞,k重量 0.92
(b) Newsgroups Experiment. (b)ニュースグループ実験。 0.82
(cid:107)A(cid:107)2 ,∞, √ and (cid:107)A(cid:107)o p / (cid:107)A(cid:107)2 ,1 /k k Weight Norms, Linear Embedding. (cid:107)A(cid:107)2 ,∞,(cid:107)A(cid:107) op / (cid:107)A(cid:107)2 ,1 /k k 重量ノルム、線形埋め込み。 0.81
• All experiments were run on a GTX 1080 GPU, with Tensorflow 2.0. • すべての実験は、Tensorflow 2.0でGTX 1080 GPU上で実行された。 0.76
A single run of the longest experiment, MNIST with k = 5000, took under 150 minutes to complete. 最も長い実験の1回、k = 5000のMNISTは150分以下で完了した。 0.71
All experiments combined, with repetitions, finish running in under 48 hours. 全ての実験は繰り返し実施され、48時間以内に完了した。 0.78
16 12345105010050010005 000K1.001.251.501.75, infty) norm, LinearL(2,1) norm / K, LinearL(op) norm / sqrt(K), Linear12345105010050 010005000K5101520253 0NormL(2,infty) norm, LinearL(2,1) norm / K, LinearL(op) norm / sqrt(K), Linear 16 1234510501005005000K 2.252.50NormL(2,inft y) norm, LinearL(2,1) norm / K, LinearL(op) norm / sqrt(K), Linear12345105050050 00K510202530NormL(2, infty) norm, LinearL(2,1) norm / K, LinearL(op) norm / sqrt(K), Linear 0.84

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