Vectorization of deep learning formula

This is my participation 8 The fourth of the yuegengwen challenge 18 God , Check out the activity details ：8 Yuegengwen challenge

---

Σ( ° △ °|||)︴ Let's start with a few nonsense . As a biology student （ At that time, all majors chose computers , As a result, I was forced to learn biology ）, But I had to study by myself . I use C++ As an introductory language , When I first started learning data structures , Because it's self-study , A lot of pain , I make complaints about it every day. ： Yes STL Why write it yourself ！！！ I learned later , In order to practice , Therefore, when you often brush questions, you can write some functions that even the library function already has to realize . At that time, all roads lead to Rome in my eyes , You can get the same result anyway . Although I learned the time complexity of the algorithm, I didn't put it into practice , After all, there is not so much test data in question brushing .

Later, an elder told me , You can have a look at the source code of the library function in your spare time . For example, the ranking of others may be a combination of several sorts , They are all algorithms optimized by various bosses .

Get down to business

This is also true for some formulas in our in-depth learning , If you can simplify , It's great to use the library of linear algebra built in the language .

Benefits of using built-in algorithms ：

• Faster
• Implemented in less code
• It's less error prone than what you write yourself
• Better coordination with hardware system

Take a simple chestnut ：

$h_{\theta}(x)=\sum_{j=0}^{n} \theta_{j} x_{j}$

You can think of it as $\theta^{T} x$ And calculate , This translates into two vectors $\theta=\left[\begin{array}{l}\theta_{0} \\ \theta_{1} \\ \theta_{2} \\ ... \end{array}\right] \quad x=\left[\begin{array}{l}x_{0} \\ x_{1} \\ x_{2} \\ ...\end{array}\right]$ The product of .

octave：

Unvectorized implementation

Is to declare two vectors , Traverse .

%  No vectorization code is as follows ：
prediction =0.0; 
for j = 1:n+l
    prediction = prediction + theta(j) * x(j)
end
 Copy code 

Vectorized implementation

%  After vectorization, the code is as follows ：
prediction= theta' * x; %  Single quotation mark in English  '  Represents the transpose of a matrix or vector . Forget to go back and see octave grammar   Copy code 

C++：

Unvectorized implementation

double prediction = 0.0; 
for(int j = 0; j<=n; j++)
{
    prediction += theta[j]*x[j];
}
 Copy code 

Vectorized implementation

double prediction = theta.transpose()*x;
 Copy code 

Another chestnut ：

This formula is familiar , Is the formula for gradient descent . In this formula x It's a data matrix ,y Is a column vector .

For multiple linear regression ：

First simplify the gradient descent formula to make it easier to write code ：

among δ It's a column vector ： $\delta=\left[\begin{array}{l} \delta_{0} \\ \delta_{1} \\ \delta_{2} \\... \end{array}\right]$

And for x Come on , $x^{(i)}=\left[\begin{array}{c} x_{0}^{(i)} \\ x_{1}^{(i)} \\ x_{2}^{(i)} \\... \end{array}\right]$

So it must be $\delta_{n \times 1} = Count ×(...)× x_{1×n}^{(i)}$ namely $x_j^{(i)}$ To transpose .

If this logic is not vectorized, it may need to write many cycles to complete . Just a little garbage like me can't write it for a while . I'm handy c++ I wrote it , No guarantee, right , Just take a general look , I didn't run this code either .

for(int j=0;j<n;j++)
{
    // First calculate h(x) Come on 
    for(int i=0;i<len;i++)
    {
        hx[i] += theta[i][j]*x[i][j];
    }
    // Calculation [h(x)-j]*x And sum up 
    for(int i=0;i<len;i++)
    {
        sum += (h[i] - y[i])*x[i][j]; 
    }
    // The rest of the formula 
    theta[j] = theta[j] - alpha * (1/m) * sum;
}
 Copy code 

But if you vectorize it, you can write it as ：

%  Suppose it's binary now 
hx = X * theta;
theta(1) = theta(1) - alpha * (1/m) * sum((hx-y)*X(:,1:1))
theta(2) = theta(2) - alpha * (1/m) * sum((hx-y)*X(:,2:2))
% Be careful octave and C And so on , Subscript from 1 Start 
 Copy code 

%  If it is n yuan 
hx = X * theta;
for i = 1:n
    theta(i) = theta(i) - alpha * (1/m) * sum((hx-y)*X(:,i:i))
    % Be careful octave and C And so on , Subscript from 1 Start 
endfor
 Copy code 

After vectorization, everything is easy to deal with , But without vectorization , Then you may have to nest a lot for Circulated . So we should make good use of vectorization to reduce the workload .