-
Notifications
You must be signed in to change notification settings - Fork 0
/
MLpseudo.txt
95 lines (74 loc) · 2.81 KB
/
MLpseudo.txt
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
# We are given two nodes (items or brands)
Node1, Node2
# This type is a rating for both nodes in a link; r1, r2 in {1,2,3,4,5}
type rating = int*int
# This is the set of all differences of ratings between Node1 and Node2.
# For example, if a user rates Node1 as a 1 and Node2 as a 3, then 2 (or -2, depending on orientation) will be added to this set.
type differences = int list
# Mean of all points in differences
type m = float
# Standard Deviation of all points in differences
type s = float
# Size of differences
type n = int
# Confidence, which will be determined via machine learning function
type c = float
# List of predictions given to users in the past
type predicted = (int*user) list
# List of ratings that the same users supplied after purchasing
type purchased = (int*user) list
# This type represents a pair of *items* when confidence is being calculated for real links, and a pair of *brands* when confidence is being calculated for virtual links
type link = (m,s,n,c,predicted,purchased)
# Given two variables relating to the same pair:
Let x be of type link
Let r be of type rating
# Returns (new mean, new stdev) given addition of new element
def update(m, std, n, x):
newm = (m*n + x)/(n+1)
diff = (newm - m)*(newm - m)*n+(x-newm)*(x-newm)
newstd = sqrt((std * std * n + diff)/(n+1))
return (newm, newstd)
# Increment n
Let inc (n_0 : n) : n = n_1++
# Update c
# This function gives a new confidence. It is the one which will be modified with higher order functions; k_1 is a constant float which will be modified.
Let f (n_0 : n) (s_0 : s) : c=
k_1 * log(n_0 / s_0)
# Update predicted
Add this user and prediction to the predicted list
# purchased will be updated after user rates
# Learning the confidence function f by comparing predictions to user responses. This higher order function will be executed every time purchased is updated.
# First, calculate the actual confidence.
Let count = 0
Let correct_count = 0
For each pur_pair in purchased:
let x1 = the int component of pur_pair
let x2 = the int component of corresponding pre_pair in predicted
if x1 = x2 then correct_count++
count++
actual_confidence = correct_count / count
# Now compose a set of actual values, which we will train f to fit
actual_values = (n, log(s/c)) list
Open scikit-learn package
use sklearn.linear_model.LinearRegression for n, log(s/c)
return k_1
# Dijkstra's algorithm: returns shortest path between start and end in graph:
def Dijkstra's(G, start, end):
dist = {start : 0}
prev = {}
Q = Heap(start : 0)
for v in G:
dist[v] = -1
prev[v] = None
iterator = start
while(!Q.empty())
u = Q.pop()
if dist[u] == -1:
break
for neighbor in G.array[u]:
alt = dist[u] + G.getDist(u,neighbor)
if alt < dist[neighbor]:
dist[neighbor] = alt
prev[neighbor] = u;
Q.insert(neighbor, dist[neighbor])
return dist[end]