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

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?

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

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

w.resize((w.shape[0],1))
y.resize((y.shape[0],1))

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.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?

• 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". – JahKnows Jan 25 '18 at 10:39
• @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? – Andy.Jian Jan 26 '18 at 16:11
• Jian I edited my answer to add the corresponding code. – JahKnows Jan 26 '18 at 19:09

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.

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)

• 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. – Andy.Jian Jan 25 '18 at 10:55
• Yah I'll append some code, one sec. – JahKnows Jan 26 '18 at 2:03