机器学习基石与趋势1.3：属性测试的理论视角

Machine

Learning

需积分: 10 50 浏览量更新于2024-07-21 收藏 564KB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

《机器学习基础与趋势》第1卷第3期（2008年）探讨了在机器学习领域中的一个重要概念——属性测试。属性测试是一种任务，目标在于确定一个对象（如函数或图）是否具有预定义的属性（如函数是否线性或图是否二分图），或者它与任何此类对象存在显著差异。这个任务的关键是通过只查询对象的一小部分来完成，允许算法存在一定的错误概率。属性测试可以被视为学习任务的一种放松形式，即不是精确地获取对象的完整表示，而是寻找近似特征或特性。这种视角下的属性测试算法在实际应用中扮演着筛选器的角色，它们帮助高效地选择学习过程中应采用的假设类别。从学习理论的角度出发，本篇综述着重介绍了属性测试的研究成果，特别是在指导学习算法选择方面的应用。在机器学习过程中，属性测试算法的作用主要体现在以下几个方面： 1. **效率优化**：由于属性测试关注的是局部信息，而不是全局结构，因此设计出的测试算法能够在处理大规模数据时，有效地降低计算复杂度，提高算法的运行速度。 2. **假设选择**：属性测试可以帮助学习算法快速确定输入数据集可能属于的特定类别的可能性，从而避免对所有可能的模型进行冗余训练，节省资源。 3. **噪声和不确定性处理**：在实际场景中，数据往往存在噪声或不确定性。属性测试能够容忍一定程度的错误，这对于在不完美数据上进行学习至关重要。 4. **理论基础**：属性测试的研究还推动了机器学习理论的发展，为理解数据和模型之间的复杂交互提供了新的分析框架。 5. **应用广泛**：属性测试被应用于各种领域，如社交网络分析、数据库查询优化、计算机图形学、生物学数据分析等，帮助解决实际问题中的快速决策问题。属性测试作为一种强大的工具，不仅扩展了我们理解和处理复杂数据的能力，还在机器学习的实践和理论研究中占据着重要地位。通过将属性测试作为预学习阶段，我们可以设计出更高效、更具针对性的学习算法，适应不断发展的信息技术需求。

资源详情

资源推荐

322 Algebraic Properties

Let L denote the class of linear functions over {0,1}

. By Fact 3.1,

Algorithm 3.1 accepts every function f ∈L with probability 1. We

turn to proving that if dist(f,L) > then the algorithm rejects with

probability at least 2/3. Let 

(f) denote the distance of f to being

linear. Namely, 

(f)

def

= dist(f,L). We would like to prove that for

every given >0, if 

(f) >then the probability that the test rejects

is at least 2/3. This will follow from showing that if the constraint

f(x)+f(y)=f (x + y) is violated for relatively few pairs (x, y), then

f is close to some linear function. In other words (using the terminol-

ogy of [42, 128]), the characterization provided by Fact 3.1 is robust.

To this end we deﬁne:

η(f)

def

=Pr

x,y

[f(x)+f(y) = f(x + y)] , (3.1)

where in Equation (3.1) and elsewhere in this subsection, the probabi-

lity is taken over a uniform choice of points in {0, 1}

. That is, η(f)is

the probability that a single iteration of the algorithm “ﬁnds evidence”

that f is not a linear function. We shall show that η(f) ≥ 

(f)/c for

some constant c ≥ 1 (this can actually be shown for c = 1 but the proof

uses Discrete Fourier analysis [32] while the proof we show builds on

ﬁrst principles). It directly follows that if 

(f) >and the number of

iterations is at least 2c/, then the probability that the test rejects is

at least

1 − (1 − η(f))

2c/

> 1 − e

−2cη(f)/

≥ 1 − e

−2

> 2/3 , (3.2)

thus establishing Theorem 3.1.

Somewhat unintuitively, showing that η(f) ≥ 

(f)/c is easier if



(f) is not too large. Speciﬁcally, it is not hard to prove the following

claim.

Claim 3.2. For every function f, η(f) ≥ 3

(f)(1 − 2

(f)). In par-

ticular, if 

(f) ≤

then η(f) ≥

(f) (and more generally, if η(f)=

− γ for γ>0, then η(f) ≥ 6γ

(f), which gives a weak bound as

η(f) approaches 1/2).

It remains to prove that even when 

(f) is not bounded away (from

above) from 1/2 then still η(f) ≥ 

(f)/c for a constant c. To this

end we deﬁne the following majority function: for each ﬁxed choice of

3.1 Linearity 325

But in such a case,

(a)+g

(b)=f(b + a + y) − f(y)=g

(a + b) , (3.6)

and we are done. To see why there exists such a point y, consider

selecting y uniformly at random. For each of the three equalities, by

Claim 3.5, the probability that the equality does not hold is at most

2η(f). By the union bound, the probability (over a uniform selection

of y) that any one of the three does not hold is at most 6η(f). Since

