[Kai-Zhu_Huang,_Haiqin_Yang,_Michael_R._Lyu]_Machi(b-ok.org)

3.6 How Tight Is the Bound? 59given the fixed mean and covariance as m and σ respectively. This exampledemonstrates the inner rationality of the minimax probability machines. To further examine the tightness of the worst-case bound in Fig. 3.9(a),we vary β from 0 to 1 and plot against β the real test accuracy that a verticalFig. 3.9. Three two-dimensional data with the same means and covariances butwith different skewness. The worst-case accuracy bound of (a) is tighter than thatof (b) and looser than that of (c)line classifies the y data by using Eq.(3.46). Note that the real accuracy canbe calculated as Φ(z ≤ d). This curve is plotted in Fig. 3.10. Fig. 3.10. Three two-dimensional data with the same means and covari- ances but with different skewness. The worst-case accuracy bound of (a) is tighter than that of (b) and looser than that of (c) Observed from Fig. 3.9, the smaller the worst-case accuracy, the looser itis. On the other hand, if we skew the y data towards the left side, while simul-

60 3 A General Global Learning Model: MEMPMtaneously maintaining the mean and covariance unchanged (see Fig. 3.9(b)),even a bigger gap will be generated when β is small; analogically, if we skewthe data towards the right side (see Fig. 3.9(c)), a tighter accuracy bound willbe expected. This finding would mean that only adopting up to the secondorder moments may not achieve a satisfactory bound. In other words, for atighter bound, higher order moments such as skewness need to be consid-ered. This problem of estimating a probability bound based on moments ispresented as the (n, k, Ω)-bound problem, which means “finding the tightestbound for n-dimensional variable in the set Ω based on up to the k-th mo-ments.” Unfortunately, as proved in [24], it is NP-hard for (n, k, Rn)-boundproblems with k ≥ 3. Thus tightening the bound by simply scaling up themoment order may be intractable in this sense. We may have to exploit otherstatistical techniques to achieve this goal. Certainly, this deserves a closerexamination in the future.3.7 On the Concavity of MEMPMWe address the issue of the concavity on the MEMPM model in this sec-tion. We will demonstrate that although MEMPM cannot generally guaran-tee its concavity, there is strong empirical evidence showing that many real-world problems demonstrate reasonable concavity in MEMPM. Hence, theMEMPM model can be solved successfully by standard optimization meth-ods, e.g. the linear search method proposed in this chapter. We first present a lemma on BMPM.Lemma 3.10. The optimal solution for BMPM is a strictly and monotoni-cally decreasing function with respect to β0.Proof. Let the corresponding optimal worst-case accuracies on x be α1 andα2 respectively, when β01 and β02 are set as the acceptable accuracy levelsfor y in BMPM. We will prove that if β01 > β02, then α1 < α2. This can be proved by considering the contrary case, i.e. we assume α1 ≥α2. From the problem definition of BMPM, we have:α1 ≥ α2 =⇒ κ(α1) ≥ κ(α2)=⇒ 1 − κ(β01) w1TΣyw1 ≥ 1 − κ(β02) w2TΣyw2 ,(3.48)wT1 Σxw1 w2TΣxw2where, w1 and w2 are the corresponding optimal solutions which maximizeκ(α1) and κ(α2) respectively, when β01 and β02 are specified. From β01 > β02 and Eq.(3.48), we have1 − κ(β02) wT1 Σyw1 > 1 − κ(β01) w1TΣyw1 (3.49)w1TΣxw1 w1TΣxw1 (3.50) ≥ 1 − κ(β02) w2TΣyw2 . w2TΣxw2









































4.1 Maxi-Min Margin Machine 81 Nx +Ny min ξk, (4.23) ρ,w=0,b,ξ (4.24) k=1 (4.25) (4.26) s.t. wTxi + b ≥ ρ− ξi , wTΣxw − wTyj + b ≥ ρ − ξj+Nx , wTΣyw ρ ≥ A , ξk ≥ 0 ,where A is a positive constant parameter. Now if we expand Eq.(4.24) for each i and add them all together, we canobtain: wTx + b Nx Nx wTΣxw ≥ Nxρ − ξi . (4.27) i=1This equation can easily be changed as: Nx wTx + b ξi ≥ Nxρ − Nx . (4.28) wTΣxw i=1Similarly, if we expand Eq.(4.25) for each j and add them all together, weobtain: Ny wTy + b ξj+Nx ≥ Nyρ + Ny . (4.29) wTΣyw j=1By adding Eq.(4.28) and Eq.(4.29), we obtain:N wTx + b wTy + b ξk ≥ Nρ − Nx − Ny wTΣyw . (4.30) wTΣxwk=1 Nx +NyTo achieve minimum training error, namely, minρ,w=0,b,ξ k=1 ξk, wemay consider to minimize its lower bound as specified by the right hand sideof Eq.(4.30). Hence in this case ρ should attain its lower bound A, while thesecond part should be as large as possible, i.e. max θ wTx + b − (1 − θ) wTy + b , (4.31) w=0,b wTΣxw wTΣywwhere θ is defined as Nx/N and thus 1 − θ denotes Ny/N . If one furthertransforms the above to: