-
Notifications
You must be signed in to change notification settings - Fork 3
/
project1.py
390 lines (331 loc) · 13.9 KB
/
project1.py
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
from string import punctuation, digits
import numpy as np
import random
# Part I
def get_order(n_samples):
try:
with open(str(n_samples) + '.txt') as fp:
line = fp.readline()
return list(map(int, line.split(',')))
except FileNotFoundError:
random.seed(1)
indices = list(range(n_samples))
random.shuffle(indices)
return indices
def hinge_loss_single(feature_vector, label, theta, theta_0):
"""
Finds the hinge loss on a single data point given specific classification
parameters.
Args:
feature_vector - A numpy array describing the given data point.
label - A real valued number, the correct classification of the data
point.
theta - A numpy array describing the linear classifier.
theta_0 - A real valued number representing the offset parameter.
Returns: A real number representing the hinge loss associated with the
given data point and parameters.
"""
z = label*(theta.dot(feature_vector)+theta_0)
singleHingeLoss = 1-z
if z >= 1:
singleHingeLoss = 0
return singleHingeLoss
raise NotImplementedError
def hinge_loss_full(feature_matrix, labels, theta, theta_0):
"""
Finds the total hinge loss on a set of data given specific classification
parameters.
Args:
feature_matrix - A numpy matrix describing the given data. Each row
represents a single data point.
labels - A numpy array where the kth element of the array is the
correct classification of the kth row of the feature matrix.
theta - A numpy array describing the linear classifier.
theta_0 - A real valued number representing the offset parameter.
Returns: A real number representing the hinge loss associated with the
given dataset and parameters. This number should be the average hinge
loss across all of the points in the feature matrix.
"""
Z = 0
for i in range(len(feature_matrix)):
Z += hinge_loss_single(feature_matrix[i], labels[i], theta, theta_0)
return Z / len(labels)
raise NotImplementedError
def perceptron_single_step_update(
feature_vector,
label,
current_theta,
current_theta_0):
"""
Properly updates the classification parameter, theta and theta_0, on a
single step of the perceptron algorithm.
Args:
feature_vector - A numpy array describing a single data point.
label - The correct classification of the feature vector.
current_theta - The current theta being used by the perceptron
algorithm before this update.
current_theta_0 - The current theta_0 being used by the perceptron
algorithm before this update.
Returns: A tuple where the first element is a numpy array with the value of
theta after the current update has completed and the second element is a
real valued number with the value of theta_0 after the current updated has
completed.
"""
tx = np.dot(current_theta, feature_vector)
txtz = tx + current_theta_0
ytx = label * tx
ytxtz = label * txtz
if ytxtz <= 0:
current_theta += label*feature_vector
current_theta_0 += label
return (current_theta, current_theta_0)
raise NotImplementedError
def perceptron(feature_matrix, labels, T):
"""
Runs the full perceptron algorithm on a given set of data. Runs T
iterations through the data set, there is no need to worry about
stopping early.
NOTE: Please use the previously implemented functions when applicable.
Do not copy paste code from previous parts.
NOTE: Iterate the data matrix by the orders returned by get_order(feature_matrix.shape[0])
Args:
feature_matrix - A numpy matrix describing the given data. Each row
represents a single data point.
labels - A numpy array where the kth element of the array is the
correct classification of the kth row of the feature matrix.
T - An integer indicating how many times the perceptron algorithm
should iterate through the feature matrix.
Returns: A tuple where the first element is a numpy array with the value of
theta, the linear classification parameter, after T iterations through the
feature matrix and the second element is a real number with the value of
theta_0, the offset classification parameter, after T iterations through
the feature matrix.
"""
# Your code here
(n, k) = feature_matrix.shape
theta = np.zeros(k)
theta_0 = 0.0
for t in range(T):
for i in get_order(n):
# Your code here
theta, theta_0 = perceptron_single_step_update(feature_matrix[i], labels[i], theta, theta_0)
return (theta, theta_0)
raise NotImplementedError
def average_perceptron(feature_matrix, labels, T):
"""
Runs the average perceptron algorithm on a given set of data. Runs T
iterations through the data set, there is no need to worry about
stopping early.
NOTE: Please use the previously implemented functions when applicable.
Do not copy paste code from previous parts.
NOTE: Iterate the data matrix by the orders returned by get_order(feature_matrix.shape[0])
Args:
feature_matrix - A numpy matrix describing the given data. Each row
represents a single data point.
labels - A numpy array where the kth element of the array is the
correct classification of the kth row of the feature matrix.
T - An integer indicating how many times the perceptron algorithm
should iterate through the feature matrix.
Returns: A tuple where the first element is a numpy array with the value of
the average theta, the linear classification parameter, found after T
iterations through the feature matrix and the second element is a real
number with the value of the average theta_0, the offset classification
parameter, found after T iterations through the feature matrix.
Hint: It is difficult to keep a running average; however, it is simple to
find a sum and divide.
"""
# Your code here
(n, k) = feature_matrix.shape
theta = np.zeros(k)
theta_total = np.zeros(k)
theta_0 = 0.0
theta_0_total = 0.0
for t in range(T):
for i in get_order(n):
theta, theta_0 = perceptron_single_step_update(feature_matrix[i], labels[i], theta, theta_0)
theta_total += theta
theta_0_total += theta_0
return (theta_total / (n * T), theta_0_total / (n * T))
raise NotImplementedError
def pegasos_single_step_update(
feature_vector,
label,
L,
eta,
current_theta,
current_theta_0):
"""
Properly updates the classification parameter, theta and theta_0, on a
single step of the Pegasos algorithm
Args:
feature_vector - A numpy array describing a single data point.
label - The correct classification of the feature vector.
L - The lamba value being used to update the parameters.
eta - Learning rate to update parameters.
current_theta - The current theta being used by the Pegasos
algorithm before this update.
current_theta_0 - The current theta_0 being used by the
Pegasos algorithm before this update.
Returns: A tuple where the first element is a numpy array with the value of
theta after the current update has completed and the second element is a
real valued number with the value of theta_0 after the current updated has
completed.
"""
tx = np.dot(current_theta, feature_vector)
ytx = label * tx
txtz = tx + current_theta_0
ytxtz = label * txtz
coef = 1-eta*L
if ytxtz <= 1:
current_theta = (coef)*(current_theta) + (eta * label * feature_vector)
current_theta_0 += eta * label
else:
current_theta = (coef)*(current_theta)
return (current_theta, current_theta_0)
raise NotImplementedError
def pegasos(feature_matrix, labels, T, L):
"""
Runs the Pegasos algorithm on a given set of data. Runs T
iterations through the data set, there is no need to worry about
stopping early.
For each update, set learning rate = 1/sqrt(t),
where t is a counter for the number of updates performed so far (between 1
and nT inclusive).
NOTE: Please use the previously implemented functions when applicable.
Do not copy paste code from previous parts.
Args:
feature_matrix - A numpy matrix describing the given data. Each row
represents a single data point.
labels - A numpy array where the kth element of the array is the
correct classification of the kth row of the feature matrix.
T - An integer indicating how many times the algorithm
should iterate through the feature matrix.
L - The lamba value being used to update the Pegasos
algorithm parameters.
Returns: A tuple where the first element is a numpy array with the value of
the theta, the linear classification parameter, found after T
iterations through the feature matrix and the second element is a real
number with the value of the theta_0, the offset classification
parameter, found after T iterations through the feature matrix.
"""
# Your code here
(nsamples, nfeatures) = feature_matrix.shape
theta = np.zeros(nfeatures)
theta_0 = 0
count = 0
for t in range(T):
for i in get_order(nsamples):
count += 1
eta = 1.0 / np.sqrt(count)
(theta, theta_0) = pegasos_single_step_update(
feature_matrix[i], labels[i], L, eta, theta, theta_0)
return (theta, theta_0)
raise NotImplementedError
# # Part II
#
#
# def classify(feature_matrix, theta, theta_0):
# """
# A classification function that uses theta and theta_0 to classify a set of
# data points.
#
# Args:
# feature_matrix - A numpy matrix describing the given data. Each row
# represents a single data point.
# theta - A numpy array describing the linear classifier.
# theta - A numpy array describing the linear classifier.
# theta_0 - A real valued number representing the offset parameter.
#
# Returns: A numpy array of 1s and -1s where the kth element of the array is
# the predicted classification of the kth row of the feature matrix using the
# given theta and theta_0. If a prediction is GREATER THAN zero, it should
# be considered a positive classification.
# """
# # Your code here
# raise NotImplementedError
#
#
# def classifier_accuracy(
# classifier,
# train_feature_matrix,
# val_feature_matrix,
# train_labels,
# val_labels,
# **kwargs):
# """
# Trains a linear classifier and computes accuracy.
# The classifier is trained on the train data. The classifier's
# accuracy on the train and validation data is then returned.
#
# Args:
# classifier - A classifier function that takes arguments
# (feature matrix, labels, **kwargs) and returns (theta, theta_0)
# train_feature_matrix - A numpy matrix describing the training
# data. Each row represents a single data point.
# val_feature_matrix - A numpy matrix describing the validation
# data. Each row represents a single data point.
# train_labels - A numpy array where the kth element of the array
# is the correct classification of the kth row of the training
# feature matrix.
# val_labels - A numpy array where the kth element of the array
# is the correct classification of the kth row of the validation
# feature matrix.
# **kwargs - Additional named arguments to pass to the classifier
# (e.g. T or L)
#
# Returns: A tuple in which the first element is the (scalar) accuracy of the
# trained classifier on the training data and the second element is the
# accuracy of the trained classifier on the validation data.
# """
# # Your code here
# raise NotImplementedError
#
#
def extract_words(input_string):
"""
Helper function for bag_of_words()
Inputs a text string
Returns a list of lowercase words in the string.
Punctuation and digits are separated out into their own words.
"""
for c in punctuation + digits:
input_string = input_string.replace(c, ' ' + c + ' ')
return input_string.lower().split()
def bag_of_words(texts):
"""
Inputs a list of string reviews
Returns a dictionary of unique unigrams occurring over the input
Feel free to change this code as guided by Problem 9
"""
# Your code here
dictionary = {} # maps word to unique index
for text in texts:
word_list = extract_words(text)
for word in word_list:
if word not in dictionary:
dictionary[word] = len(dictionary)
return dictionary
def extract_bow_feature_vectors(reviews, dictionary):
"""
Inputs a list of string reviews
Inputs the dictionary of words as given by bag_of_words
Returns the bag-of-words feature matrix representation of the data.
The returned matrix is of shape (n, m), where n is the number of reviews
and m the total number of entries in the dictionary.
Feel free to change this code as guided by Problem 9
"""
# Your code here
num_reviews = len(reviews)
feature_matrix = np.zeros([num_reviews, len(dictionary)])
for i, text in enumerate(reviews):
word_list = extract_words(text)
for word in word_list:
if word in dictionary:
feature_matrix[i, dictionary[word]] = 1
return feature_matrix
# def accuracy(preds, targets):
# """
# Given length-N vectors containing predicted and target labels,
# returns the percentage and number of correct predictions.
# """
# return (preds == targets).mean()