24
$\begingroup$

Just covered Andrew Ng's Non-linear Hypothesis of Neural Netowrks, and we had a multiple choice question for determining number of features for an image of resolution 100x100 of grescale intensities.

And the answer was 50 million, $5$ x $10^7$

However, earlier for a 50 x 50 pixel, grey scale image. the number of features is 50x50 (2500)

Why would it be $5$ x $10^7$ instead of $10,000$?

He does however say including all quadratic terms ($x_ix_j$) as features

Suppose you are learning to recognize cars from 100×100 pixel images (grayscale, not RGB). Let the features be pixel intensity values. If you train logistic regression including all the quadratic terms ($x_ix_j$) as features, about how many features will you have?

and in the earlier slide regarding the 100x100, that the quadratic features ($x_i$ x $x_j$) = 3 million features, but I still can't put a finger on the connection.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ if you have 100*100 pixel images that means, 100*100 = 10000 features and the formula is ((n features) square)/2 i.e., n=10000, ((n features) square)/2 => (10000 * 10000)/2 => 100000000/2 => 50000000 $\endgroup$
    – Ajay Raj
    May 8, 2020 at 1:37

3 Answers 3

Reset to default
19
$\begingroup$

Perhaps a simpler case will make things clearer. Lets say we choose a 1x2 sample of pixels instead of 100x100.

Sample Pixels From the Image

+----+----+
| x1 | x2 |
+----+----+

Imagine when plotting our training set, we noticed that it can't be separated easily with a linear model, so we choose to add polynomial terms to better fit the data.

Let's say, we decide to construct our polynomials by including all of the pixel intensities, and all possible multiples that can be formed from them.

Since our matrix is small, let's enumerate them:

$$x_1,\ x_2,\ x_1^2,\ x_2^2,\ x_1 \times x_2,\ x_2 \times x_1 $$

Interpreting the above sequence of features can see that there is a pattern. The first two terms, group 1, are features consisting only of their pixel intensity. The following two terms after that, group 2, are features consisting of the square of their intensity. The last two terms, group 3, are the product of all the combinations of pairwise (two) pixel intensities.

group 1: $x_1,\ x_2$

group 2: $x_1^2,\ x_2^2$

group 3: $x_1 \times x_2,\ x_2 \times x_1$

But wait, there is a problem. If you look at the group 3 terms in the sequence ($ x_1 \times x_2$ and $x_2 \times x_1$) you'll notice that they are equal. Remember our housing example. Imagine having two features x1 = square footage, and x2 = square footage, for the same house... That doesn't make any sense! Ok, so we need to get rid of the duplicate feature, lets say arbitrarily $x_2 \times x_1$. Now we can rewrite the list of group three features as:

group 3: $x_1 \times x_2$

We count the features in all three groups and get 5.

But this is a toy example. Lets derive a generic formula for calculating the number of features. Let's use our original groups of features as a starting point.

$size group 1 + size group 2 + size group 3 = m \times n + m \times n +m \times n = 3 \times m \times n$

Ah! But we had to get rid of the duplicate product in group 3.

So to properly count the features for group 3 we will need a way to count all unique pairwise products in the matrix. Which can be done with the binomial coefficient, which is a method for counting all possible unique subgroups of size k from an equal or larger group of size n. So to properly count the features in group 3 calculate $C(m \times n, 2)$.

So our generic formula would be:

$$ m \times n + m \times n +C(m \times n, 2) = 2m \times n + C(m \times n, 2) $$

Lets use it to calculate the number of features in our toy example:

$$2 \times 1 \times 2 + C(1 \times 2, 2) = 4 + 1 = 5$$

Thats it!

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Wish this explanation had been given in the lecture! $\endgroup$
    – Ian Walker-Sperber
    Jan 16, 2018 at 14:00
  • $\begingroup$ I am wondering how we supposed to know this in the course without being explained $\endgroup$
    – Mohammed Noureldin
    Feb 26, 2019 at 15:34
  • $\begingroup$ @MohammedNoureldin binomial coefficients are thought in high-school/secondary level. $\endgroup$
    – Ryuu
    Feb 25, 2020 at 6:27
6
$\begingroup$

If you are using all the linear and quadratic features, the total number is supposed to be:

100*100 + 100*100 + C(100*100,2) = 50015000
10000   + 10000   + 49995000     = 50015000
xi         xi^2       xixj

To calculate the combination in Octave/Matlab,

octave:23> nchoosek(100*100,2)
ans =  49995000
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Can you explain it a little bit further? are you saying xi + xi^2 + xixi? Is xi = 100, and xj = 100? why is xi and xi^2 both are 100*100? What is C(100*100,2)? $\endgroup$
    – Iancovici
    Dec 29, 2013 at 18:52
  • 4
    $\begingroup$ (1)there are totally 100*100 pixels, if you are using intensity as features, there will be 100*100 features in total, that's xi; and (ii) you may also use the power density as a feature, that's (xi,xi) or xi.^2, still 100*100 in total; finally(iii) if you use the correlations between two pixels, there will be C pairs of pixels in total, that's (xi,xj), C is combination in math (mathworld.wolfram.com/Combination.html) $\endgroup$
    – lennon310
    Dec 29, 2013 at 19:20
  • $\begingroup$ Thanks, one last question is why does xi = xi^2 in this context? $\endgroup$
    – Iancovici
    Dec 30, 2013 at 1:39
  • $\begingroup$ I used xi to represent single pixel, and xi^2 means use pairs of the same pixel (xi,xi). The number of single pixel is the same of pairs of the same pixel. It has nothing to do with the pixel intensity. Sorry for the confusion. $\endgroup$
    – lennon310
    Dec 30, 2013 at 1:49
  • $\begingroup$ Same question, a few years later. Shouldn't we take into account also the possible intensity values (from 0 to 255)? $\endgroup$
    – albus_c
    Nov 8, 2018 at 10:37
0
$\begingroup$

The idea of ($x^2$)/2 might also work to obtain the quadratic features. So if n = 2500, then we know that x(i) = 2500 and substituting x in the formula will give 50 million

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I obtain $2500^2/2 \approx 3 $ million, not $50$ million. $\endgroup$
    – whuber ♦
    Jun 5, 2019 at 18:10
  • $\begingroup$ @whuber 50 million comes when you have 100*100 pixel image. where square(100*100) = 100000000 (10 million) and square(100*100)/2 = 5 million. Hope this answers. $\endgroup$
    – Tahir Ahmad
    Jul 28, 2019 at 13:58
  • $\begingroup$ @Tahir Right. So what is the value of "2500" doing in this answer?? $\endgroup$
    – whuber ♦
    May 8, 2020 at 13:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.