I was reading these slides about Bag of Features (BoF). At slide 23 you can read:
each image is represented by a vector, typically 1000-4000 dimension, normalization with L1/L2 norm
What does the bold phrase means?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ I know what that L2 Eucledian distance is. I don't know what normalize an histogram with such a norm means $\endgroup$– user6321Commented Jul 20, 2016 at 13:41
-
$\begingroup$ I just noticed that the title is incompleate, I'm sorry for that $\endgroup$– user6321Commented Jul 20, 2016 at 13:41
-
1$\begingroup$ @Tim and I answered your previous question, and now you are bringing a new question. Really, you shouldn't post updates. Post these as new questions instead. $\endgroup$– FirebugCommented Jul 20, 2016 at 14:41
-
$\begingroup$ You're right. If you're still interested to answer, look at this question. $\endgroup$– user6321Commented Jul 20, 2016 at 15:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
$L_p$ normalization is actually described in Wikipedia that quotes Dalal and Triggs (2005)
Dalal and Triggs explored four different methods for block normalization. Let $v$ be the non-normalized vector containing all histograms in a given block, $\|v\|_k$ be its $k$-norm for $k={1,2}$ and $e$ be some small constant (the exact value, hopefully, is unimportant). Then the normalization factor can be one of the following:
L2-norm: $f = {v \over \sqrt{\|v\|^2_2+e^2}}$
(...)
L1-norm: $f = {v \over (\|v\|_1+e)}$
L1-sqrt: $f = \sqrt{v \over (\|v\|_1+e)}$
So $L_p$ normalization of histograms in fact relates to using $L_p$ norms to normalize vectors.
By "dimensions" authors mean the "length" of vectors.
Dalal, N., & Triggs, B. (2005). Histograms of oriented gradients for human detection. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) (Vol. 1, pp. 886-893). IEEE.
-
$\begingroup$ Thanks for your answer. Ok, should be unimportant, but some suggestion about the value of $e$? $\endgroup$– user6321Commented Jul 20, 2016 at 14:35
-
-
2$\begingroup$ @user6321 you changed your question to different one - please do not to that. You should rather accept one of the answers (it they answer your initial question) and start a new question. $\endgroup$– TimCommented Jul 20, 2016 at 14:45
-
-
1$\begingroup$ @user6321 thanks :) This makes this site much better organized and in fact makes you more likely to receive answer to the new question because people may be less prone to look at edited question then to check the new question (such new question would be also longer visible on the list of new questions comparing to the edited one). $\endgroup$– TimCommented Jul 20, 2016 at 15:10
$\begingroup$
$\endgroup$
8
Well, if I had to guess what the slide is referring to:
$L_{2}$ normalization $$x_i'=\frac{x_i}{\|x\|_2}=\frac{x_i}{\left(\sum_j{x_j^2}\right)^{1/2}}$$
$L_{1}$ normalization $$x_i'=\frac{x_i}{\|x\|_1}=\frac{x_i}{\sum_j{|x_j|}}$$
The $L^{p}$ norm is given by $\|x\|_{p}=\sqrt[p]{\sum_i|x_i|^{p}}, p \in \mathbb{R}$ (link).
-
$\begingroup$ I'm sorry, but I don't understand your annotation. $x_i$ is a the i-th vector? Or is it the i_th dimension of vector x? $\endgroup$– user6321Commented Jul 20, 2016 at 13:53
-
-
$\begingroup$ @Tim it's an answer, because that's the definition of the $L^{p}$ norm, but it's a guess because I'm not sure that's what the slide is referring to. $\endgroup$– FirebugCommented Jul 20, 2016 at 13:57
-
$\begingroup$ @user6321 $x_i$ is the $i$-th position of the $x$ vector, yes. See the denominator is the norm I refer to. $\endgroup$– FirebugCommented Jul 20, 2016 at 13:58
-
1$\begingroup$ An answer. Actually, it is the same as used in loss-regularization techniques for example. Of course, in other fields, other L-norms exists (say, more general definitions), but regarding ML this is the commonly used one. $\endgroup$– Mayou36Commented Jul 20, 2016 at 14:01