/
pegasos.js
98 lines (92 loc) · 2.21 KB
/
pegasos.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
* Primal Estimated sub-GrAdientSOlver for SVM
*/
export default class Pegasos {
// https://www.slideshare.net/hirsoshnakagawa3/ss-32274089
// Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
// https://home.ttic.edu/~nati/Publications/PegasosMPB.pdf
/**
* @param {number} rate Learning rate
* @param {number} [k] Batch size
*/
constructor(rate, k = 1) {
this._r = rate
this._k = k
this._itr = 100
this._do_projection = false
}
/**
* Initialize this model.
*
* @param {Array<Array<number>>} train_x Training data
* @param {Array<1 | -1>} train_y Target values
*/
init(train_x, train_y) {
this._x = train_x
this._y = train_y
this._t = 0
this._w = Array(this._x[0].length).fill(0)
this._b = 0
}
/**
* Update model parameters with some data.
*
* @param {Array<Array<number>>} x Training data
* @param {Array<1 | -1>} y Target value
*/
update(x, y) {
this._t++
const eta = 1 / (this._r * this._t)
const n = x.length
const wt = Array(this._w.length).fill(0)
let bt = 0
for (let i = 0; i < n; i++) {
const m = x[i].reduce((s, v, j) => s + v * this._w[j], 0) + this._b
if (m < 1) {
for (let j = 0; j < x[i].length; j++) {
wt[j] += y[i] * x[i][j]
}
bt += y[i]
}
}
this._w = this._w.map((v, j) => (1 - eta * this._r) * v + (eta * wt[j]) / n)
this._b = (1 - eta * this._r) * this._b + (eta * bt) / n
if (this._do_projection) {
const r = 1 / (Math.sqrt(this._r) * Math.sqrt(this._w.reduce((s, v) => s + v ** v, this._b ** 2)))
if (r < 1) {
this._w = this._w.map(v => v * r)
this._b *= r
}
}
}
/**
* Fit model parameters.
*/
fit() {
const n = this._x.length
for (let i = 0; i < this._itr; i++) {
const x = []
const y = []
for (let k = 0; k < this._k; k++) {
const r = Math.floor(Math.random() * n)
x.push(this._x[r])
y.push(this._y[r])
}
this.update(x, y)
}
}
/**
* Returns predicted values.
*
* @param {Array<Array<number>>} data Sample data
* @returns {(1 | -1)[]} Predicted values
*/
predict(data) {
const p = []
for (let i = 0; i < data.length; i++) {
const m = data[i].reduce((s, v, j) => s + v * this._w[j], 0)
p.push(m + this._b <= 0 ? -1 : 1)
}
return p
}
}