How to understand incremental stochastic gradient algorithm and its implementation in logistic regression [updated]?

Question

I have a difficulty where to start the implementation of incremental stochastic gradient descent algorithm and its respective implementation in logistic regression. I don't quite understand this algorithm and there are few sources to explain it with crystal-clear interpretation and possible demo code. I am quite new with ML algorithm and I have no idea which would be efficient workaround to solve this problem.

In particular, the problem I am studying is to implement hogWild! algorithm for logistic regression, which asks me to program incremental SGD algorithm with a sequential order. Can anyone give me a general idea or possible pipeline to make this happen in python?

logistic loss function and gradient

Here is my implementation:

import numpy as np
import scipy as sp
import sklearn as sl
from scipy import special as ss
from  sklearn import datasets

X_train, y_train=datasets.load_svmlight_file('/path/to/train_dataset')
X_test,y_test=datasets.load_svmlight_file('/path/to/train_dataset.txt', 
                                          n_features=X_train.shape[1])

class ISGD:
def lossFunc(X,y,w):
    w.resize((w.shape[0],1))
    y.resize((y.shape[0],1))

    lossFnc=ss.log1p(1+np.nan_to_num(ss.expm1(-y* np.dot(X,w,))))
    rslt=np.float(lossFnc)
    return rslt

def gradFnc(X,y,w):
    w.resize((w.shape[0],1))
    y.resize((y.shape[0],1))

    gradF1=-y*np.nan_to_num(ss.expm1(-y))
    gradF2=gradF1/(1+np.nan_to_num(ss.expm1(-y*np.dot(X,w))))
    gradF3=gradF2.resize(gradF2.shape[0],)
    return gradF3

def _init_(self, learnRate=0.0001, num_iter=100, verbose=False):
    self.w=None
    self.learnRate=learnRate
    self.verbose=verbose
    self.num_iter=num_iter


def fitt(self, X,y):
    n,d=X.shape
    self.w=np.zeros(shape=(d,))

    for i in range(self.num_iter):
        print ("\n:", "Iteration:", i)

        grd=gradFnc(self.w, X,y)
        grd.resize((grd.shape[0],1))
        self.w=self.w-grd
        print "Loss:", lossFunc(self.w,X,y)

    return self

Seems my above implementation has some problems. Can anyone help me how to correct that? Plus, I don't have a solid idea how to implement incremental SGD sequentially. How can I make this happen? Any idea?

Answer 1

Gradient Descent

The idea of gradient descent is to traverse a function $f_{LR}(\textbf{w})$ and find a local maximum or minimum for a set a values $\textbf{w}$. Gradient descent is an iterative process. At each iteration you will evaluate the function given your current set of values. Then you will take the derivative of that function with respect to those values to see how much each value contributes to the slope of the function. We can then change the values in a proportionate way to move towards this optimal point.

The gradient descent equation is described as

$\textbf{w}^{(k+1)} = \textbf{w}^{(k)} - \rho \frac{\partial f_{LR}(\textbf{w})}{\partial \textbf{w}^{(k)}}$

where $\rho$ is the learning rate, usually small number. A constant which determines the speed at which we want to change the values we are optimizing.

Initializing the values

There's many ways to initialize these values. We can either set them all to zero, or set them randomly.

Then you can take a random instance in your dataset $x_i$ and $y_i$ and compute the derivative

$\frac{\partial f_{LR}(\textbf{w})}{\partial \textbf{w}^{(k)}} = \textbf{x}_i (-y_i \frac{e^{-y_i \textbf{x}_i \textbf{w}}}{1 + e^{-y_i \textbf{x}_i \textbf{w}}})$.

Once the compute this you can put the result into the gradient descent equation and update all your weights.

You then continue to go through this process until your weights $\textbf{w}$ converge to a value, or some other condition is met. You might want to limit your algorithm with some iteration counter to avoid infinite loops caused by weights that do not converge.

---

Gradient Descent Code

Here is an example using gradient descent to train weights along the logistic regression loss function.

import numpy as np

def update_weights(x_i, y_i, w):
   p = 0.8                  # The learning rate
   yhat = predict(x_i, w)   # The predicted target
   error = y_i - yhat       
   return w + p * (y_i - yhat) * x_i  # Update the weights

def predict(x_i, w):
   return 1/(1+np.exp(-1 * np.dot(w.T, x_i)))

def train_weights(x, y, verbose = 0):
   w = np.zeros((x.shape[1],))
   w_temp = np.zeros((x.shape[1],)) 

   epoch = 0
   while epoch <= 1000:
      for i, x_i in enumerate(x):
         w = update_weights(x_i, y[i], w)

      pred = 1/(1+np.exp(-1 * np.dot(x, w)))
      error = np.sum(pred - y)

      pred[pred < 0.5] = 0
      pred[pred >= 0.5] = 1
      epoch += 1

      if verbose == 1:
         print('------------------------------------------------')
         print('Targets: ', y)
         print('Predictions: ', pred)
         print('Predictions: ', pred)
         print('------------------------------------------------')

      # Check if we have reach convergence
      if np.sum(np.abs(w_temp - w)) < 0.001:
         print(epoch)
         print(error)
         return w
      else: 
         w_temp = w
  return w

# Create some artificial database
x = np.zeros((4,3))
y = np.zeros((4,)) 
x[0] = [1, 1, 1]
x[1] = [1, 2, 2]
x[2] = [1, 10, 10]
x[3] = [1, 11, 11]
y[0] = 0
y[1] = 0
y[2] = 1
y[3] = 1

print(x)
print(y)

# Train the weights
w = train_weights(x, y, 0)
print('Trained weights: ', w)

# Get predicitons
pred = 1/(1+np.exp(-1 * np.dot(x, w)))
error = np.sum(pred - y)   
pred[pred < 0.5] = 0
pred[pred >= 0.5] = 1
print('Predictions: ', pred)