η(f) < 1/6, this is bounded away from 1, and so the probability that

there exists a point y for which all three equalities hold simultaneously

is greater than 0, implying that there exists at least one such pair.

3.1.1 Self-Correction

One of the nice features of the analysis of the linearity tester (which

we shall use in two diﬀerent contexts, in Subsection 4.1.1 and in Sec-

tion 5.1) is that it implies that f can be self-corrected (assuming it is

suﬃciently close to being linear). That is, for any x of our choice, if we

want to know the value, on x, of the closest linear function (or, in the

coding theory view, we want to know the correct bit in the position

corresponding to x in the closest code-word), then we do the following.

We select, uniformly at random, y

,...,y

and take the majority vote

of V

(x),...,V

(x) (where the choice of t determines the probability

that the majority is correct).

3.1.2 On the Relation Between η(f) and 

(f)

By combining Claim 3.2 with Lemmas 3.3 and 3.4 we get that η(f) ≥

max{3

(f)(1 − 2

(f)),



(f)}. The analysis of [42] actually showed

that the constant

can be replaced with 2/9.

An interesting ques-

tion is what is the true behavior of η(f) as a function of 

(f)? Bel-

lare et al. [32] studied this question and showed several lower bounds,

some of which are tight. One of the interesting phenomenon they

observe is that the lower bound 3

(f)(1 − 2

(f)) is tight as long as



(f) ≤ 5/16, implying that there is a nonmonotonic behavior (since

We note that this holds for every f : G → H, where G and H are any two groups, and not

only for Boolean functions over the Boolean hypercube.

326 Algebraic Properties

3x(1 − 2x) increases until x =1/4 but then decreases between x =1/4

and x =5/16). Recent progress was made on understanding the rela-

tion between η(f) and 

(f) in [102].

3.2 Low-Degree Polynomials

Let F be a ﬁnite ﬁeld, and consider ﬁrst the univariate case, that is,

testing whether a function f : F → F is of the form f (x)=



i=0

for a given degree bound d (where the coeﬃcients C

belong to F ). In

this case, the testing algorithm [128] works by simply trying to inter-

polate the function f on Θ(1/) collections of d + 2 uniformly selected

points, and checking whether the resulting functions are all polynomial

of degree at most d. Thus the algorithm essentially works by trying to

learn the function f.

We now turn to multivariate polynomials.

Deﬁnition 3.2 (Multivariate Polynomials). Let F be a ﬁnite

ﬁeld. A function f : F

→ F is a (multivariate) polynomial of degree

(at most) d, if there exist coeﬃcients C

in F for every α ∈{0,...,d}

satisfying



i=1

≤ d, such that f (x)=



α∈{0,...,d}



i=1

Let POLY

n,d

denote the class of all functions f : F

→ F that are

polynomials of total degree at most d (where the degree in each variable

is at most |F |−1).

Low-degree testing has been studied extensively in the context of PCP

systems [22, 23, 24, 66, 77, 78, 128]. The aforementioned results all

apply to testing polynomials over ﬁelds that are larger than the degree-

bound, d (where in some cases the bound is on the total degree, and in

some case it is on the degree in each variable). In particular, if |F |≥

d + 2, then the dependence on d is known to be polynomial [77, 128].

In fact, a slightly more eﬃcient version of the algorithm would select d + 1 arbitrary

points, ﬁnd (by interpolating), the unique polynomial g

of degree d that agrees with f

on these points, and then check that g

agrees with f on an additional sample of Θ(1/)

uniformly selected points.

To be precise, the requirement that |F |≥d + 2 is suﬃcient for prime ﬁelds, and otherwise

needs to be slightly modiﬁed.

剩余95页未读，继续阅读

听一季雨声

粉丝: 0
资源: 3

机器学习基石与趋势1.3：属性测试的理论视角

通信与信息论基础 Foundations and Trends in Communications and Information Theory

Foundations_and_Trends_in_Machine_Learning

foundations and trends in communication theory

推荐几篇增量学习领域比较优秀的文献

Can you tell me some high-quality forums or blogs about artificial intelligence, and attach specific websites or access methods

where can I find new on machine learning

Development Editor opencv

Can you develop a learning path for me to master AI

Aurora et al.（2020）提出了一种基于机器学习的学生请假管理系统设计。该系统采用机器学习算法对学生请假信息进行分析和预测，帮助学校决策者制定更好的请假政策。该系统提高了请假管理的智能化和决策性

计算机英语期末试题,计算机英语期末考试试题

write an 1000 words essay about planing for my future development in university study and career planing in finance career

Towards Data Science

deep multimodal learning a survey on recent advances and trends

pattern history table

Write an essay commenting on the saying “Learning is a daily experience and a lifetime mission.”

请给我一篇关于地名消歧的最新外文综述文献

how to understand AI

Work in groups and discuss what other preparations you can make for writing the results and discussion section of your research paper

M2M (Machine-to-Machine)相关文献

When you have unstructured problems, what approach do you use for decision-making?

最新资源