# Understanding similarity sensitive hashing algorithm in AdaBoost

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')}$

Algorithm

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.

• user11869, I was just checking in to see how this was going. In particular, despite appearances, I wonder whether you will get an answer here. I will see if I can post on the Meta here, there does seem to be a reputation lower bound for that. From my count of numbers of questions with related tags, certainly there are those who are able to answer you. Will, mathoverflow.net/users/3324/will-jagy and math.stackexchange.com/users/10400/will-jagy – Will Jagy Dec 5 '11 at 21:39
• I placed a question at local Meta: meta.stats.stackexchange.com/questions/1010/… – Will Jagy Dec 5 '11 at 22:17
• I really appreciate your help. Thanks! BTW, what is the Meta you mentioned above? – user11869 Dec 5 '11 at 22:19
• stats.stackexchange has its own discussion page for questions about policy. If you just click on meta.stats.stackexchange.com/questions/1010/… you will be sent to my question. If you then click on the word QUESTIONS it will show you all the most recent discussions. At the bottom of the page, you may then click to any of the total of 19 pages of discussions to see more. – Will Jagy Dec 5 '11 at 22:49

It seems like the exponential loss they refer to is:

$\sum_{f,f' \in N}\exp^{−sign(A_{i}f_p+b_i)sign(A_if'_p+b_i)}$

so I would imagine they simply take the argmin over $A \in \mathcal{A}$ and $b \in \mathcal{B}$ where $\mathcal{A}$ is the set of $A$ represented by the top ten eigenvectors, and $\mathcal{B}$ is some range (e.g. $b \in \left[-1,1\right]$, since $\left| A \right| \leq 1$ from the constrained eigendecomposition)

$\arg\min_{A \in \mathcal{A}, b \in \mathcal{B}} \sum_{f,f' \in N}\exp^{−sign(A_{i}f_p+b_i)sign(A_if'_p+b_i)}$

• Thanks. Is b the eigenvalue associated with the eigenvector A? – user11869 Dec 7 '11 at 19:31
• Is the goal to minimize the exponential loss or maximize it? The paper said A and b should be chosen such that the exponential loss is minimized, while your goal is to maximize it. But anyway, the point here is to increase the weights of mis-classified examples, am I correct? – user11869 Dec 8 '11 at 2:12
• Sorry yes that should have been argmin - I've updated. And yes that is the point – tdc Dec 8 '11 at 9:49
• And no, b doesn't enter into the eigenvalue decomposition. It's not quite clear they minimise over $b$ - I've updated the answer to give one idea how. Perhaps you could email the authors? – tdc Dec 8 '11 at 9:53
• I actually did contact the author before I post my question here. But I haven't heard anything back yet – user11869 Dec 8 '11 at 15:08