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.
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.
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.
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.
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.
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.
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.
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.
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,
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.
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.
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
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.
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 ϕ.
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.
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].
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.
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.
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).
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.
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].
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.
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.
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.
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.
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.
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
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.
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.
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.
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(α).
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.
Note that features are allowed a small dependence between each other and, by construction, log-Lipschitz distributions are supported on the whole input space.
Notable examples of log-Lipschitz distributions are the uniform distribution (with parameter α = 1) and the class of product distributions with bounded means.
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.
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.
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 ε.
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
(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
(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 ϕ.
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 |= ϕ′
(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
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).
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,
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 ρ.
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.
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ρ.
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.
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ρ.
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.
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.
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 ρ.
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.
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.
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.
Connected to this, we note that our lower bound focuses on establishing the exponential dependence of the number of samples on the robustness parameter.
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 α.
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.
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-
[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.
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.
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.
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 .
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 である。