logistic_regression.py

from math import *
import random
import numpy as np

def sigmoid(s):
    return 1 / (1 + exp(-s))

class LogRegression:
    '''
    Implements Logistic Regression with Stochastic Gradient Descent
    fields:
    int dim             Dimensionality of the data
    int learning_rate   Learning rate
    ndarray weights     numpy ndarray (dim x 1) of the weights
    List data            Array (N x 1) of tuples (x, y) composed of vectors x and classification results y
    int epochs          Number of full passes of the N data points undergone
    '''
    def __init__(self, dim, rate, data = []):
        self.dim = dim
        self.learning_rate = rate
        self.reset(data)

    def reset(self, data):
        '''
        Reset weights and feed a data sample
        '''
        self.weights = np.zeros(self.dim+1)
        for t in data:
            if len(t[0])!=self.dim:
                raise ValueError('Wrong data dimensionality')
            elif t[1]!=1 and t[1]!=-1:
                raise ValueError('Function output is not binary')
        self.data = data
        self.epochs = 0

    def probability(self, x, y):
        '''
        Takes d-dimensional data vector x, binary value y=(+1 or -1) and computes P(y|x) using the current weights
        P(y|x) is the probability to obtain y from data point x
        '''
        x_adj = [1.0] + x    #adjusted to include 1 at the start
        s = y*np.dot(self.weights, x_adj)    #y * (dot product of w and x)
        return sigmoid(s)

    def cross_entropy_error(self, data):
        '''
        Computes the in-sample error Ein if given self.data as data,
        computes the out-of-sample error Eout if given a dataset generated by the original P(y|x) as data
        '''
        total_error = 0
        for point in data:
            total_error += log(1 / self.probability(point[0], point[1]))
        return total_error / len(data)

    def batch_error_gradient(self):
        '''
        Computes the current error gradient vector from all available data (batch)
        Not used in this implementation
        '''
        total_vector = np.zeros(self.dim+1)
        for point in self.data:
            x_adj = np.array([1.0] + point[0])
            total_vector += point[1]*x_adj / (1 + exp(point[1]*np.dot(self.weights, x_adj)))
        return -total_vector / len(self.data)

    def stochastic_error_gradient(self, point):
        '''
        Computes the current error gradient vector from a single point in the data
        The average direction will still be that of the batch gradient
        '''
        x_adj = np.array([1.0] + point[0])
        return -point[1]*x_adj / (1 + exp(point[1]*np.dot(self.weights, x_adj)))

    def gradient_descent(self, minstep):
        '''
        Stochastic Gradient Descent Algorithm
        An epoch 't' is a full pass through a random permutation of the N data points
        Stops when ||w of (t-1) - w of t|| < minstep
        '''
        indexes = list(range(len(self.data)))
        while True:
            prev_weights = np.copy(self.weights)
            random.shuffle(indexes)
            for i in indexes:
                self.weights -= self.learning_rate*self.stochastic_error_gradient(self.data[i])  #gradient descent
            self.epochs += 1
            if np.linalg.norm(prev_weights - self.weights) < minstep:   #stop condition
                break