alextp · August 22, 2010 19:59 · Aug 22, 2010
diff --git a/pegasos.py b/pegasos.py
@@ -0,0 +1,61 @@
+class OnlineLearner(object):
+    def __init__(self, **kwargs):
+        self.last_misses = 0.
+        self.iratio = 0.
+        self.it = 1.
+        self.l = kwargs["l"]
+        self.max_ratio = -np.inf
+        self.threshold = 500.
+
+    def hinge_loss(self, vector, cls, weight):
+        p = self.predict(vector)
+        hl = max(0, weight-cls*p)
+        if hl >= weight:
+            self.last_misses += 1.
+        ir = hl/weight
+        self.iratio += ir
+        if self.max_ratio < ir: self.max_ratio = ir
+        self.it += 1
+        if self.it % self.threshold == 0:
+            print str(type(self).__name__),
+            print "l", self.last_misses/self.threshold, "r", self.iratio/self.threshold, 
+            print "m", self.max_ratio
+            self.max_ratio = self.last_misses = self.iratio = 0
+        return hl
+
+class Pegasos(OnlineLearner):
+    def __init__(self, **kwargs):
+        super(Pegasos, self).__init__(**kwargs)
+        self.w = Z(kwargs["dim"], dtype=np.float32)
+        self.learn = True
+
+    def update(self, vector, cls, weight):
+        eta_t = 1./(self.l*self.it)
+        loss = self.hinge_loss(vector, cls, weight)
+        if not self.learn: return
+        if loss > 0:
+            self.w = (1-eta_t*self.l)*self.w + eta_t*cls*vector
+        else:
+            self.w = (1-eta_t*self.l)*self.w
+
+    def predict(self, vector):
+        return np.dot(vector, self.w)
+
+class KernelPegasos(OnlineLearner):
+    def __init__(self, **kw):
+        self.ws = []
+        self.y = []
+        super(KernelPegasos,self).__init__(**kw)
+        self.k = kw["kernel"]
+        self.learn = True
+
+    def update(self, vector, cls, weight):
+        loss = self.hinge_loss(vector, cls, weight)
+        if not self.learn: pass
+        if loss > 0:
+            self.ws.append(vector)
+            self.y.append(cls)
+
+    def predict(self, v):
+        return (1./(self.l*self.it))*sum(self.k(self.ws[i],v)*self.y[i] 
+                                         for i in xrange(len(self.ws)))