|
| 1 | +#################################################################################### |
| 2 | +## PROBLEM1: Gradient Descent |
| 3 | +## Gradient descent is a popular optimization technique to solve many |
| 4 | +## machine learning problems. In this case, we will explore the gradient |
| 5 | +## descent algorithm to fit a line for the given set of 2-D points. |
| 6 | +## ref: https://tinyurl.com/yc4jbjzs |
| 7 | +## ref: https://spin.atomicobject.com/2014/06/24/gradient-descent-linear-regression/ |
| 8 | +## |
| 9 | +## |
| 10 | +## input: directory of faces in ./data/1_points.csv/ |
| 11 | +## function for reading points is provided |
| 12 | +## |
| 13 | +## |
| 14 | +## your task: fill the following functions: |
| 15 | +## evaluate_cost |
| 16 | +## evaluate_gradient |
| 17 | +## udpate_params |
| 18 | +## NOTE: do NOT change values of 'init_params' and 'max_iterations' in optimizer |
| 19 | +## |
| 20 | +## |
| 21 | +## output: cost after convergence (rmse, lower the better) |
| 22 | +## |
| 23 | +## |
| 24 | +## NOTE: all required modules are imported. DO NOT import new modules. |
| 25 | +## NOTE: references are given intline |
| 26 | +## tested on Ubuntu14.04, 22Oct2017, Abhilash Srikantha |
| 27 | +#################################################################################### |
| 28 | + |
| 29 | +import numpy as np |
| 30 | +import matplotlib.pyplot as plt |
| 31 | +import time |
| 32 | + |
| 33 | +def load_data(fname): |
| 34 | + points = np.loadtxt(fname, delimiter=',') |
| 35 | + y_ = points[:,1] |
| 36 | + # append '1' to account for the intercept |
| 37 | + x_ = np.ones([len(y_),2]) |
| 38 | + x_[:,0] = points[:,0] |
| 39 | + # display plot |
| 40 | + #plt.plot(x_[:,0], y_, 'ro') |
| 41 | + #plt.xlabel('x-axis') |
| 42 | + #plt.ylabel('y-axis') |
| 43 | + #plt.show() |
| 44 | + print('data loaded. x:{} y:{}'.format(x_.shape, y_.shape)) |
| 45 | + return x_, y_ |
| 46 | + |
| 47 | +def evaluate_cost(x_,y_,params): |
| 48 | + tempcost = 0 |
| 49 | + for i in range(len(y_)): |
| 50 | + tempcost += (y_[i] - ((params[0] * x_[i,0]) + params[1])) ** 2 |
| 51 | + return tempcost / float(10000) |
| 52 | + |
| 53 | +def evaluate_gradient(x_,y_,params): |
| 54 | + m_gradient = 0 |
| 55 | + b_gradient = 0 |
| 56 | + N = float(len(y_)) |
| 57 | + for i in range(len(y_)): |
| 58 | + m_gradient += -(2/N) * (x_[i,0] * (y_[i] - ((params[0] * x_[i,0]) + params[1]))) |
| 59 | + b_gradient += -(2/N) * (y_[i] - ((params[0] * x_[i,0]) + params[1])) |
| 60 | + return [m_gradient,b_gradient] |
| 61 | + |
| 62 | +def update_params(old_params, grad, alpha): |
| 63 | + new_m = old_params[0] - (alpha * grad[0]) |
| 64 | + new_b = old_params[1] - (alpha * grad[1]) |
| 65 | + return [new_m,new_b] |
| 66 | + |
| 67 | +# initialize the optimizer |
| 68 | +optimizer = {'init_params':np.array([4.5,2.0]) , |
| 69 | + 'max_iterations':10000, |
| 70 | + 'alpha':0.69908, |
| 71 | + 'eps':0.0000001, |
| 72 | + 'inf':1e10} |
| 73 | + |
| 74 | +# load data |
| 75 | +x_, y_ = load_data("./data/1_points.csv") |
| 76 | + |
| 77 | +# time stamp |
| 78 | +start = time.time() |
| 79 | + |
| 80 | +try: |
| 81 | + # gradient descent |
| 82 | + params = optimizer['init_params'] |
| 83 | + old_cost = 1e10 |
| 84 | + for iter_ in range(optimizer['max_iterations']): |
| 85 | + # evaluate cost and gradient |
| 86 | + cost = evaluate_cost(x_,y_,params) |
| 87 | + grad = evaluate_gradient(x_,y_,params) |
| 88 | + # display |
| 89 | + if(iter_ % 10 == 0): |
| 90 | + print('iter: {} cost: {} params: {}'.format(iter_, cost, params)) |
| 91 | + # check convergence |
| 92 | + if(abs(old_cost - cost) < optimizer['eps']): |
| 93 | + break |
| 94 | + # udpate parameters |
| 95 | + params = update_params(params,grad,optimizer['alpha']) |
| 96 | + old_cost = cost |
| 97 | +except: |
| 98 | + cost = optimizer['inf'] |
| 99 | + |
| 100 | +# final output |
| 101 | +print('time elapsed: {}'.format(time.time() - start)) |
| 102 | +print('cost at convergence: {} (lower the better)'.format(cost)) |
0 commit comments