論文の概要、ライセンス

# (参考訳) 侵入攻撃に対するロバスト学習決定リストのためのサンプル複雑度境界 [全文訳有]

Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks ( http://arxiv.org/abs/2205.06127v1 )

ライセンス: CC BY 4.0
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska and James Worrell(参考訳) 敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。 本稿では,PAC学習の枠組みの中で,意思決定リストのクラスに着目し,この問題に対処する。 リプシッツ条件を満たす入力データ上の確率分布について, 分布の仮定が相反する設定において必須であることを考慮すると, 近傍点が類似する確率を持つ。 私たちの重要な結果は、敵の予算(つまり各入力で摂動できるビット数)が、ロバストな学習のサンプル複雑性を決定する基本的な量であることを示している。 モノトン結合の類(本質的にはブール超キューブ上の最も単純な非自明な仮説クラス)であり、任意の超クラスは少なくとも敵の予算において指数関数的にサンプル複雑性を持つ。 固定された$k$ に対して、$k$-決定リストのクラスは$\log(n)$-bounded adversaryに対して多項式のサンプル複雑性を持つ。 これにより、効率的なpac学習アルゴリズムが常に一様分布下で効率的な$\log(n)$-robust学習アルゴリズムとして使用できるかどうかという疑問が浮き彫りになる。

A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. In this paper we address this issue within the framework of PAC learning, focusing on the class of decision lists. Given that distributional assumptions are essential in the adversarial setting, we work with probability distributions on the input data that satisfy a Lipschitz condition: nearby points have similar probability. Our key results illustrate that the adversary's budget (that is, the number of bits it can perturb on each input) is a fundamental quantity in determining the sample complexity of robust learning. Our first main result is a sample-complexity lower bound: the class of monotone conjunctions (essentially the simplest non-trivial hypothesis class on the Boolean hypercube) and any superclass has sample complexity at least exponential in the adversary's budget. Our second main result is a corresponding upper bound: for every fixed $k$ the class of $k$-decision lists has polynomial sample complexity against a $\log(n)$-bounded adversary. This sheds further light on the question of whether an efficient PAC learning algorithm can always be used as an efficient $\log(n)$-robust learning algorithm under the uniform distribution.
公開日: Thu, 12 May 2022 14:40:18 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
2 2 0 2 y a M 2 1 2 2 0 2 y a m 2 1 である。 0.52
] G L . s c [ ] G L。 sc [ 0.47
1 v 7 2 1 6 0 1 v 7 2 1 6 0 0.42
. 5 0 2 2 : v i X r a . 5 0 2 2 : v i X r a 0.42
Sample Complexity Bounds for Robustly Learning Decision Lists ロバストに学習する決定リストのためのサンプル複雑性境界 0.61
against Evasion Attacks Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell 侵略に対する攻撃 Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell 0.48
University of Oxford オックスフォード大学 0.57
May 13, 2022 2022年5月13日 0.72
Abstract A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. 概要 敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
訳抜け防止モード: 概要 対人機械学習における根本的な問題は 避難攻撃の有無で どれだけの訓練データが必要か 定量化します
0.60
In this paper we address this issue within the framework of PAC learning, focusing on the class of decision lists. 本稿では,PAC学習の枠組みの中で,意思決定リストのクラスに着目し,この問題に対処する。 0.82
Given that distributional assumptions are essential in the adversarial setting, we work with probability distributions on the input data that satisfy a Lipschitz condition: nearby points have similar probability. リプシッツ条件を満たす入力データ上の確率分布について, 分布の仮定が相反する設定において必須であることを考慮すると, 近傍点が類似する確率を持つ。 0.77
Our key results illustrate that the adversary’s budget (that is, the number of bits it can perturb on each input) is a fundamental quantity in determining the sample complexity of robust learning. 私たちの重要な結果は、敵の予算(つまり各入力で摂動できるビット数)が、ロバストな学習のサンプル複雑性を決定する基本的な量であることを示している。 0.78
Our first main result is a sample-complexity lower bound: the class of monotone conjunctions (essentially the simplest non-trivial hypothesis class on the Boolean hypercube) and any superclass has sample complexity at least exponential in the adversary’s budget. モノトン結合のクラス(本質的にはブール超キューブ上の最も単純な非自明な仮説クラス)であり、任意の超クラスは少なくとも敵の予算において指数関数的にサンプル複雑性を持つ。 0.73
Our second main result is a corresponding upper bound: for every fixed k the class of k-decision lists has polynomial sample complexity against a log(n)-bounded adversary. 2つ目の主な結果は対応する上界である:すべての固定 k に対して、k-分解リストのクラスは、log(n)-bounded adversary に対する多項式サンプル複雑性を持つ。 0.72
This sheds further light on the question of whether an efficient PAC learning algorithm can always be used as an efficient log(n)-robust learning algorithm under the uniform distribution. これにより、効率的なpac学習アルゴリズムが常に一様分布下で効率的なlog(n)-robust学習アルゴリズムとして使用できるかどうかという疑問が浮き彫りになる。 0.74
1 Introduction Adversarial machine learning has been extensively studied in recent years, first with spam filtering in [6, 19, 20], and then when the notion of adversarial examples was introduced by Szegedy et al [26], and independently noticed by Biggio et al [3]. 1 はじめに 近年, [6, 19, 20] のスパムフィルタリング, そして Szegedy et al [26] の逆例の概念を導入し, Biggio et al [3] に独立して認識されるなど,逆機械学習が広く研究されている。 0.56
Various settings to study adversarial machine learning guarantees (and impossibility results) have emerged in the literature since. それ以来、敵対的機械学習の保証(および不可能な結果)を研究するための様々な設定が文献に現れている。
訳抜け防止モード: 敵対的機械学習の保証(および不可能な結果)を研究するための様々な設定 文学に登場しました
0.72
The most common distinction, presented by Biggio and Roli [4], differentiates between attacks at training time, known as poisoning attacks, and attacks at test time, called evasion attacks. biggioとroli [4]によって提示された最も一般的な区別は、トレーニング時の攻撃(毒殺攻撃)と、テスト時の攻撃(脱走攻撃)との違いである。 0.68
In the context of evasion attacks, a misclassification by a model has been defined in various ways, and sometimes regrettably referred to by the same terminology. 回避攻撃の文脈では、モデルによる誤分類は様々な方法で定義され、時には同じ用語で後悔して言及される。 0.76
Dreossi et al [10], Diochnos et al [7], Gourdeau et al [17] offer thorough discussions on the subject. Dreossi et al [10], Diochnos et al [7], Gourdeau et al [17] では、この問題について徹底的な議論が行われている。 0.75
We will focus on the exact-in-the-ball notion of robustness (also known as error region risk in [7]), which necessitates a ground truth function. 我々は、基底真理関数を必要とするロバストネス([7]におけるエラー領域リスクとも呼ばれる)の正確な考え方に焦点を当てる。 0.70
Briefly, the exact-in-the-ball notion of robustness requires a hypothesis to be correct with respect to the ground truth in a perturbation region around each test point. 簡単に言えば、ボール内のロバスト性の正確な概念は、各試験点周辺の摂動領域における基底的真実に関して正しい仮説を必要とする。 0.62
Note that, in this case, the ground truth must be specified on all input points in the perturbation region. この場合、基底真理は摂動領域のすべての入力点に指定しなければならないことに注意。 0.72
By contrast, the constant-in-the-ball notion of robustness (which is also known as corrupted input robustness) is concerned with the stability of the hypothesis to perturbations in the input, 対照的に、球内ロバスト性(constant-in-the-bal l)の概念は、入力の摂動に対する仮説の安定性に関係している。 0.60
1 1 0.43
英語(論文から抽出)日本語訳スコア
and requires that the label produced by the hypothesis remain constant in the perturbation region, meaning that we only need access to the test point labels. そして、仮説によって生成されたラベルは摂動領域で一定であり、つまりテストポイントラベルへのアクセスのみが必要である。 0.68
The hardness of robust classification has been explored from both a computational complexity and a statistical viewpoint, see for e g , [5, 23]. 頑健な分類の硬さは、計算複雑性と統計的視点の両方から、eg , [5, 23] について検討されている。 0.71
In this paper, we focus on the Boolean hypercube {0, 1}n as our input space and study the information-theoreti c complexity of robust learning by exhibiting sample complexity upper and lower bounds that depend on an adversarial budget, i.e., the number of bits an adversary is allowed to flip at test time, thus illustrating that the adversarial budget is a fundamental quantity in determining the sample complexity of robustly learning important concept classes. 本稿では,我々の入力空間としてのBoolean hypercube {0, 1}nに着目し,敵対的予算に依存するサンプルの複雑度を上・下限で表すことにより,ロバスト学習の知識論的複雑さを考察する。
訳抜け防止モード: 本稿では,入力空間としてのブールハイパーキューブ {0, 1}nに着目した。 情報 - 堅牢な学習の理論的複雑さを 敵の予算に依存する上と下の境界のサンプルの複雑さを示す つまり 相手のビットの数は テスト時に回すことができる したがって、敵の予算は、重要な概念クラスをしっかり学習する際の、サンプルの複雑さを決定するための基本的な量である。
0.75
1.1 Our Contributions 1.1 コントリビューション 0.69
Our work builds on the work of Gourdeau et al [16] and its extended version [17]. 私たちの作品は、gourdeau et al [16] と拡張版 [17] の成果に基づいている。 0.64
Our results hold for the exact-in-the-ball robustness to evasion attacks, and are outlined below. 本研究の結果は, 脱走攻撃に対するボールの正確な堅牢性を示すものであり, 以下に概説する。 0.46
Robust Learning of Decision Lists: As shown in [17], efficient, exact-in-the-ball robust learning is not possible without distributional assumptions on the training data.1 決定リストのロバスト学習:[17]に示すように、トレーニングデータに分散仮定がなければ、効率的で正確なロバスト学習は不可能である。 0.74
We follow their line of work and establish the sample-efficient robust learnability of decision lists against a log(n)bounded adversary under log-Lipschitz distributions, which include the uniform and product distributions. 我々は,彼らの研究の行に従い,一様分布と積分布を含むlog-lipschitz分布の下でのlog(n)bounded adversaryに対する決定リストのサンプル効率のロバストな学習可能性を確立する。 0.68
The algorithms we use to show such upper bounds are called ρ-robust learning algorithms, where ρ is the allowed perturbation budget for an adversary. このような上限を示すアルゴリズムはρ-robust Learningアルゴリズムと呼ばれ、ρは敵に対する摂動予算として許容される。 0.83
In proving our first result we obtain an isoperimetric bound that may be of independent interest: for a CNF formula ϕ we give an upper bound on the number of points in the Boolean hypercube within a given Hamming distance to a satisfying assignment of ϕ. cnfの公式 φ に対して、与えられたハミング距離内のブール超キューブ内の点の数の上界を φ の満足する代入に与える。 0.37
An analogue result was shown only for monotone decision lists in [17]. 類似の結果は[17]の単調決定リストに対してのみ示された。 0.72
More importantly, Gourdeau et al [17] suggested the following open problem: さらに重要なことに、Gourdeau氏ら[17]は以下のオープンな問題を提案した。 0.57
Let A be a sample-efficient (potentially proper) PAC-learning algorithm for concept class C. Is A also a sample-efficient log(n)-robust learning algorithm for C under the uniform distribution? a を概念クラス c のサンプル効率(潜在的に適切な)pac学習アルゴリズムとし、また一様分布の下で c のサンプル効率のよい log(n)-robust 学習アルゴリズムでもあるか? 0.76
So far, all the concept classes that have been studied point towards a positive answer to this question. これまで研究されてきたすべての概念クラスは、この問題に対する肯定的な答えを示している。 0.65
As log-Lipschitz distributions subsume the uniform distribution, our result thus adds to the body of positive evidence for this problem. 対数Lipschitz分布が一様分布を仮定するので、この結果はこの問題に対する肯定的な証拠の本体に追加される。 0.67
An Adversarial Sample Complexity Lower Bound: To complement the above result, we show that any ρ-robust learning algorithm for monotone conjunctions must have a sample complexity that is exponential in the number ρ of bits an adversary is allowed to flip during an evasion attack. A Adversarial Sample Complexity Lower Bound: 上記の結果を補完するために、単調な接続に対するρ-robust学習アルゴリズムは、敵が回避攻撃中に反転できるビット数ρで指数関数的なサンプル複雑性を持つ必要があることを示す。 0.85
Previously, Gourdeau et al [17] showed that there does not exist such an algorithm with polynomial sample complexity against an adversary that can perturb ω(log(n)) bits of the input. gourdeau et al [17] は、入力の ω(log(n)) ビットを摂動できる敵に対して、多項式サンプル複雑性を持つそのようなアルゴリズムは存在しないことを示した。 0.82
1.2 Related Work The inevitability of adversarial examples under the constant-in-the-ball definition of robustness has been extensively studied, see for e g , [13, 11, 12, 15, 25, 27, 18]. 1.2関連作品 球状強靭性の定義の下での逆例の不可避性は、e g , [13, 11, 12, 12, 15, 25, 27, 18] について広く研究されている。 0.68
We first outline related work on sample complexity lower bounds for robust learning. まず,ロバスト学習のためのサンプル複雑性下限について概説する。 0.69
Bhagoji et al [2] work with the constant-in-the-ball definition of robustness and use an optimal transport cost function to derive lower bounds for learning classes with labels that come from a mixture of Gaussian distributions. Bhagoji et al [2] はボール内のロバスト性の定義に取り組み、ガウス分布の混合から得られるラベルを持つ学習クラスに対する下界を導出するために最適な輸送コスト関数を使用する。
訳抜け防止モード: Bhagoji et al [ 2 ] work with the constant - in - the - ball definition of robustness 最適な輸送コスト関数を使い ガウス分布の混合に由来するラベルを持つ学習クラスに対する下位境界を導出する。
0.89
1This is in contrast to PAC learning, which is distribution-free. 1これは、分散のないPAC学習とは対照的である。 0.61
2 2 0.42
英語(論文から抽出)日本語訳スコア
Montasser et al [23] also use this notion of robustness to show a lower bound that depends on a complexity measure adapted to robustness from the shattering dimension of a concept class. montasser氏ら[23]はまた、このロバスト性の概念を用いて、概念クラスの分散次元からロバスト性に適合する複雑性尺度に依存する下界を示す。 0.64
Closer to our work, Diochnos et al [8, 9] exhibit lower bounds for the exact-in-the-ball robust risk. diochnos et al [8, 9]は我々の研究に近く、正確なボール内ロバストなリスクの限界を低く示しています。 0.54
They focus on a family of concentrated distributions, Normal L´evy families, which include, for e g , the Gaussian distribution on Rn and product distribution of dimension n under the Hamming distance.2 彼らは集中分布の族、正規 L ́evy 族に焦点を合わせ、例えば、Rn 上のガウス分布と、ハミング距離 2 の下での次元 n の積分布を含む。 0.77
Instead of looking at a specific class of functions, they allow any concept class that contain concepts that have small enough (2−Θ(n)) standard error with respect to each other, and so would be indistinguishable for sufficiently small samples. 関数の特定のクラスを見る代わりに、各クラスは、互いに十分に小さい(2−)(n))標準誤差を持つ概念を含む任意の概念クラスを許容するので、十分小さなサンプルに対して区別できない。 0.85
Note that monotone conjunctions satisfy this property. 単調結合はこの性質を満たすことに注意。 0.64
When considering the Boolean hypercube and an adversary that can perturb ρ bits of the input, they get that any robust PAC learning algorithm for their robust learning setting requires a sample of size 2Ω(ρ2/n). ブールハイパーキューブと、入力のρビットを摂動できる逆数を考えると、堅牢な学習環境でのPAC学習アルゴリズムには2Ω(ρ2/n)のサンプルが必要である。 0.71
Note that this lower bound is non trivial only when considering adversaries that can perturb √n bits or more, while we show a lower bound that is strictly exponential in the adversary’s budget (though for slightly more restricted concept classes), and thus meaningful for a wider class of adversaries. 注意すべきなのは、この下限が非自明であるのは、アンビット以上を摂動できる敵を考える場合のみであり、一方、下限は、敵の予算において厳密に指数関数的である(ただし、より制限された概念クラスについては)。 0.65
In terms of sample complexity upper bounds, Montasser et al [23] show sample complexity upper bounds that are linear (ignoring log factors) in the VC dimension and the dual VC dimension of a concept class under the constant-in-the-ball notion of robustness, yielding an exponential upper bound in the VC dimension. サンプル複雑性上界に関して、Montasser et al [23] は、VC次元において線形な(対数要素を無視する)サンプル複雑性上界と、ボール内のロバスト性の概念の下で概念クラスの双対VC次元を示し、VC次元において指数的な上界をもたらす。 0.70
As noted in [17], their techniques do not apply to the exact-in-the-ball setting, which is studied for evasion attacks notably in [7, 22, 21, 16, 17]. この手法は,[7, 22, 21, 16, 17]において特に回避攻撃について研究されている, ボールの正確な設定には適用されない。 0.71
The work of Diochnos et al [7] addresses the ability of an adversary to cause a blow up the adversarial error with respect to the standard error. Diochnos et al [7] の作業は、標準的なエラーに関して敵の誤りを爆発させる敵の能力に対処する。 0.66
For instance, they show that, under the uniform distribution, a O(√n)-bounded adversary can cause the probability of a misclassification to be 1/2 given that the standard error is 0.01 for any learning problem. 例えば、一様分布の下では、任意の学習問題に対して標準誤差が 0.01 であることを考えると、O(n)-有界敵は誤分類の確率を1/2 にすることができる。 0.84
These results are extended by Mahloujifar et al [21] for a wider family of distributions. これらの結果はmahloujifar et al [21]によりより広い分布に拡張された。 0.72
Finally, Gourdeau et al [17] exhibit sample complexity upper bounds for the robust learnability of a variety of concept classes (parities, monotone decision lists, and decision trees) under log-Lipschitz distributions for various adversarial budgets. 最後に、Gourdeau et al [17] は様々な概念クラス(パーティ、モノトーン決定リスト、決定ツリー)の様々な逆の予算に対する対数-リプシッツ分布の頑健な学習性に対するサンプル複雑性上限を示す。 0.79
2 Problem Set Up In this section, we will first recall two definitions of robustness that have been widely used in the literature, and formalize the notion of robustness thresholds in the robust PAC-learning framework. 2つの問題設定 本稿では,文献で広く使われているロバストネスの定義を2つ思い出し,ロバストPAC学習フレームワークにおけるロバストネスしきい値の概念を定式化する。 0.74
We will then review relevant concept classes for this paper, as well as log-Lipschitz distributions, which were introduced in [1] and will be the focus of our results. 次に、本論文の関連する概念クラスと、[1] で導入され、その結果の焦点となる log-Lipschitz 分布について検討する。 0.71
2.1 Robust Learning 2.1 ロバスト学習 0.72
We work in the PAC learning framework of Valiant [28] (see Appendix A.1), but where the (standard) risk function is replaced by a robust risk function. 私たちは、Valiant [28]のPAC学習フレームワーク(Appendix A.1参照)で作業していますが、(標準)リスク関数が堅牢なリスク関数に置き換えられます。 0.68
Since we focus on the Boolean hypercube {0, 1}n as the input space, the only relevant notion of distance between points is the Hamming distance (denoted dH), i.e., the number of bits that differ between two points. 入力空間としてブールハイパーキューブ {0, 1}n にフォーカスするため、点間の距離に関する唯一の関連する概念はハミング距離(dH)である。
訳抜け防止モード: Boolean hypercube { 0, 1}n を入力空間とするからである。 点間の距離に関する唯一の関連する概念はハミング距離(dH と表記される)である。 つまり 2つの点で異なるビットの数です
0.75
Thus, the adversary’s perturbation budget will be the number of bits of the input the adversary is allowed to flip to cause a misclassification. したがって、敵の摂動予算は、敵がひっくり返して誤った分類を引き起こすことを許される入力のビット数である。 0.56
We will use the exact-in-the-ball definition of robust risk (which is called errorregion risk in [7]). 堅牢なリスク( [7] では errorregion risk と呼ばれます)を正確に定義します。 0.77
Given respective hypothesis and target functions h, c : X → {0, 1}, distribution それぞれの仮説と対象関数 h, c : X → {0, 1} が与えられたとき、分布 0.85
2We work with the uniform distribution, which is a special case of product distributions. 2 製品分布の特殊な場合である均一分布を扱う。 0.63
3 3 0.42
英語(論文から抽出)日本語訳スコア
ρ (h, c) = Pr x∼D ρ (h, c) = pr である。 0.85
D on X , and robustness parameter ρ ≥ 0, the exact-in-the-ball robust risk of h with respect to c is (∃z ∈ Bρ(x) : h(z) 6= c(z)), where Bρ(x) = {z ∈ {0, 1}n | dH (x, z) ≤ ρ}. bρ(x) = {z ∈ {0, 1}n | dh(x, z) ≤ ρ} ここで、c に関する h の球内ロバストなリスクは (z ∈ bρ(x) : h(z) 6= c(z)) である。
訳抜け防止モード: X 上とロバストネスパラメータ ρ ≥ 0 上、c に関する h の正確な - in - 球のロバストリスクは、( )z ∈ Bρ(x ) : h(z ) 6= c(z ) ) である。 ここで Bρ(x ) = { z ∈ { 0, 1}n | dH ( x, z ) ≤ ρ } .
0.88
defined as RE This is in contrast to the more widely-used constant-in-the-ball risk function (also called corruptedinstance risk from the work of Feige et al [14]) RC (∃z ∈ Bρ(x) : h(z) 6= c(x)) where the hypothesis is required to be constant in the perturbation region in addition to being correct with respect to the unperturbed point’s label c(x). RE として定義されるこの関数は、より広く使われている定数-in-the-ball の危険関数(Feige et al [14]) RC (\z ∈ Bρ(x) : h(z) 6= c(x)) とは対照的である。
訳抜け防止モード: REとして定義されるこの関数は、より広く使われる定数 in - において、-ボールリスク関数(Feige et al [14 ] ) RC ( shz ∈ Bρ(x ) : h(z ) 6= c(x ) ) と対照的である。 摂動領域において一定であるさま 非摂動点 のラベル c(x) に関して正しいことに加えて、
0.75
ρ (h, c) = Pr x∼D ρ (h, c) = pr である。 0.85
Both Diochnos et al [7] and Gourdeau et al [17] offer a thorough discussion on the advantages and drawbacks of the two notions of robust risk. Diochnos et al [7] と Gourdeau et al [17] はどちらも、堅牢なリスクという2つの概念の利点と欠点について、徹底的に議論している。 0.64
We will study the exact-in-the-ball robust risk, as our learning problems have considerable probability mass near the decision boundary. 我々は,学習課題が決定境界付近にかなりの確率質量を持つため,ボール内厳密なリスクの研究を行う。 0.74
Thus it makes sense to consider the faithfulness of the hypothesis with respect to the target function. したがって、対象関数に対する仮説の忠実さを考えることは理にかなっている。 0.74
The exact-in-the-ball robust risk also has various advantages: if the distribution is supported on the whole input space (e g , the uniform distribution), exact learnability implies robust learnability and the target concept is always the robust risk minimizer.3 ボール内ロバストリスクは、入力空間全体(例えば一様分布)で分布がサポートされている場合、正確な学習性はロバストな学習可能性を示し、目標概念は常にロバストリスク最小化器である。
訳抜け防止モード: 正確な-------ボールロバストリスクにも様々な利点がある : 入力空間全体(例えば一様分布)で分布が支持されている場合 正確な学習性は 目標とする概念は 常に 頑丈なリスク最小化装置です
0.81
We have from Gourdeau et al [17] the following definition of robust learnability with respect to the exact-in-the-ball robust risk. Gourdeau氏ら[17]は、ボール内の正確な堅牢なリスクに関して、以下の堅牢な学習可能性の定義を持っています。 0.46
Note that we will henceforth drop the superscript and simply use Rρ to denote the exact-in-the-ball robust risk. したがって、我々はスーパースクリプトを降ろし、単にRρを使ってボール内の正確なロバストリスクを示すことに注意する。 0.51
Definition 1. Fix a function ρ : N → N. We say that an algorithm A efficiently ρ-robustly learns a concept class C with respect to distribution class D if there exists a polynomial poly(·,·,·,·) such that for all n ∈ N, all target concepts c ∈ Cn, all distributions D ∈ Dn, and all accuracy and confidence parameters ǫ, δ > 0, if m ≥ poly(n, 1/ǫ, 1/δ, size(c)), whenever A is given access to a sample S ∼ Dm labelled according to c, it outputs a polynomially evaluable function h : {0, 1}n → {0, 1} such that Pr 定義1。 すべての n ∈ N に対し、すべての対象概念 c ∈ Cn と全ての分布 D ∈ Dn と全ての精度および信頼パラメータ φ, δ > 0 に対して、m ≥ poly(n, 1/i, 1/δ, size(c)) が成り立つとき、A は c に従ってラベル付けされたサンプル S > Dm へのアクセスを与えられるとき、多項式的に評価可能な関数 h : {0, 1}n → {0, 1} を出力する多項式的ポリ(·,·,·,·) が存在する。
訳抜け防止モード: 定義1。 アルゴリズム A が効率的な ρ - 多項式ポリ ( · ) が存在する場合、分布クラス D に関する概念クラス C を頑健に学習する。 すべての n ∈ N に対して ·, ·, · ) である。 すべての対象概念 c ∈ Cn, すべての分布 D ∈ Dn, 精度と信頼性のパラメータは δ > 0 である。 m ≥ poly(n, 1 / s, 1 / δ, size(c ) ) A が c に従ってラベル付けされたサンプル S > Dm へのアクセスを与えられるとき、 多項式的に評価可能な関数 h : { 0, 1}n → { 0 を出力する。 1 } Pr
0.77
S∼Dm (Rρ(h, c) < ǫ) > 1 − δ. 佐々木 (rρ(h, c) < ...) > 1 − δ である。 0.50
2.2 Concept Classes and Distribution Families 2.2 概念クラスと流通家族 0.83
Our work uses formulas in the conjunctive normal form (CNF) to show the robust learnability of decision lists. 我々の研究は、決定リストの堅牢な学習可能性を示すために、連結正規形式(CNF)の式を用いる。
訳抜け防止モード: 我々の研究は共役正規形式(CNF)の式を用いる。 意思決定リストの堅牢な学習可能性を示すためです
0.64
This concept class was proposed and shown to be PAC learnable by Rivest [24]. この概念クラスが提案され, Rivest [24] が PAC を学習可能であることを示した。 0.74
Formally, given the maximum size k of a conjunctive clause, a decision list f ∈ k-DL is a list (K1, v1), . . . , (Kr, vr) of pairs where Kj is a term in the set of all conjunctions of size at most k with literals drawn from {x1, ¯x1, . . . , xn, ¯xn}, vj is a value in {0, 1}, and Kr is true. 形式的には、連結節の最大サイズ k が与えられたとき、決定リスト f ∈ k-dl はリスト (k1, v1, . . . , (kr, vr) であり、kj は最大 k におけるすべての大きさの結合の集合の項であり、 {x1, sx1, . . , xn, sxn}, vj は {0, 1} の値であり、kr は真である。 0.83
The output f (x) of f on x ∈ {0, 1}n is vj, where j is the least index such that the conjunction Kj evaluates to true. x ∈ {0, 1}n 上の f の出力 f (x) は vj である。
訳抜け防止モード: x ∈ { 0, 1}n 上の f の出力 f ( x ) は vj である。 ここで、j は結合 kj が真であると評価する最小の指標である。
0.82
Given k, n ∈ N, we denote by ϕ a k-CNF on n variables, where k refers to the size of the largest clause in ϕ. k, n ∈ n が与えられたとき、g は n 変数上の φ a k-cnf で表され、k は φ の最大の節の大きさを指す。
訳抜け防止モード: k, n ∈ N が与えられたとき、n 変数上の φ a k - CNF で表す。 ここで k は φ で最大の節のサイズを指します
0.81
Note that the class MON-CONJ of monotone conjunctions, where each variable appears as a positive literal, is a subclass of 1-CNF formulas. 各変数が正のリテラルとして現れる単調接続の MON-CONJ クラスは 1-CNF 式の部分クラスである。 0.75
Moreover, since decision lists generalize formulas in disjunctive normal form (DNF) and conjunctive normal form, in the sense that k-CNF ∪ k-DNF ⊆ k-DL, a robust learnability result for k-DL holds for k-CNF and k-DNF as well. さらに、決定リストは、解離正規形 (DNF) と共役正規形 (conjunctive normal form) の式を一般化するので、k-CNF は k-DNF であり、k-DL は k-CNF と k-DNF も頑健な学習性を持つ。 0.62
We refer the reader to Appendix A.2 for more background on conjunctions and k-CNF formulas. 読者はappendix a.2を参照し、結合子とk-cnf公式についてより詳しい背景を述べる。 0.51
(x |= ϕ) that x drawn from distribution D results in a satisfying assignment of ϕ. (x |= φ) 分布 D から引き出された x は φ の満足な割り当てをもたらす。 0.86
We will also denote the probability mass Pr x∼D 確率質量 Pr x {\displaystyle x} も表す。 0.68
For a formula ϕ, we will denote by S0(ϕ) the probability Pr x∼D 公式 φ に対して、確率 Pr x = D を S0(φ) で表す。 0.82
(∃z ∈ Bρ(x) . (z ∈ Bρ(x) 。 0.84
z |= ϕ) of the ρ-expansion of a satisfying assignment by Sρ(ϕ). z |= φ) は sρ(φ) による満足する代入の ρ-展開である。 0.76
3This is not necessarily the case with the constant-in-the-ball definition [17]. 3 これは必ずしもconstant-in-the-ball 定義[17]の場合ではない。 0.63
4 4 0.42
英語(論文から抽出)日本語訳スコア
Our robust learnability results will hold for a class of sufficiently smooth distributions, called 私たちの頑健な学習可能性の結果は十分滑らかな分布のクラスを保ちます 0.70
log-Lipschitz distributions, originally introduced by Awasthi et al [1]: Definition 2. log-Lipschitz 分布は Awasthi et al [1] によって最初に導入された。 0.70
A distribution D on {0, 1}n is said to be α-log-Lipschitz if for all input points x, x′ ∈ {0, 1}n, if dH(x, x′) = 1, then | log(D(x)) − log(D(x′))| ≤ log(α). 0, 1}n 上の分布 D が α-log-Lipschitz であるとは、すべての入力点 x, x′ ∈ {0, 1}n に対して dH(x, x′) = 1 であれば | log(D(x)) − log(D(x′))| ≤ log(α) が成り立つことである。 0.93
Neighbouring points in {0, 1}n have probability masses that differ by at most a multiplicative factor of α under α-log-Lipschitz distributions. 0, 1}n の近傍の点は α-log-lipschitz 分布の下で α の乗法係数の最大値が異なる確率質量を持つ。 0.76
The decay of probability mass along a chain of neighbouring points is thus at most exponential; not having sharp changes to the underlying distribution is a very natural assumption, and one weaker than many often make in the literature. したがって、近傍点の連鎖に沿った確率質量の減衰は、最も指数関数的であり、基底分布に鋭い変化がないことは、非常に自然な仮定であり、多くの文献でしばしばなされるよりも弱いものである。 0.71
Note that features are allowed a small dependence between each other and, by construction, log-Lipschitz distributions are supported on the whole input space. 特徴は互いに小さな依存を許容し、構成により、対数Lipschitz分布は入力空間全体において支持される。 0.69
Notable examples of log-Lipschitz distributions are the uniform distribution (with parameter α = 1) and the class of product distributions with bounded means. ログリプシッツ分布の有名な例は(パラメータ α = 1 を持つ)一様分布と有界な平均を持つ積分布のクラスである。 0.84
3 The log(n)-Expansion of Satisfying Assignments for k-CNF For- 3 log(n)-k-CNF For に対する Satisfying Assignments の拡張- 0.91
mulas In this section, we show that, under log-Lipschitz distributions, the probability mass of the log(n)expansion of the set of satisfying assignments of a k-CNF formula can be bounded above by an arbitrary constant ε > 0, given an upper bound on the probability of a satisfying assignment. ムラス この節では、対数-Lipschitz分布の下で、k-CNF式を満足する代入の集合の log(n) 展開の確率質量は、満足する代入の確率上の上限が与えられたとき、任意の定数 ε > 0 で上限付けられることを示す。 0.55
The latter bound is polynomial in ε and 1/n. 後者の境界は ε と 1/n の多項式である。 0.66
While this result is of general interest, our goal is to prove the efficient robust learnability of decision lists against a log(n)-bounded adversary. この結果は一般的な関心事であるが、我々のゴールは、ログ(n)-バウンドされた敵に対して、決定リストの効率的な堅牢な学習可能性を証明することである。
訳抜け防止モード: この結果は一般的な関心事ですが 目標は ログ(n)境界付けられた敵に対する決定リストの効率的な学習性を証明する。
0.68
Here the relevant fact is that, given two decision lists c, h ∈ k-DL, the set of inputs in which c and h differ can be written as a disjunction of quadratically many (in the combined length of c and h) k-CNF formulas. ここで関連する事実は、二つの決定リスト c, h ∈ k-dl が与えられたとき、c と h が異なる入力の集合は(c と h の合計長さにおいて)二次的に多くの k-cnf の公式の和として書けることである。
訳抜け防止モード: ここで関連する事実は、2つの決定リストが与えられたとき、 c と h が異なる入力の集合である h ∈ k - DL は2次数の和として書くことができる (cとhの組合せで)k- CNF式。
0.81
The log(n)-expansion of this set is then the set of inputs where a log(n)-bounded adversary can force an error at test time. この集合の log(n)-展開は、log(n)-bounded adversary がテスト時にエラーを強制できる入力の集合である。
訳抜け防止モード: log(n)-expansion of this set is the set of inputs where log(n)-bounded adversary はテスト時にエラーを強制することができる。
0.76
This is the main technical contribution of this paper, and the theorem is stated below. これは本論文の主な技術的貢献であり、以下にその定理を述べる。 0.74
The combinatorial approach, below, vastly differs from the approach of [17] in the special case of monotone k-DL, which relied on facts about propositional logic. 下記の組合せ的アプローチは、命題論理に関する事実に依存する単調なk-DLの特殊な場合における[17]のアプローチとは大きく異なる。 0.79
Theorem 3. Suppose that ϕ ∈ k-CNF and let D be an α-log-Lipschitz distribution on the valuations of ϕ. 理論3。 φ ∈ k-CNF と D を φ の値上で α-log-Lipschitz 分布とする。 0.72
Then there exist constants C1, C2, C3, C4 ≥ 0 that depend on α and k such that if the probability of a satisfying assignment satisfies S0(ϕ) < C1εC2 min(cid:8)εC3, n−C4(cid:9), then the log(n)expansion of the set of satisfying assignments has probability mass bounded above by ε. すると、 α と k に依存する定数 C1, C2, C3, C4 ≥ 0 が存在し、満足な代入の確率が S0(φ) < C1εC2 min(cid:8)εC3, n−C4(cid:9) を満たすなら、満足な代入の集合の log(n) 展開は ε によって上界される確率質量を持つ。 0.78
Corollary 4. The class of k-decision lists is efficiently log(n)-robustly learnable under log-Lipschitz distributions. 第4回。 k-決定リストのクラスは、log-Lipschitz分布の下で効率的にlog(n)-robustly学習可能である。 0.58
The proof of Corollary 4 is similar to Theorem 24 in [17], and is included in Appendix B. We note that it is imperative that the constants Ci do not depend on the learning parameters or the Corollary 4の証明は[17]のTheorem 24と似ており、Appendix Bに含まれている。
訳抜け防止モード: Corollary 4 の証明は[17 ] における Theorem 24 と似ている。 Appendix Bに含まれる。 定数 Ci が学習パラメータやパラメータに依存しないことは必須である。
0.73
input dimension, as the quantity C1εC2 min(cid:8)εC3, n−C4(cid:9) is directly used as the accuracy parameter 入力次元は、C1εC2 min(cid:8)εC3,n−C4(cid:9)を直接精度パラメータとして使用する。 0.66
in the (proper) PAC learning algorithm for decision lists, which is used as a black box. ブラックボックスとして使用される意思決定リストのための(プロパ)pac学習アルゴリズムで。 0.74
To prove Theorem 3, we will need several lemmas outlined below, which are either taken directly or slightly adapted from [17]. 定理 3 を証明するには、下記に概説したいくつかの補題が必要となる。
訳抜け防止モード: 定理3を証明するために 以下に概説するいくつかの補題が必要です 17]から直接、またはわずかに順応する。
0.67
The first is an adaptation of Lemma 17 in [17] for conjunctions, which was originally stated for decision lists: 1つ目は、[17]において、決定リストに記載された共同作業のためのLemma 17の適応である。 0.64
5 5 0.42
英語(論文から抽出)日本語訳スコア
Lemma 5. Let ϕ be a conjunction and let D be an α-log-Lipschitz distribution. 第5回。 φ を接続とし、D を α-log-Lipschitz 分布とする。 0.64
If Pr x∼D (1 + α)−d, then ϕ is a conjunction on at least d variables. pr が (1 + α)−d であれば、 φ は少なくとも d 変数上の結合である。 0.81
(x |= ϕ) < (x |= φ) < 0.49
The second result, which states an upper bound on the expansion of satisfying assignments for 第2の結果は、満足な代入の展開に関する上限を述べたものである。 0.73
conjunctions, will be used for the base case of the induction proof. 共用器は 誘導証明の ベースケースに使用される。 0.51
Lemma 6. Let D be an α-log-Lipschitz distribution on the n-dimensional Boolean hypercube and let ϕ be a conjunction of d literals. 第6回。 D を n-次元ブールハイパーキューブ上の α-log-Lipschitz 分布とし、φ を d リテラルの連結とする。 0.67
Set η = 1 then Pr x∼D η = 1 を Pr x = D とする。 0.56
1+α . Then for all 0 < ε < 1/2, if d ≥ maxn 4 1+α . このとき、すべての 0 < ε < 1/2 に対して、d ≥ maxn 4 が成り立つ。 0.51
((∃y ∈ Bρ(x) · y |= ϕ)) ≤ ε. ((y ∈ bρ(x) · y |= φ)) ≤ ε である。 0.92
η o, ε(cid:1) , 2ρ η o, ε(cid:1), 2ρ 0.49
η2 log(cid:0) 1 η2 log(cid:0) 1 0.41
Finally, we will use the following lemma, which will be used in the inductive step of the induction 最後に、誘導の誘導段階において使用される次の補題を用いる。 0.64
proof. Lemma 7. Let ϕ be a k-CNF formula that has a set of variable-disjoint clauses of size M . 証明だ 第7回。 φ を k-CNF の公式とし、大きさ M の変分節の集合とする。 0.66
Let D be an α-log-Lipschitz distribution on valuations for ϕ. D を φ の値の α-log-Lipschitz 分布とする。 0.74
Let 0 < ε < 1/2 be arbitrary and set 0 < ε < 1/2 を任意とし、集合とする 0.74
η := (1 + α)−k. η := (1 + α)−k。 0.44
If M ≥ maxn 4 M ≥ maxn 4 ならば 0.95
η2 log(cid:0) 1 η2 log(cid:0) 1 0.41
ε(cid:1) , 2ρ ε(cid:1), 2ρ 0.45
η o then Pr x∼D η o と pr x‐D 0.38
(∃y ∈ Bρ(x) · y |= ϕ) ≤ ε. (y ∈ bρ(x) · y |= φ) ≤ ε である。 0.90
We are now ready to prove Theorem 3. 私たちは現在、Theorem 3を証明する準備ができています。 0.59
The main idea behind the proof is to consider a given k-CNF formula ϕ and distinguish two cases: 証明の主な考え方は、与えられた k-CNF の公式 φ を考慮し、2つのケースを区別することである。
訳抜け防止モード: 証明の主な考え方は 与えられた k - CNF の公式 φ を考え、二つのケースを区別する。
0.66
(i) either ϕ contains a sufficiently-large set of variabledisjoint clauses, in which case the adversary is not powerful enough to make ϕ satisfied by Lemma 7; or (i) φ が十分大きな変数分離節を含むか、その場合、敵は φ を補題 7 で満足させるほど強力ではないか、
訳抜け防止モード: (i) または φ は、十分に大きな変数分離節を含む。 この場合、敵は φ を lemma 7 で満足させるほど強力ではない。
0.71
(ii) we can rewrite ϕ as the disjunction of a sufficiently small number of (k − 1)-CNF formulas, which allows us to use the induction hypothesis to get the desired result. (ii) φ を十分少ない数の (k − 1)-cnf の公式の切断として書き直すことができ、帰納的仮説を用いて所望の結果を得ることができる。 0.80
The final step of the proof is to derive the constants mentioned in the statement of Theorem 3. 証明の最終ステップは、定理3のステートメントで言及される定数を導出することである。 0.78
Proof of Theorem 3. We will use the lemmas above and restrictions on ϕ to show the following. 定理3の証明。 上記の補題と φ の制限を使って、以下のように示す。 0.66
Induction hypothesis: Suppose that ϕ ∈ (k − 1)-CNF and let D be an α-log-Lipschitz distribution on the valuations of ϕ. 帰納仮説: φ ∈ (k − 1)-CNF を仮定し、D を φ の付値上の α-log-Lipschitz 分布とする。 0.83
Then there exists constants C1, C2, C3, C4 ≥ 0 that depend on α and k and satisfy C3 ≥ η このとき、α と k に依存して C3 ≥ η を満たす定数 C1, C2, C3, C4 ≥ 0 が存在する。 0.77
2 C4 such that if S0(ϕ) < C1εC2 min(cid:8)εC3, n−C4(cid:9), then Slog(n)(ϕ) ≤ ε. S0(φ) < C1εC2 min(cid:8)εC3, n−C4(cid:9) であれば、Slog(n)(φ) ≤ ε となる。 0.78
Base case: This follows from Lemmas 5 and 6. ベースケース: Lemmas 5 と 6 から続く。 0.60
Set η to (1 + α)−1, and C1 = 1, C2 = 0, C3 = 4 η2 η を (1 + α)−1 とし、c1 = 1, c2 = 0, c3 = 4 η2 とする。 0.83
and C4 = 2 そして c4 = 2 0.92
η . Note that C3 ≥ η η . c3 ≥ η に注意。 0.59
2 C4. Inductive step: Suppose ϕ ∈ k-CNF and let D be an α-log-Lipschitz distribution on the valua4 be the constants in the induction hypothesis for 2C4。 帰納段階: φ ∈ k-CNF とし、D を valua4 上の α-log-Lipschitz 分布とし、誘導仮説の定数とする。 0.60
3, C ′ 2, C ′ tions of ϕ. 3, C' 2 c ′ の φ の割数。 0.56
Set η = (1 + α)−k. η = (1 + α)−k とする。 0.84
Let C ′ ϕ′ ∈ (k − 1)-CNF. C ′ φ′ ∈ (k − 1)-CNF とする。 0.88
Set the following constants: 12−k(C ′ C1 = C ′ C2 = C ′ 2 + C ′ 3 8 12−k(c ′ c1 = c ′ c2 = c ′ 2 + c ′ 3 8 とする。 0.82
1, C ′ and note that these are all constants that depend on k and α by the induction hypothesis, and that C3 ≥ η 1, c ′ そしてこれらは全て帰納仮説によって k と α に依存する定数であり、C3 ≥ η である。 0.63
2 C4. 2+C ′ 3) 2C4。 2+c′′) である。 0.45
2, C ′ 2, C ′ 2, C' 2, C' 0.37
C3 = C4 = η2 max(cid:8)C ′ max(cid:8)C ′ C3 = C4 = η2 max(cid:8)C ′ max(cid:8)C ′ 0.44
2 η 3(cid:9) 3(cid:9) , 2 η 3(cid:9) 3(cid:9) , 0.42
6 6 0.43
英語(論文から抽出)日本語訳スコア
Let S0(ϕ) < C1εC2 min(cid:8)εC3, n−C4(cid:9). S0(φ) < C1εC2 min(cid:8)εC3, n−C4(cid:9) とする。 0.61
Let M be a maximal set of clauses of ϕ such that no two clauses contain the same variable. M を φ の節の最大集合とし、2つの節が同じ変数を含まないようにする。 0.73
Denote by IM the indices of the variables in M and let M = maxn 4 IMで注意: M の変数の指数を M = maxn 4 とする。 0.76
η log no. η2 log 1 η log no. η2 log 1 0.45
ε , 2 We distinguish two cases: ε , 2 2つの事例を区別します 0.49
(i) |M| ≥ M : We can then invoke Lemma 7 and guarantee that S (i) |M| ≥ M : すると Lemma 7 を呼び出して S を保証できる 0.90
log(n) ≤ ε, and we get the required result. log(n) ≤ ε とすると、必要な結果が得られる。 0.83
(ii) |M| < M : Then let AM be the set of assignments of variables in M, i.e. a ∈ AM is a function a : IM → {0, 1}, which represents a partial assignment of variables in ϕ. (ii) |M| < M : 次に AM を M 内の変数の代入集合とし、すなわち a ∈ AM は φ 内の変数の部分代入を表す函数 a : IM → {0, 1} である。 0.81
We can thus rewrite ϕ as follows: したがって φ を次のように書き直すことができる。 0.58
ϕ ≡ _a∈AM  ϕa ∧ ^i∈IM li  , φ 初出は『i』。 という。 0.16
where ϕa is the restriction of ϕ under assignment a and li is xi in case a(i) = 1 and ¯xi otherwise. φa は代入 a の下で φ の制限であり、li は a(i) = 1 と xi がそうでなければ xi である。 0.75
For short, denote by ϕ′ mentions some variable in M, and hence ϕ′ in the sense that if some assignment x satisfies ϕ′ b. すなわち、ある代入 x が φ′ b を満たすという意味で φ′ は m の変数に言及される。 0.62
Note also that a the formula ϕa ∧Vi∈IM li. 注意点 式 φa は li である。 0.49
By the maximality of M every clause in ϕ An,ε := |AM| ≤ 2k max((cid:18) 1 S0(ϕ) = Xa∈AM x∼D(cid:0)x |= ϕ′ M の極大性により、φ An,ε := |AM| ≤ 2k max((cid:18) 1 S0(φ) = Xa⋅AM x\D(cid:0)x |= φ′ の全ての節は最大である。 0.67
ε(cid:19)4/η2 a(cid:1) = Xa∈AM ε(cid:19)4/η2 a(cid:1) = Xa・AM 0.30
a is (k− 1)-CNF. a は (k− 1)-CNF である。 0.80
Moreover, the formulas ϕ′ さらに φ′ の式も 0.84
a are disjoint, b for a distinct index a は解離し、b は別個の指数を表す 0.61
a, it will not satisfy another ϕ′ a, 他の φ′ を満たさない 0.81
, n2/η) . S0(ϕ′ ,n2/η)。 s0(φ') 0.47
Thus, a) . したがって a) である。 0.65
(1) Pr By the induction hypothesis, we can guarantee that if (1) Pr 帰納仮説により、もしもそれが保証できる。 0.46
S0(ϕ′ a) < C ′ s0(φ') a) < C ′ 0.39
An,ε(cid:19)C ′ 1(cid:18) ε An,ε(cid:19)C ′ 1(cid:18)ε 0.45
2 min((cid:18) ε 2 min((cid:18) ε 0.44
An,ε(cid:19)C ′ An,ε(cid:19)C ′ 0.48
3 , n−C ′ 4) 3 , n−c′ 4) 0.40
for all ϕ′ すべてのφ'に対して 0.51
a then the log(n)-expansion Slog(n)(ϕ) can be bounded as follows: このとき、log(n)-expansion slog(n)(φ) は次のように有界である。 0.73
S log(n)(ϕ) = Pr x∼D S log(n)(φ) = Pr x = D 0.44
(∃z ∈ Blog n(x) . (z ∈ Blog n(x) )。 0.83
z |= ϕ) x∼D(cid:0)∃z ∈ Blog n(x) . z |= φ) x-d(cid:0)-z ∈ blog n(x) 。 0.78
z |= ϕ′ a(cid:1) z |= φ′ a(cid:1) 0.39
Pr = Xa∈AM ≤ Xa∈AM Pr =Xa・AM≤Xa・AM 0.41
= ε . ε An,ε = ε . ε An,ε 0.42
(2) (I.H.) (2) (I.H.) 0.42
fying assignment for ϕ implies an upper bound S0(ϕ′ φ のfying代入は上界 s0(φ′) を意味する 0.68
By Equation 1, the upper bound S0(ϕ) < C1εC2 min(cid:8)εC3, n−C4(cid:9) on the probability of a satisa) < C1εC2 min(cid:8)εC3, n−C4(cid:9) on the probability 方程式 1 により、上界 S0(φ) < C1εC2 min(cid:8)εC3, n−C4(cid:9) は a satisa) < C1εC2 min(cid:8)εC3, n−C4(cid:9) の確率である。 0.69
7 7 0.42
英語(論文から抽出)日本語訳スコア
of the restrictions ϕ′ Equation 2 holds. 制限 φ′ 方程式 2 は成立する。 0.77
a. Thus it only remains to show that the condition on S0(ϕ) implies that aだ したがって、s0(φ) の条件は、そのことを暗示するだけである。 0.70
Let us rewrite the RHS of Equation 2 as follows, where each of the equations is a stricter 式 2 の rh を次のように書き直すと、各方程式はより厳密である。 0.75
condition on S0(ϕ′ a) than its predecessor: S0(φ′ の条件 a) 前者より大きい。 0.65
C ′ 2 An,ε(cid:19)C ′ 1(cid:18) ε 2k(cid:17)C ′ 1(cid:16) ε ≥ C ′ 2k(cid:17)C ′ 1(cid:16) ε C' 2 An,ε(cid:19)C ′ 1(cid:18) ε 2k(cid:17)C ′ 1(cid:16) ε ≥ C ′ 2k(cid:17)C ′ 1(cid:16) ε 0.39
= C ′ 2 2 c' である。 2 2 0.44
min((cid:18) ε minnε4C ′ minnε4C ′ min((cid:18) ε minnε4C ′ minnε4C ′ 0.34
= C ′ ≥ C ′ = C ′ = C ′ ≥ C ′ = C ′ 0.43
12−k(C ′ 12−k(C ′ 12−k(C ′ 12−k(C ′ 12−k(C ′ 12−k(C ′)′ 0.36
2+C ′ 3)εC ′ 2+C' 3)εC' 0.63
2+C ′ 2+C ′ 3)εC ′ 2+C' 2+C' 3)εC' 0.53
2+C ′ 2+C ′ 3)εC ′ 2+C' 2+C' 3)εC' 0.53
2+C ′ = C1εC2 min(cid:8)εC3, n−C4(cid:9) , 3 ≥ η 2+C' = C1εC2 min(cid:8)εC3, n−C4(cid:9) , 3 ≥ η 0.33
2 C ′ 3 An,ε(cid:19)C ′ 2 C ′ 3 An,ε(cid:19)C ′ 0.44
, n−C ′ 2/η2 , n−c′ 2/η2 0.29
, n−2C ′ 2/η2 ,n−2C ′ 2/η2 0.43
, n−2C ′ 2/η2 ,n−2C ′ 2/η2 0.43
3 minnε4C ′ 3 minnε8C ′ 3 minnε8 max{C ′ 3 minnε4C ′ 3 minnε8C ′ 3 minnε8 max{C ′ 0.36
2/η2 4) 2k ! 2/η2 4) 2k! 0.36
C ′ 2/ηo min ε1+4/η2  2k ! ε1+4/η2+2k! 0.34
C ′ 2/ηo min ε1+4/η2  2/ηo minnε4C ′ , n−4C ′ , n−4 max{C ′ 3}/η2 c ′ 2/ηo min ε1+4/η2 , 2/ηo minnε4c ′ , n−4c ′ , n−4 max{c ′ 3}/η2
訳抜け防止モード: C ′ 2 / ηo min = ε1 + 4 / η2 > 2 / ηo minnε4C ′ である。 n−4C ′ , n−4 max{C ′ 3}/η2
0.54
2/η, ε8C ′ , n−2C ′ 2/η,ε8C′ ,n−2C ′ 0.47
3/η2 2,C ′ 3/η2 2,c ′ 0.31
3 3 , n−C ′ 3 3 , n−c′ 0.40
4  3 2k ! 4  3 2K! 0.56
C ′ , εn−2/η 2k ! C ′ , εn−2/η 2k ! 0.32
C ′ 3 , εn−2/η  3/ηo εn−2/η > 3/ηo 0.30
, n−2C ′ 3/η2 ,n−2C ′ 3/η2 0.43
, n−4C ′ 2,C ′ ,n−4C ′ 2,c ′ 0.51
3/ηo 3}/ηo 3/ηo 3}/ηo 0.29
where the first step is by definition of An,ε, the second from the induction hypothesis, which guarantees C ′ Finally, the last equality follows by the definition of the Ci’s. 最初のステップが an,ε の定義であり、c ′ を最終的に保証する帰納的仮説からの第二のステップであるとき、最後の等式は ci の定義によって従う。 0.82
4, and the fourth from the property min{a, b}· min{c, d} ≥ min(cid:8)a2, b2, c2, d2(cid:9). 4 は、min{a, b}· min{c, d} ≥ min(cid:8)a2, b2, c2, d2(cid:9) から得られる。 0.90
Note that we set η = (1+α)−k to be able to apply Lemma 7 in the first part of the inductive step. ここでは η = (1+α)−k を、帰納段階の最初の部分でLemma 7 を適用することができるように設定する。 0.69
Then, An,ǫ is a function of η = (1 + α)−k. すると、An は η = (1 + α)−k の函数である。 0.78
When we consider the distribution on the valuations of the restriction ϕ′ a, we still operate with an α-log-Lipschitz distribution on its valuations, by log-Lipschitz facts (see Appendix A.3). 制限 φ′ a の値の分布を考えると、我々はまだその値の α-log-Lipschitz 分布をlog-Lipschitz facts で操作する(Appendix A.3)。 0.78
Constants. We want to get explicit constants C1, C2, C3 and C4 as a function of k and η. 定数。 k と η の函数として、明示定数 C1, C2, C3, C4 を得る。 0.66
Note that η = (1 + α)−k is dependent on k. η = (1 + α)−k は k に依存することに注意。 0.83
Let us recall the recurrence system from the inductive step: 帰納的な段階から再発システムを思い出しましょう。 0.54
1 C (k) 1 = C (k−1) C (k) 2 = C (k−1) C (k) 1 C (k) 1 = C (k−1) C (k) 2 = C (k−1) C (k) 0.46
2 8 3 = C (k) 2 8 3 = c (複数形 cs) 0.48
4 = +C(k−1) 4 = +C(k−1) 0.40
3 ) 2 2−k(C(k−1) + C (k−1) 3 ) 2 2−k(C(k−1) + C(k−1) 0.42
3 2 η2 maxnC (k−1) maxnC (k−1) 3 2 η2 maxnC (k−1) maxnC (k−1) 0.41
2 η 2 , C (k−1) 2 η 2 , c (k−1) 0.43
3 , C (k−1) 3 , c (k−1) 0.43
3 o o . It is easy to see that C (k) we can now consider the following recurrence system, which dominates the previous one: 3 です。 C (k) では、次の再帰システムを考えることができ、これは以前のシステムを支配している。 0.49
for all k ∈ N. If we fix η = (1+α)−k at each level of the recurrence, すべての k ∈ N に対して η = (1+α)−k を繰り返しのレベルに固定する。 0.86
3 ≥ C (k) 2 3 ≥ C (k) 2 0.42
C (k) 1 = C (k−1) C (k) C (k) 1 = C (k−1) C (k) 0.48
1 8 3 = η2 C (k−1) 1 8 3 = η2 C (k−1) 0.41
3 2−2kC(k−1) 3 2−2kc(k−1) 0.36
3 2 = 2C (k−1) C (k) 3 C (k−1) C (k) 3 2 = 2C (k−1) C (k) 3C (k−1) C (k) 0.45
4 = 3 2 η . 4 = 3 2 η . 0.42
8 8 0.42
英語(論文から抽出)日本語訳スコア
We can now see that 私たちはそれを見ることができる。 0.48
C (k) c (複数形 cs) 0.58
C (k) c (複数形 cs) 0.58
η2(cid:19)k−1 2 = 2(cid:18) 8 η2(cid:19)k 3 =(cid:18) 8 η2(cid:19)k−1 η (cid:18) 8 η2(cid:19)k−1 2 = 2(cid:18) 8 η2(cid:19)k 3 =(cid:18) 8 η2(cid:19)k−1 η (cid:18) 8 0.38
4 = 2 C (k) 4 = 2 c (複数形 cs) 0.48
= 2(8(1 + α)2k)k−1 = 2(8(1 + α)2k)k−1 0.48
= (8(1 + α)2k)k = (8(1 + α)2k)k 0.46
= 2(1 + α)k(8(1 + α)2k)k−1 . = 2(1 + α)k(8(1 + α)2k)k−1。 0.47
Finally, we can get a lower bound on the value of C (k) 最後に、C (k) の値の低い境界を得ることができます。 0.82
1 as follows: C (k) 1 以下の通りです c (複数形 cs) 0.56
1 = k Yi=2 1 = k Yi=2 0.62
2−2iC(i−1) 2−2iC(i−1) 0.29
3 = 2 −2 Pk 3 = 2 -2Pk 0.39
i=2 i·(cid:16) 8 i=2i·(cid:16)8 0.31
η2 (cid:17)(i−1) η2 (cid:17)(i−1) 0.36
−2k2(cid:16) 8 -2k2(cid:16)8 0.28
η2 (cid:17)(k−1) η2 (cid:17)(k−1) 0.36
≥ 2 = 2−2k2(8(1+α)2k )k−1 ≥ 2 = 2−2k2(8(1+α)2k )k−1 0.37
. 4 An Adversarial Sample Complexity Lower Bound . 4 敵対的サンプル複雑性下限 0.55
In this section, we will show that any robust learning algorithm for monotone conjunctions under the uniform distribution must have an exponential sample-complexity dependence on an adversary’s budget ρ. 本節では,一様分布下の単調結合に対するロバスト学習アルゴリズムは,敵の予算 ρ に対して指数関数的サンプル複雑度依存性を持たなければならないことを示す。 0.79
This result extends to any superclass of monotone conjunctions, such as CNF formulas, decision lists and halfspaces. この結果は、CNF式、決定リスト、ハーフスペースなど、任意の単調結合のスーパークラスにまで拡張される。 0.49
It is a generalization of Theorem 13 in [17], which shows that no sample-efficient robust learning algorithm exists for monotone conjunctions against adversaries that can perturb ω(log(n)) bits of the input under the uniform distribution. これは[17]における定理13の一般化であり、一様分布の下で入力の ω(log(n)) ビットを摂動できる敵に対する単調結合に対するサンプル効率の良いロバスト学習アルゴリズムは存在しないことを示している。 0.82
The idea behind the proof is to show that, for a fixed constant κ < 2, and sufficiently large input dimension, a sample of size 2κρ from the uniform distribution won’t be able to distinguish between two disjoint conjunctions of length 2ρ. この証明の背後にある考え方は、固定定数 κ < 2 と十分大きな入力次元に対して、一様分布から大きさ 2κρ のサンプルは、長さ 2ρ の二つの相反する結合を区別できないことを示すことである。 0.88
However, the robust risk between these two conjunctions can be lower bounded by a constant. しかし、この2つの接続間の堅牢なリスクは定数によって低くすることができる。 0.62
Hence, there does not exist a robust learning algorithm with sample complexity 2κρ that works for the uniform distribution, and arbitrary input dimension and confidence and accuracy parameters. したがって、一様分布と任意の入力次元と信頼度と精度パラメータに対応するサンプル複雑性2κρを持つ頑健な学習アルゴリズムは存在しない。 0.89
Recall that the sample complexity of PAC learning conjunctions is Θ(n) in the non-adversarial setting. PAC学習接続のサンプルの複雑さは、非対逆的な設定において ^(n) である。 0.70
On the other hand, our adversarial lower bound in terms of the robust parameter is super linear in n as soon as the adversary can perturb more than log(√n)) bits of the input. 一方、ロバストパラメーターの項における我々の逆境下界は、逆境が入力のlog(\n)ビット以上を摂動できるとすぐに n において超線形となる。 0.62
Theorem 8. Fix a positive increasing robustness function ρ : N → N. For κ < 2 and sufficiently large input dimensions n, any ρ(n)-robust learning algorithm for MON-CONJ has a sample complexity lower bound of 2κρ(n) under the uniform distribution. 理論8。 κ < 2 と十分大きな入力次元 n に対して、MON-CONJ に対する任意の ρ(n)-robust 学習アルゴリズムは、一様分布の下で 2κρ(n) のサンプル複雑性の下界を持つ。
訳抜け防止モード: 理論8。 正増加ロバスト性関数 ρ : N → N を固定する。 十分に大きな入力次元 n と MON - CONJ に対するρ(n)-ロバスト学習アルゴリズムは、一様分布の下で 2κρ(n ) のサンプル複雑性の下界を持つ。
0.74
The proof of the theorem follows similar reasoning as Theorem 13 in [17], and is included in Appendix C. The main difference in the proof is its reliance on the following lemma, which shows that, for sufficiently large input dimensions, a sample of size 2κρ from the uniform distribution will look constant with probability 1/2 if labelled by two disjoint monotone conjunctions of length 2ρ. 証明の主な違いは次の補題に依存することであり、十分大きな入力次元に対して、一様分布から2κρの大きさのサンプルは、長さ2ρの2つの不連続な単調結合によってラベル付けされた場合、確率1/2で定数に見えることを示している。
訳抜け防止モード: 定理の証明は[17]における定理13と同様の推論に従う。 証明の主な違いは次の補題に依存することである。 これは、十分大きな入力次元に対して、一様分布から2κρの大きさのサンプルが確率 1/2 で一定に見えることを意味する。 長さ 2ρ の2つの不連結単調結合によりラベル付けされる。
0.79
As shown in Lemma 14, which can be found in Appendix C, these two conjunctions have a robust risk bounded below by a constant against each other. 補題 c で見られる lemma 14 に示されるように、これらの2つの結合は、互いに定数で囲まれる強固なリスクを持つ。 0.63
9 9 0.42
英語(論文から抽出)日本語訳スコア
Lemma 9. For any constant κ < 2, for any robustness parameter ρ ≤ n/4, for any disjoint monotone conjunctions c1, c2 of length 2ρ, there exists n0 such that for all n ≥ n0, a sample S of size 2κρ sampled i.i.d. from D will have that c1(x) = c2(x) = 0 for all x ∈ S with probability at least 1/2. 第9回。 任意の定数 κ < 2 に対して、任意のロバスト性パラメータ ρ ≤ n/4 に対して、長さ 2ρ の任意の単調結合 c1, c2 に対して、すべての n ≥ n0 に対して、d から標本化された 2κρ のサンプル s が c1(x) = c2(x) = 0 となるような n0 が存在する。 0.71
Proof. We begin by bounding the probability that c1 and c2 agree on an i.i.d. sample of size m. 証明。 まず、サイズ m の i.i.d. サンプル上で c1 と c2 が一致する確率を限定する。
訳抜け防止モード: 証明。 まずは 確率を制限し c1 と c2 はサイズ m の i.i.d サンプルに一致する。
0.68
We have . (3) (4) 我々は . (3) (4) 0.51
Pr S∼Dm (∀x ∈ S · c1(x) = c2(x) = 0) =(cid:18)1 − Pr 佐々木 (x ∈ S · c1(x) = c2(x) = 0) = (cid:18)1 − 0.36
1 22ρ(cid:19)2m 1 22ρ(cid:19)2m 0.39
In particular, if m ≤ then the RHS of Equation 3 is at least 1/2. 特に、もし m ≤ このとき、方程式3の RHS は少なくとも 1/2 である。 0.54
log(2) 2 log(22ρ/(22ρ − 1)) ログ(2) 2 log(22ρ/(22ρ − 1)) 0.62
, Now, let us consider the following limit, where ρ is a function of the input parameter n: , さて、次の極限を考える: ここで ρ は入力パラメータ n の関数である。
訳抜け防止モード: , さて、次の制限について考えてみましょう。 ρ は入力パラメータ n の関数である。
0.59
lim n→∞ 2κρ log(cid:18) 22ρ lim n→∞ 2κρ log(cid:18) 22ρ 0.36
22ρ − 1(cid:19) = − log(4) κ log(2) = − log(4) κ log(2) 22ρ − 1(cid:19) = − log(4) κ log(2) = − log(4) κ log(2) 0.47
lim n→∞ 2κρ 1 − 22ρ lim n→∞ lim n→∞ 2κρ 1 − 22ρ lim n→∞ 0.35
κ log(2) −2 log(2) κ log(2) −2 log(2) 0.46
2κρ 22ρ = lim n→∞ 2κρ 22ρ = lim n→∞ 0.34
2(κ−2)ρ where the first two equalities follow from l’Hˆopital’s rule. 2(κ−2)ρ 最初の2つの等式はl’h'opitalの法則に従う。 0.61
Thus if κ < 2 then 2κρ is o(cid:18)(cid:16)log (cid:16) 22ρ したがって、κ < 2 なら 2κρ は o(cid:18)(cid:16)log (cid:16) 22ρ である。 0.70
0 if κ < 2 1 if κ = 2 ∞ if κ > 2 0 if κ < 2 1 if κ = 2 ∞ if κ > 2 0.42
, =  22ρ−1(cid:17)(cid:17)−1(cid:19). , 以下は、22ρ−1(cid:17)(cid:17)−1(cid:19)である。 0.49
Remark 10. Note that for a given κ < 2, the lower bound 2κρ holds only for sufficiently large ρ(n). 背番号10。 与えられた κ < 2 に対して、下界 2κρ は十分大きな ρ(n) に対してのみ成立する。 0.67
By looking at Equation 3, and letting m = 2ρ, we get that ρ(n) ≥ 2 is a sufficient condition for it to hold. 方程式 3 を見て m = 2ρ とすると、ρ(n) ≥ 2 が成立するのに十分な条件となる。 0.76
If we want a lower bound for robust learning that is larger than that of standard learning (where the dependence is Θ(n)) for a log(n) adversary, setting m = 21.7ρ and requiring ρ(n) ≥ 6, for e g , would be sufficient. もし、log(n) の逆数に対する標準学習(依存が θ(n)) よりも大きいロバスト学習に対する下限を求めるならば、m = 21.7ρ とし、例えば ρ(n) ≥ 6 を必要とするような場合、十分である。 0.74
5 Conclusion We have shown that the class k-DL is efficiently robustly learnable against a logarithmicallybound ed adversary, thus making progress on the open problem of Gourdeau et al [17] of whether PAC-learnable classes are always robust in general against a logarithmically-boun ded adversary. 5 結論 我々は,k-DLクラスが対数有界敵に対して効率よく学習可能であることを示し,対数有界敵に対してPAC学習可能なクラスが常に常に強固であるかどうかというGourdeau et al[17]のオープン問題に進展することを示した。 0.64
The main technical tool was an isoperimetric result concerning CNF formulas. 主な技術ツールはCNF式に関する等尺的な結果であった。 0.68
Moreover, we have shown that, for monotone conjunctions and any superclass thereof, any ρ-robust learning algorithm must have a sample complexity that is exponential in the adversarial budget ρ. さらに、単調結合とその超クラスに対して、任意のρ-ロバスト学習アルゴリズムは、逆予算 ρ において指数関数的なサンプル複雑性を持つ必要があることを示した。 0.73
10 10 0.42
英語(論文から抽出)日本語訳スコア
Deriving sample complexity bounds for the robust learnability of halfspaces under the uniform distribution is perhaps the most natural next step towards resolving the above-mentioned open problem. 半空間の均一分布の下での堅牢な学習可能性に対するサンプル複雑性の導出は、上記の開問題を解くための最も自然な次のステップである。 0.71
Another direction of further research concerns improving the sample complexity bounds for k-DL in the present paper. さらなる研究の方向性として,k-DLの複雑さ境界の改善があげられる。 0.68
Here we have used a proper PAC-learning algorithm as a black box in our robust learning procedure (see Corollary 4). ここでは、堅牢な学習手順において、適切なPAC学習アルゴリズムをブラックボックスとして使用しています(図4参照)。 0.64
By controlling the accuracy parameter of the standard PAC-learning algorithm, we are able to get a robust learning algorithm. 標準的なPAC学習アルゴリズムの精度パラメータを制御することにより、堅牢な学習アルゴリズムを実現できる。 0.83
From this, we get polynomial sample complexity upper bounds for k-DL in terms of the robustness accuracy parameter ε, the distribution parameter α, and the input dimension n. これにより、ロバスト性精度パラメータε、分布パラメータα、入力次元nという観点からk-dlの多項式サンプル複雑性上限が得られる。 0.76
The resulting polynomial has degree O(8k(1 + α)2k2 ) in the dimension n. 得られる多項式は次元 n の次数 o(8k(1 + α)2k2 ) を持つ。 0.78
It is natural to ask whether these bounds can be improved in a significant way, e g , by adapting the learning procedure to directly take robustness into account, rather than using a PAC-learning algorithm as a black box. 例えば、パック学習アルゴリズムをブラックボックスとして使うのではなく、直接ロバスト性を考慮して学習手順を適用することで、これらの境界が大幅に改善できるかどうかを問うのは自然である。 0.67
Connected to this, we note that our lower bound focuses on establishing the exponential dependence of the number of samples on the robustness parameter. これに関連して、下限はロバスト性パラメータにサンプル数を指数関数的に依存させることに焦点を当てていることに注意する。
訳抜け防止モード: これとつながってる 我々の下限は、ロバスト性パラメータのサンプル数に対する指数関数的依存性を確立することに焦点を当てている。
0.69
The bound is derived from the case of monotone conjunctions (a special case of 1-DL) under the uniform distribution and so does not mention k, nor the distribution parameter α. 境界は一様分布の下で単調結合の場合(1-dlの特別な場合)に由来するので、k や分布パラメータ α は言及しない。 0.72
Likewise, it does not mention the desired accuracy ε. 同様に、所望の精度 ε については言及しない。 0.72
Deriving sample complexity lower bounds with a dependence on these parameters, potentially through other techniques, would help give a complete picture of the robust learnability of k-DL. サンプル複雑性をこれらのパラメータに依存する下限から導出することは、他の手法を通じて、k-dlの堅牢な学習可能性を完全に示すのに役立つだろう。 0.60
) in the term 1/ε and degree O(k8k(1 + α)2k2 ) 1/ε と次数 o(k8k(1 + α)2k2 0.91
Acknowledgments MK and PG received funding from the ERC under the European Union’s Horizon 2020 research and innovation programme (FUN2MODEL, grant agreement No. 834115). 承認 MKとPGは欧州連合のHorizon 2020研究イノベーションプログラム(FUN2MODEL, grant agreement No. 834115)の下でECCから資金提供を受けた。 0.60
References [1] Awasthi, P., Feldman, V., and Kanade, V. (2013). 参考文献 [1] Awasthi, P., Feldman, V., and Kanade, V. (2013)。 0.54
Learning using local membership queries. ローカルメンバーシップクエリによる学習。 0.79
In COLT, volume 30, pages 1–34. 院 全30巻、1-34頁。 0.43
[2] Bhagoji, A. N., Cullina, D., and Mittal, P. (2019). [2] Bhagoji, A. N., Cullina, D., Mittal, P. (2019)。 0.42
Lower bounds on adversarial robustness 対向ロバスト性に関する下界 0.71
from optimal transport. arXiv preprint arXiv:1909.12272. 最適な輸送手段から arXiv preprint arXiv:1909.12272 0.57
[3] Biggio, B., Corona, I., Maiorca, D., Nelson, B., ˇSrndi´c, N., Laskov, P., Giacinto, G., and Roli, F. (2013). 5] Biggio, B., Corona, I., Maiorca, D., Nelson, B., .Srndi ́c, N., Laskov, P., Giacinto, G., Roli, F. (2013).
訳抜け防止モード: [3]Biggio, B., Corona, I., Maiorca, D. ネルソン、B.、Srndi ́c、N.、ラスコフ、P.。 Giacinto, G., and Roli, F. (2013)。
0.88
Evasion attacks against machine learning at test time. テスト時の機械学習に対する回避攻撃。 0.72
In Joint European conference on machine learning and knowledge discovery in databases, pages 387–402. データベースにおける機械学習と知識発見に関する欧州合同会議 (european conference on machine learning and knowledge discovery in databases) では、387-402ページを扱っている。 0.44
Springer. [4] Biggio, B. and Roli, F. (2017). Springer 5] Biggio, B. and Roli, F. (2017)。 0.33
Wild patterns: Ten years after the rise of adversarial machine 野生のパターン:敵機械の台頭から10年後 0.73
learning. arXiv preprint arXiv:1712.03141. 学ぶこと。 arXiv preprint arXiv:1712.03141 0.51
[5] Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. (2019). 5]Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. (2019)。 0.77
Adversarial examples from In Proceedings of the 36th International Conference on Machine computational constraints. 第36回機械計算制約国際会議(In Proceedings of the 36th International Conference on Machine)の参加者。 0.50
Learning, volume 97 of Proceedings of Machine Learning Research, pages 831–840, Long Beach, California, USA. 機械学習研究議事録第97巻871-840頁、カリフォルニア州ロングビーチ。 0.51
PMLR. [6] Dalvi, N., Domingos, P., Sanghai, S., Verma, D., et al (2004). PMLR。 6] Dalvi, N., Domingos, P., Sanghai, S., Verma, D., et al (2004). 0.40
Adversarial classification. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 99–108. 敵の分類。 第10回知識発見・データマイニング国際会議(acm sigkdd international conference on knowledge discovery and data mining)の議事録99-108頁。
訳抜け防止モード: 敵の分類。 第10回ACM SIGKDD国際会議「知識発見とデータマイニング」の開催報告 99-108頁。
0.69
ACM. 11 acm。 11 0.53
英語(論文から抽出)日本語訳スコア
[7] Diochnos, D., Mahloujifar, S., and Mahmoody, M. (2018). [7]Diochnos, D., Mahloujifar, S., and Mahmoody, M. (2018)。 0.40
Adversarial risk and robustness: General definitions and implications for the uniform distribution. 敵対的リスクと堅牢性:一様分布に対する一般的な定義と意味。 0.73
In Advances in Neural Information Processing Systems. 神経情報処理システムの進歩です 0.58
[8] Diochnos, D. I., Mahloujifar, S., and Mahmoody, M. (2019). [8]Diochnos, D. I., Mahloujifar, S., and Mahmoody, M. (2019)。 0.42
Lower bounds for adversarially robust pac learning. 逆境における下限 堅実な太平洋学習です 0.59
arXiv preprint arXiv:1906.05815. arXiv preprint arXiv:1906.05815 0.36
[9] Diochnos, D. I., Mahloujifar, S., and Mahmoody, M. (2020). 9]Diochnos, D. I., Mahloujifar, S., and Mahmoody, M. (2020)。 0.39
Lower bounds for adversarially robust PAC learning under evasion and hybrid attacks. 回避とハイブリッド攻撃による対向的堅牢なPAC学習の限界 0.70
In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 717–722. 2020年の第19回ieee international conference on machine learning and applications (icmla) 717-722ページ。 0.80
[10] Dreossi, T., Ghosh, S., Sangiovanni-Vincente lli, A., and Seshia, S. A. (2019). [10]Dreossi, T., Ghosh, S., Sangiovanni-Vincente lli, A., and Seshia, S. A. (2019) 0.44
A formalization of robustness for deep neural networks. 形式化 ディープニューラルネットワークのロバスト性です 0.56
arXiv preprint arXiv:1903.10033. arXiv preprint arXiv:1903.10033 0.36
[11] Fawzi, A., Fawzi, H., and Fawzi, O. (2018a). [11]Fawzi, A.,Fawzi, H.,Fawzi, O. (2018a). 0.58
Adversarial vulnerability for any classifier. あらゆる分類器の逆の脆弱性。 0.59
arXiv preprint arXiv:1802.08686. arXiv arXiv:1802.08686 0.37
[12] Fawzi, A., Fawzi, O., and Frossard, P. (2018b). 12] Fawzi, A., Fawzi, O., Frossard, P. (2018b). 0.81
Analysis of classifiers? robustness to adversarial 分類器の分析? 敵意に対する堅牢性 0.70
perturbations. Machine Learning, 107(3):481–508. 混乱だ 機械学習、107(3):481–508。 0.64
[13] Fawzi, A., Moosavi-Dezfooli, S. 13]fawzi, a., moosavi-dezfooli, s。 0.68
-M. , and Frossard, P. (2016). -M。 and frossard, p. (2016) を参照。 0.60
Robustness of classifiers: from In Advances in Neural Information Processing Systems, pages 分類器のロバスト性:神経情報処理システム,ページにおける進歩から 0.81
adversarial to random noise. ランダムノイズに逆らう。 0.56
1632–1640. 1632–1640. 0.35
[14] Feige, U., Mansour, Y., and Schapire, R. (2015). [14]Feige, U., Mansour, Y. and Schapire, R. (2015)。 0.43
Learning and inference in the presence of 存在下での学習と推論 0.69
corrupted inputs. In Conference on Learning Theory, pages 637–657. 入力が破損した 637-657頁。 0.33
[15] Gilmer, J., Metz, L., Faghri, F., Schoenholz, S. S., Raghu, M., Wattenberg, M., and Goodfel- [15]Gilmer,J.,Metz,L.,Fa gri,F.,Schoenholz,S. S.,Raghu,M.,Wattenbe rg,M.,Goodfel
訳抜け防止モード: [15 ]ギルマー,J.,メッツ,L.,ファグリ, F., Schoenholz, S. S., Raghu, M., Wattenberg, M., Goodfel-
0.77
low, I. (2018). low, i. (2018)。 0.40
Adversarial spheres. arXiv preprint arXiv:1801.02774. 敵の球体。 arXiv preprint arXiv:1801.02774 0.30
[16] Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2019). 16] Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2019)。 0.76
On the hardness of robust classification. 頑健な分類の難しさについて 0.51
In Advances in Neural Information Processing Systems, pages 7444–7453. 神経情報処理システムの進歩』7444-7453頁。 0.68
[17] Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2021). He17] Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2021年) 0.78
On the hardness of robust classification. 硬さについて 頑丈な分類だ 0.62
Journal of Machine Learning Research, 22. Journal of Machine Learning Research, 22。 0.41
[18] Ilyas, A., Santurkar, S., Tsipras, D., Engstrom, L., Tran, B., and Madry, A. (2019). [18]Ilyas, A., Santurkar, S., Tsipras, D., Engstrom, L., Tran, B., Madry, A. (2019). 0.41
Adversarial examples are not bugs, they are features. 反対 例はバグではなく 特徴です 0.39
arXiv preprint arXiv:1905.02175. arXiv preprint arXiv:1905.02175 0.36
[19] Lowd, D. and Meek, C. (2005a). [19] Lowd, D. and Meek, C. (2005a). 0.49
Adversarial learning. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 641–647. 敵対的な学習。 第11回 ACM SIGKDD International Conference on Knowledge Discovery in data mining, page 641–647 0.59
ACM. [20] Lowd, D. and Meek, C. (2005b). acm。 [20] Lowd, D. and Meek, C. (2005b). 0.56
Good word attacks on statistical spam filters. 統計的スパムフィルターに対する良い言葉攻撃。 0.83
In CEAS, volume 2005. CEAS 2005年。 0.41
[21] Mahloujifar, S., Diochnos, D. I., and Mahmoody, M. (2019). 21] mahloujifar, s., diochnos, d. i., and mahmoody, m. (2019) 0.36
The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. 堅牢な学習における集中の呪い: 集中度からの侵入と毒殺。 0.65
AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence(英語) 0.80
[22] Mahloujifar, S. and Mahmoody, M. (2019). [22]mahloujifar, s. and mahmoody, m. (2019) 0.36
Can adversarially robust learning leveragecompu- 逆向きに頑健な学習レバレッジコンプ- 0.43
tational hardness? In Algorithmic Learning Theory, pages 581–609. タチオン硬さ? アルゴリズム学習理論』 581-609頁。 0.61
PMLR. 12 PMLR。 12 0.41
英語(論文から抽出)日本語訳スコア
[23] Montasser, O., Hanneke, S., and Srebro, N. (2019). [23]Montasser, O., Hanneke, S., and Srebro, N. (2019)。 0.84
Vc classes are adversarially robustly Vcクラスは逆向きに強固である 0.58
learnable, but only improperly. 学べるが 不適切なだけだ 0.55
In Conference on Learning Theory, pages 2512–2530. 学習理論に関する会議では2512-2530頁。 0.76
PMLR. [24] Rivest, R. L. (1987). PMLR。 [24] Rivest, R. L. (1987)。 0.43
Learning decision lists. 意思決定リストの学習。 0.67
Machine learning, 2(3):229–246. 機械学習 2(3):229–246。 0.87
[25] Shafahi, A., Huang, W. R., Studer, C., Feizi, S., and Goldstein, T. (2018). [25]Shafahi, A., Huang, W. R., Studer, C., Feizi, S., Goldstein, T. (2018)。 0.84
Are adversarial examples inevitable? 敵対的です 避けられない例? 0.59
arXiv preprint arXiv:1809.02104. arXiv preprint arXiv:1809.02104 0.36
[26] Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. (2013). [26]Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., Fergus, R. (2013).
訳抜け防止モード: [26 ]Szegedy, C., Zaremba, W., Sutskever. I., Bruna, J., Erhan, D., Goodfellow, I. とFergus, R. (2013)。
0.78
Intriguing properties of neural networks. ニューラルネットワークの興味深い性質 0.67
In International Conference on Learning Representations. 学習表現に関する国際会議に参加。 0.79
[27] Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. (2019). [27]Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., Madry, A. (2019)。 0.77
Robustness may be at odds with accuracy. ロバスト性は 正確さと相反する。 0.46
In International Conference on Learning Representations. 学習表現に関する国際会議に参加。 0.79
[28] Valiant, L. G. (1984). [28] Valiant, L. G. (1984)。 0.47
A theory of the learnable. In Proceedings of the sixteenth annual ACM 学習可能な理論。 第16回年次acmの手続において 0.63
symposium on Theory of computing, pages 436–445. 計算理論シンポジウム, 436-445頁。 0.65
ACM. A Preliminaries A.1 acm。 予科 A.1 0.40
The PAC framework PACフレームワーク 0.58
We study the problem of robust classification in the realizable setting and where the input space is the Boolean cube Xn = {0, 1}n. 実現可能な設定におけるロバスト分類の問題と入力空間がブール立方体 Xn = {0, 1}n のどこにあるかを検討する。 0.77
For clarity, we first recall the definition of the PAC learning framework [28]. 明確にするために、まずPAC学習フレームワークの定義を思い出します [28]。 0.66
Definition 11 (PAC Learning). 定義11(PAC Learning)。 0.38
Let Cn be a concept class over Xn and let C =Sn∈N Cn. cn を xn 上の概念クラスとし、c =snhtmln cn とする。 0.74
We say that C is PAC learnable using hypothesis class H and sample complexity function p(·,·,·,·) if there exists an algorithm A that satisfies the following: for all n ∈ N, for every c ∈ Cn, for every D over Xn, for every 0 < ǫ < 1/2 and 0 < δ < 1/2, if whenever A is given access to m ≥ p(n, 1/ǫ, 1/δ, size(c)) examples drawn i.i.d. from D and labeled with c, A outputs a polynomially evaluatable h ∈ H such that with probability at least 1 − δ, C が仮説クラス H とサンプル複雑性関数 p(·,·,·,·) を用いて学習可能であるとは、すべての n ∈ N に対して、すべての c ∈ Cn に対して、すべての 0 < > < 1/2 と 0 < δ < 1/2 に対して、A が m ≥ p(n, 1/>, 1/δ, size(c)) にアクセスできるとき、すなわち D から d から C にラベル付けされた場合、A は少なくとも 1 − δ の確率を持つ多項式的に評価可能な h ∈ H を出力する。 0.79
Pr x∼D (c(x) 6= h(x)) ≤ ǫ . Pr x-D (c(x) 6= h(x)) ≤ s である。 0.59
We say that C is statistically efficiently PAC learnable if p is polynomial in n, 1/ǫ, 1/δ and size(c), and computationally efficiently PAC learnable if A runs in polynomial time in n, 1/ǫ, 1/δ and size(c). p が n の多項式であれば c は統計学的にpac が学習可能であり、n の多項式時間で a が n のとき 1 と 1/δ と size(c) で計算的にpacが学習可能である。 0.68
PAC learning is distribution-free, in the sense that no assumptions are made about the distribution from which the data comes from. PAC学習は、データが生み出す分布について仮定されることはないという意味で、分布自由である。 0.80
The setting where C = H is called proper learning, and improper learning otherwise. C = H を適切な学習と呼び、それ以外は不適切な学習である。 0.75
13 13 0.85
英語(論文から抽出)日本語訳スコア
A.2 Monotone Conjunctions and k-CNF Formulas A conjunction c over {0, 1}n can be represented a set of literals l1, . . . , lk, where, for x ∈ Xn, c(x) = Vk i=1 li. A.2 単調接続と k-CNF 式 {0, 1}n 上の連結 c はリテラル l1, . . . . . , lk の集合で表すことができ、ここで x ∈ Xn に対して c(x) = Vk i=1 li となる。 0.55
For example, c(x) = x1 ∧ ¯x2 ∧ x5 is a conjunction. 例えば、c(x) = x1.x2.x5 は結合である。 0.73
Monotone conjunctions are the subclass of conjunctions where negations are not allowed, i.e., all literals are of the form li = xj for some j ∈ [n]. モノトン接続は、否定が許されない接続のサブクラスであり、すなわち、すべてのリテラルは、ある j ∈ [n] に対して li = xj の形である。 0.68
A formula ϕ in the conjunctive normal form (CNF) is a conjunction of clauses, where each clause is itself a disjunction of literals. 連結正規形 (CNF) の式 φ は節の結合であり、各節はそれ自体がリテラルの解である。
訳抜け防止モード: 連結正規形式 (CNF ) における公式 φ は節の連結である。 ここでは、各節はそれ自体がリテラルの区切りである。
0.68
A k-CNF formula is a CNF formula where each clause contains at most k literals. k-CNF式は、各節が少なくともkリテラルを含むCNF式である。 0.75
For example, ϕ = (x1 ∨ x2) ∧ ( ¯x3 ∨ x4) ∧ ¯x5 is a 2-CNF. 例えば、φ = (x1 ) x2) {\displaystyle \mathrm {x3}}x4} は 2-CNF である。 0.68
A.3 Log-Lipschitz Distributions A.3 ログリプシッツ分布 0.59
Log-Lipschitz distributions have the following useful properties, which are stated in [1] and whose proofs can be found in [16]: Lemma 12. log-lipschitz 分布は以下の有用な性質を持つ: [1] に記載され、証明は [16]: lemma 12 に示される。 0.73
Let D be an α-log-Lipschitz distribution over {0, 1}n. D を {0, 1}n 上の α-log-Lipschitz 分布とする。 0.80
Then the following hold: i. すると次のようになる。 0.61
For b ∈ {0, 1}, ii. b ∈ {0, 1}, ii に対して。 0.84
For any S ⊆ [n], the marginal distribution D ¯S is α-log-Lipschitz, where D ¯S(y) =Py′∈{0,1}S D(yy′). 任意の S > [n] に対して、境界分布 D > S は α-log-Lipschitz であり、D > S(y) = Py′∂{0,1}S D(yy′) である。 0.55
iii. For any S ⊆ [n] and for any property πS that only depends on variables xS, the marginal with respect to ¯S of the conditional distribution (D|πS) ¯S is α-log-Lipschitz. 第3回。 任意の s に対して [n] および変数 xs にのみ依存する任意の性質 πs に対して、条件分布 (d|πs) の s に対する限界は α-log-lipschitz である。 0.54
(xi = b) ≤ α 1+α . (xi = b) ≤ α 1+α 。 0.45
1+α ≤ Pr x∼D 1+α ≤ Pr x‐D 0.29
1 iv. For any S ⊆ [n] and bS ∈ {0, 1}S , we have that (cid:16) 1 1 iv 任意の S > [n] および bS ∈ {0, 1}S に対して、その (cid:16) 1 を持つ。 0.51
1+α(cid:17)|S| 1+α(cid:17)|S| 0.29
≤ Pr x∼D (xi = b) ≤(cid:16) α ≤Pr x‐D (xi = b) ≤(cid:16) α 0.35
1+α(cid:17)|S| 1+α(cid:17)|S| 0.29
. B Proof of Corollary 4 . B Proof of Corollary 4 (英語) 0.54
Proof of Corollary 4. Let A be the (proper) PAC-learning algorithm for k-DL as in [24], with sample complexity poly(·). 第4章の証明。 A を [24] の k-DL に対する(適切な) PAC 学習アルゴリズムとし、サンプル複雑性ポリ(·) とする。 0.72
Fix the input dimension n, target concept c and distribution D ∈ Dn, and let ρ = log n. 入力次元 n と対象概念 c と分布 D ∈ Dn を固定し、ρ = log n とする。 0.78
Fix the accuracy parameter 0 < ε < 1/2 and confidence parameter 0 < δ < 1/2 and let η = 1/(1 + α)k. 精度パラメータ 0 < ε < 1/2 と信頼パラメータ 0 < δ < 1/2 を固定し、η = 1/(1 + α)k とする。 0.89
Set ε0 = C1(cid:18) 16ε セット ε0 = C1(cid:18) 16ε 0.56
e4n2k+2(cid:19)C2 e4n2k+2(cid:19)C2 0.24
min((cid:18) 16ε min((cid:18) 16ε 0.41
e4n2k+2(cid:19)C3 e4n2k+2(cid:19)C3 0.24
, n−C4) , where the constants are the ones derived in Theorem 3. ,n−C4)。 ここで定数は Theorem 3 から派生したものである。 0.64
Let m = ⌈poly(n, 1/δ, 1/ε0)⌉, and note that m is polynomial in n, 1/δ and 1/ε. m = shpoly(n, 1/δ, 1/ε0) とし、m が n, 1/δ, 1/ε の多項式であることに注意する。 0.72
Let S ∼ Dm and h = A(S). S を Dm とし、h = A(S) とする。 0.78
Let the target and hypothesis be defined as the following decision s)), where the clauses Ki are conby 目標と仮説を次の決定として定義する(s))) 節 ki がコンビーである場合 0.72
lists: c = ((K1, v1), . . . , (Kr, vr)) and h = ((K ′ junctions of k literals. リスト: c = ((k1, v1), . . , (kr, vr), h = ((k ′ junctions of k literals)。 0.75
Given i ∈ {1, . . . , r} and j ∈ {1, . . . , s}, define a k-CNF formula ϕ(c,h) i ∈ {1, . . . , r} と j ∈ {1, . . , s} が与えられたとき、k-CNF式 φ(c,h) が定義される。 0.90
1), . . . , (K ′ 1), . . . , (K ′ 0.39
1, v′ s, v′ 1,v' s, v′ 0.45
i,j writing ϕ(c,h) i,j = ¬K1 ∧ ··· ∧ ¬Ki−1 ∧ Ki ∧ ¬K ′ i.j. 著作 φ(c,h) i,j = φ(c,h) i,j = ^K1 ^ ····· ^Ki−1 ^Ki ^K ′ 0.44
1 ∧ ··· ∧ ¬K ′ 1 ∧ ··· ∧ ¬K ′ 0.41
j−1 ∧ K ′ j . j − K ′ j である。 0.64
Notice that the formula ϕ(c,h) i in c and vertex j in h. 式 φ(c,h) i in c と vertex j in h に注意。 0.73
i,j represents the set of inputs x ∈ X that respectively activate vertex i.j. それぞれ頂点を活性化する入力 x ∈ X の集合を表す 0.62
14 14 0.42
英語(論文から抽出)日本語訳スコア
Since Pr x∼D (h(x) 6= c(x)) < ε0 with probability at least 1 − δ, any ϕ(c,h) プリーツx'd以来 (h(x) 6= c(x)) < ε0 の確率は少なくとも 1 − δ で、任意の φ(c,h) 0.70
i,j ) < ε0. i.j. ) < ε0. 0.44
But by Theorem 3, S しかし、Theorem 3, Sによって 0.80
Hence the probability that a ρ-bounded adversary can make ϕ(c,d) したがって、ρ-有界な敵がφ(c,d)を作る確率は 0.80
sification must have S0(ϕ(c,h) probability at least 1 − δ. S0(φ(c,h) の確率は少なくとも 1 − δ でなければならない。 0.83
Taking a union bound over all possible choices of i and j (there are Pk clauses in k-decision lists, which gives us a crude estimate of k2(cid:0) en i と j の可能なすべての選択肢に有界な結合をとる(k-決定リストに Pk 節があるので k2(cid:0) en の粗推定が得られる) 0.73
j) we conclude that Rlog(n)(h, c) < ε. j) Rlog(n)(h)(h, c) < ε である。 0.78
log(n)(ϕ(c,h) log(n)(φ(c,h)) 0.45
i,j i,j i=1(cid:0)n k (cid:1)2k ≤ e4n2k+2 i.j. i.j. i=1(cid:0)n k (cid:1)2k ≤ e4n2k+2 0.35
16 i,j ) < 16ε 16 i,j ) <16ε 0.69
that leads to a misclase4n2k+2 for all ϕ(c,h) これにより、すべての φ(c,h) に対する misclase4n2k+2 が得られる。 0.55
i,j with true is at most 私とjは もっとも 真実は 0.52
16ε e4n2k+2 . 16ε e4n2k+2。 0.28
k(cid:1) ≤ k(cid:0) en k(cid:1) ≤ k(cid:0) en 0.43
k (cid:1)k possible k (cid:1)k 可能 0.88
choices of i and C Proof of Theorem 8 i と i の選択 c 定理の証明 8 0.75
The proof of Theorem 8 relies on the following lemmas: Lemma 13 (Lemma 6 in [17]). 定理8の証明は次の補題に依存している: lemma 13 (lemma 6 in [17])。 0.67
Let c1, c2 ∈ {0, 1}X and fix a distribution on X . c1, c2 ∈ {0, 1}X とし、X 上の分布を固定する。 0.78
Then for all h : {0, 1}n → {0, 1} すべての h : {0, 1}n → {0, 1} に対して 0.85
Rρ(c1, c2) ≤ Rρ(h, c1) + Rρ(h, c2) . rρ(c1, c2) ≤ rρ(h, c1) + rρ(h, c2) である。 0.76
We then recall the following lemma from [17], whose proof here makes the dependence on the 次に、[17]から次の補題を思い出します。 0.30
adversarial budget ρ explicit. Lemma 14. 敵の予算 ρ 明示 背番号14。 0.47
Under the uniform distribution, for any n ∈ N, disjoint c1, c2 ∈ MON-CONJ of even length 3 ≤ l ≤ n/2 on {0, 1}n and robustness parameter ρ = l/2, we have that Rρ(c1, c2) is bounded below by a constant that can be made arbitrarily close to 1 均一分布の下では、任意の n ∈ N に対して、{0, 1}n 上の任意の長さ 3 ≤ l ≤ n/2 の可逆 c1, c2 ∈ MON-CONJ とロバストネスパラメータ ρ = l/2 に対して、Rρ(c1, c2) は 1 に任意に近づく定数で下界している。 0.84
2 as l (and thus ρ) increases. 2 となり, l(ρ) が増加する。 0.79
Proof. For a hypothesis c ∈ MON-CONJ, let Ic be the set of variables in c. 証明。 仮説 c ∈ MON-CONJ に対して、Ic を c 内の変数の集合とする。 0.70
Let c1, c2 ∈ C be as in the theorem statement. c1, c2 ∈ c を定理ステートメントのようにする。 0.85
Then the robust risk Rρ(c1, c2) is bounded below by その後、ロバストリスク Rρ(c1, c2) が下界する。 0.65
Pr x∼D (c1(x) = 0 ∧ x has at least ρ 1’s in Ic2) ≥ (1 − 2−2ρ)/2 . Pr x-D (c1(x) = 0 かつ x は少なくとも ρ 1 の ic2 ≥ (1 − 2−2ρ)/2 を持つ。 0.61
Proof of Theorem 8. Fix any algorithm A for learning MON-CONJ. 定理8の証明。 MON-CONJを学習するためのアルゴリズムAを修正する。 0.62
We will show that the expected robust risk between a randomly chosen target function and any hypothesis returned by A is bounded below by a constant. ランダムに選択された対象関数と、A によって返される任意の仮説の間の予測されたロバストリスクが定数で下界していることを示す。 0.60
Let δ = 1/2, and fix a positive increasing adversarial-budget function ρ(n) ≤ n/4 (n is not yet fixed). δ = 1/2 とし、正の増大する逆予算関数 ρ(n) ≤ n/4 を固定する(n はまだ固定されていない)。 0.68
Let m(n) = 2κρ(n) for an arbitrary κ < 0. 任意の κ < 0 に対して m(n) = 2κρ(n) とする。 0.84
Let n0 be as in Lemma 9, where m(n) is the fixed sample complexity function. n0 を Lemma 9 のようにすると、m(n) は固定標本複雑性関数である。 0.78
Then Equation (4) in the proof of Lemma 9 holds for all n ≥ n0. このとき、Lemma 9 の証明における方程式 (4) はすべての n ≥ n0 に対して成り立つ。
訳抜け防止モード: 式(4) Lemma 9 の証明では、すべての n ≥ n0 に対して成り立つ。
0.69
Now, let D be the uniform distribution on {0, 1}n for n ≥ max(n0, 3), and choose c1, c2 as in Lemma 14. さて、D を n ≥ max(n0, 3) の {0, 1}n 上の一様分布とし、Lemma 14 のように c1, c2 を選択する。 0.87
Note that Rρ(c1, c2) > 5 12 by the choice of n. Rρ(c1, c2) > 5 12 は n の選択によることに注意。 0.84
Pick the target function c uniformly at random between c1 and c2, and label S ∼ Dm(n) with c. 対象関数 c を c1 と c2 の間のランダムに選び、c とのラベル S は Dm(n) である。 0.79
By Lemma 9, c1 and c2 agree with the labeling of S (which implies that all the points have label 0) with probability at least 1 2 over the choice of S. Lemma 9 では、c1 と c2 は S の選択に関して少なくとも 1 2 の確率を持つ S のラベル付け(すべての点がラベル 0 を持つことを意味する)に一致する。 0.79
Define the following three events for S ∼ Dm: dm の次の3つのイベントを定義する。 0.75
E : c1|S = c2|S , Ec1 : c = c1 , Ec2 : c = c2 . E : c1|S = c2|S , Ec1 : c = c1 , Ec2 : c = c2 である。 0.70
15 15 0.43
英語(論文から抽出)日本語訳スコア
(Pr c,S (Ec1) E (Pr c,S) (Ec1)E 0.48
S [Rρ(A(S), c) | E ∩ Ec1] + Pr S [Rρ(A(S, c) | E > Ec1] + Pr 0.42
c,S (Ec2) E c,S (Ec2)E 0.44
S [Rρ(A(S), c) | E ∩ Ec2]) S [Rρ(A(S, c) | E > Ec2]) 0.41
> [Rρ(A(S), c)] ≥ Pr c,S 1 2 1 4 1 4 5 48 > [Rρ(A(S,c)] ≥ Pr c,S 1 2 1 4 4 4 5 48 0.41
≥ = = E S E S ≥ = = E S E S 0.42
Then, by Lemmas 9 and 13, そして、Lemmas 9 と 13 によって。 0.74
E c,S (E) E e c,s (E)E 0.37
c,S [Rρ(A(S), c) | E] c,S [Rρ(A(S, c) | E] 0.42
[Rρ(A(S), c1) + Rρ(A(S), c2) | E] [Rρ(c2, c1)] [Rρ(A(S), c1) + Rρ(A(S, c2) | E] [Rρ(c2, c1)] 0.48
. 16 . 16 0.42
                                 ページの最初に戻る

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