Understanding Machine Learning: From Theory to Algorithms

25.1 Feature Selection 361 Then, we updateIt=It− 1 ∪{jt}. We now describe a more efficient implementation of the forward greedy ...

362 Feature Selection and Generation Orthogonal Matching Pursuit (OMP) input: data matrixX∈Rm,d, labels vectory∈Rm, budget of fe ...

25.1 Feature Selection 363 selection procedure with respect to the function R(w) = log   ∑m i=1 exp  −yi ∑d j=1 wjhj(xi)   ...

364 Feature Selection and Generation Equation (25.4) and Equation (25.5) lead to the same solution, the two problems are in some ...

25.2 Feature Manipulation and Normalization 365 Adding` 1 regularization to a linear regression problem with the squared loss yi ...

366 Feature Selection and Generation we will obtain thatx 1 =y+0 1 .. 55 αandx 2 =y. Then, forλ≤ 10 −^3 the solution of ridge re ...

25.2 Feature Manipulation and Normalization 367 should rely on our prior assumptions on the problem. In the aforementioned ex- a ...

368 Feature Selection and Generation Logarithmic Transformation: The transformation isfi←log(b+fi), wherebis a user-specified pa ...

25.3 Feature Learning 369 and given a document, (p 1 ,...,pd), where eachpiis a word in the document, we represent the document ...

370 Feature Selection and Generation in{ 0 , 1 }kthat indicates the closest centroid tox, whileφtakes as input an indicator vect ...

25.5 Bibliographic Remarks 371 25.5 Bibliographic Remarks Guyon & Elisseeff (2003) surveyed several feature selection proced ...

372 Feature Selection and Generation LetDbe the distribution over [m] defined by Di= exp(−yifw(xi)) Z , whereZis a normalization ...

Part IV Advanced Theory ...

...

26 Rademacher Complexities In Chapter 4 we have shown that uniform convergence is a sufficient condition for learnability. In th ...

376 Rademacher Complexities This can be written more compactly by definingσ= (σ 1 ,...,σm)∈ {± 1 }mto be a vector such thatS 1 = ...

26.1 The Rademacher Complexity 377 Next, we note that for eachj,zjandz′jare i.i.d. variables. Therefore, we can replace them wit ...

378 Rademacher Complexities Furthermore, ifh?= argminhLD(h)then for eachδ∈(0,1)with probability of at least 1 −δover the choice ...

26.1 The Rademacher Complexity 379 Proof First note that the random variable RepD(F,S) = suph∈H(LD(h)−LS(h)) satisfies the bound ...

380 Rademacher Complexities lemma26.7 LetA be a subset ofRm and letA′ ={ ∑N j=1αja (j) :N ∈ N,∀j,a(j)∈A,αj≥ 0 ,‖α‖ 1 = 1}. Then, ...