2
$\begingroup$

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

enter image description here

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?

$\endgroup$
  • $\begingroup$ Please post the entirety of your code for us to be able to look at it. It seems you have an init function outside a class. That function header is also missing a d, for "def". $\endgroup$ – JahKnows Jan 25 '18 at 10:39
  • $\begingroup$ @JahKnows Thank you. How can I deal with the implementation of sequential incremental stochastic gradient descent algorithm? How to get started with that? Any idea? $\endgroup$ – Andy.Jian Jan 26 '18 at 16:11
  • $\begingroup$ Jian I edited my answer to add the corresponding code. $\endgroup$ – JahKnows Jan 26 '18 at 19:09
2
$\begingroup$

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)
$\endgroup$
  • 1
    $\begingroup$ Any possible update on my implementation respect to the problem that I stated above? Plus how can I implement incremental SGD sequentially? Would it possible for you to update your motivated answer with the possible code? Thanks for your help. $\endgroup$ – Andy.Jian Jan 25 '18 at 10:55
  • $\begingroup$ Yah I'll append some code, one sec. $\endgroup$ – JahKnows Jan 26 '18 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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