/
budget_perceptron.js
74 lines (70 loc) · 1.73 KB
/
budget_perceptron.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
/**
* Budget Perceptron
*/
export default class BudgetPerceptron {
// Online Classification on a Budget
// https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.3578&rep=rep1&type=pdf
/**
* @param {number} beta Tolerance
* @param {number} [n] Cachs size
*/
constructor(beta, n) {
this._beta = beta
this._n = n
this._w = null
this._c = 0
this._s = []
}
/**
* Fit model parameters.
*
* @param {Array<Array<number>>} x Training data
* @param {Array<1 | -1>} y Target values
*/
fit(x, y) {
if (!this._w) {
this._w = Array(x[0].length).fill(0)
}
for (let i = 0; i < x.length; i++) {
const pt = x[i].reduce((s, v, j) => s + v * this._w[j], this._c)
if (pt * y[i] <= this._beta) {
for (let j = 0; j < x[i].length; j++) {
this._w[j] += y[i] * x[i][j]
}
this._c += y[i]
if (this._n <= 0) {
for (let k = this._s.length - 1; k >= 0; k--) {
const r = this._s[k]
const pk = r.x.reduce((s, v, j) => s + v * (this._w[j] - r.y * r.x[j]), this._c - r.y)
if (pk * r.y > this._beta) {
continue
}
this._s.splice(k, 1)
}
} else if (this._s.length >= this._n) {
const p = this._s.map((r, m) => [
m,
r.x.reduce((s, v, j) => s + v * (this._w[j] - r.y * r.x[j]), this._c - r.y) * r.y,
])
p.sort((a, b) => b[1] - a[1])
this._s.splice(p[0][0], 1)
}
this._s.push({ x: x[i], y: y[i] })
}
}
}
/**
* 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], this._c)
p.push(m <= 0 ? -1 : 1)
}
return p
}
}