pegasos.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#  pegasos.py
#  
#  Copyright 2013 nipun batra <nipunb@iiitd.ac.in>
#  
#  This program is free software; you can redistribute it and/or modify
#  it under the terms of the GNU General Public License as published by
#  the Free Software Foundation; either version 2 of the License, or
#  (at your option) any later version.
#  
#  This program is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#  
#  You should have received a copy of the GNU General Public License
#  along with this program; if not, write to the Free Software
#  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
#  MA 02110-1301, USA.
#  
#  



import numpy as np
import math
import random
def train(X,Y,lam=1,T=2000,k=None,tolerance=.0000001):
	num=len(X[0])
	w=np.zeros(shape=(T+1,num))
	len_y=len(Y)
	if k is None:
		k=int(math.ceil(0.1*len_y))
	#Create a weight vector of 1*Dimensions
	w[0]=np.random.rand(1,num)[0]
	#Find norm of this weight vector
	norm=np.linalg.norm(w[0])
	w[0]=w[0]/norm
	w[0]=w[0]/math.sqrt(lam)
	
	#Now choosing 'k' random points to include in At
	for i in range(0,T):
		
		b=(Y-np.dot(X,w[i].transpose())).mean()
		idx=random.sample(range(0,len_y), k)
		xt=X[idx]
		yt=Y[idx]
		
		idx1=((np.dot(xt,w[i].transpose())+b)*yt)<1;
		xt_plus=xt[idx1]
		yt_plus=yt[idx1]
		
		etat=1.0/(lam*T)
		sum_temp2=np.sum(xt_plus*yt_plus[:,np.newaxis],0)
		if sum_temp2.shape[0]>0:
			w_temp=(1-etat*lam)*w[i]+(etat/k)*sum_temp2
				
		w[i+1]=min(1,(1.0/(math.sqrt(lam)*np.linalg.norm(w_temp))))*w_temp
		
	
	b=(Y-np.dot(X,w[T].transpose())).mean()
	sv=np.dot(X,w[T].transpose())+b
	return w[T],b,sv
	
def test(X,Y,weight_vector,b):
		positive_count=(np.dot(X,weight_vector.transpose())+b)
		return positive_count
'''
print train(np.array([[2,3,4],[2,3,4],[5,3,2],[5,2,1]]),np.array([1,-1,1,4]),1,1000)
'''