Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi all,

I'm a CS major and don't quite understand the mathematics behind a optimization problem coming from a machine learning algorithm. The algorithm is in Section 5 of the paper http://visl.technion.ac.il/bron/publications/BroBroOvsGuiTOG10.pdf

Problem Statement

given $P$ pairs of examples $(f_p, {f_p}')$ labeled by {1,-1}, where $f_p$ is a v-dimensional feature vector and +1 (reps., -1) indicates similar (reps., dissimilar) pairs, the goal is to find the $s$X$v$ matrix A and $v$X1 vector b such that $d_{A,b}$ reflects the desired similarity of the training examples. The distance $d_{A,b}$ is defined as:

$d_{A,b}(x, x')=d_H(\mbox{sign}(Af+b), \mbox{sign}(Af'+b))$,

where $d_H(y,y')=\frac{s}{2}-\frac{1}{2}\sum_{i=1}^s\mbox{sign}(y_i{y_i}')$ is the Hamming metric in the s-dimensional Hamming space of binary sequences of length s.

Ideally, we would like to achieve $d_{A,b}(f,f')\leq d_0$ for similar pairs (P) and $d_{A,b} > d_0$ for dissimilar ones (N), where $d_0$ is some threshold. However, in practice ,there always exists false positives and false negatives. Thus, optimal A, b should miminize:

$min\frac{1}{P}\sum_{(f,f')\in P}e^{\mbox{sign}(d_{A,b}(f,f')-d_0)}+\frac{1}{N}\sum_{(f,f')\in N}e^{\mbox{sign}(d_0-d_{A,b}(f,f')}$


The learning of the optimal parameters A and b is posed as a boosted binary classification problem, where $\mbox{sign}(Af+b)$ acts as a strong binary classifier and each dimension of the linear projection $\mbox{sign}(A_ix+b_i)$ is a weak classifier. This way, the AdaBoost algorithm (http://www.cs.rochester.edu/users/faculty/stefanko/Teaching/09CS446/Boosting2.pdf) can be used to progressively construct A and b. Intuitively, this algorithm increases the weights of incorrectly classified examples so that the learner is forced to focus on the hard examples in the training set.

Input: P pairs of examples $(f_p, {f_p}')$ labeled by $s_p$

  1. Initialize ${w_p}^i=1/P$
  2. For i = 1, ..., d do

    Set the ith row of A and b by solving the optimization problem $(A_i, b_i)=\min \sum_{p=1}^P {w_p}^is_p(2-\mbox{sign}(A_if_p+b_i))(2-\mbox{sign}(A_i{f_p}'+b_i))$

    Update weights ${w_p}^{i+1}={w_p}^ie^{-s_p\mbox{sign}(A_if_p+b_i)\mbox{sign}(A_i{f_p}'+b_i)}$

My Question The optimization in the above algorithm is difficult, so the author tried to solve a simpler problem by setting

$A_i=\arg \max \frac{{A_i}^TC_NA_i}{{A_i}^TC_PA_i}$

where $C_P$ and $C_N$ are covariance matrices of the positive and negative example pairs

The author says that $A_i$ maximizing the above formula is the largest generalized eigenvector of ${C_P}^{-1/2}{C_N}^{1/2}$. Since this do not coincide exactly with the original optimization problem, the author select a subspace spanned by the largest 10 eigenvectors, out which direction and as well as the threshold parameter b minimizing the exponential loss are selected. I don't understand how the selection is done. Can anyone explain to me? Thanks a lot.

share|improve this question
I know nothing about this, but I can tell you that few on MO know more than that. I will leave this be. However, I am confident that you will have a much better time at $$ stats.stackexchange.com/questions $$ where the search features list 314 questions tagged machine-learning, 96 questions tagged data-mining, 74 questions tagged algorithms. From stats.stackexchange.com/faq it is clear your question will do well there. Here, we don't really do tutorials on undergraduate level material. –  Will Jagy Dec 5 '11 at 3:59
@Will thank you for the info –  user19736 Dec 5 '11 at 4:05
Well, successfully posted as stats.stackexchange.com/questions/19359/… as I requested. I'm curious to see how they treat it. –  Will Jagy Dec 5 '11 at 4:19
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.