Homework 3

Main Part

• link

Code

Coursera Q10

from math import exp
import numpy as np

def E_uv(u, v):
    return -2.0

def E_uu(u, v):
    return exp(u) + v * v * exp(u * v) + 2

def E_vv(u, v):
    return 4 * exp(2 * v) + 4

def E_u(u, v):
    return exp(u) + exp(u * v) * v + 2 * u - 2 * v - 3

def E_v(u, v):
    return 2 * exp(2 * v) - 2 * u + 4 * v - 2

def E(u, v):
    return exp(u) + exp(2 * v) + exp(u * v) + u * u - 2 * u * v + 2 * v * v - 3 * u - 2 * v

x = [0, 0]
for _ in range(5):
    print(E(x[0], x[1]))
    u = x[0]
    v = x[1]
    H = np.array([[E_uu(u, v), E_uv(u, v)], [E_uv(u, v), E_vv(u, v)]])
    G = np.array([[E_u(u, v),], [E_v(u, v),]])
    X = np.linalg.inv(H) @ G
    x[0] -= X[0][0]
    x[1] -= X[1][0]

print(E(x[0], x[1]))

Coursera Q13

import random
import numpy as np

N = 1000
T = 1000

def sign(x):
    return 1 if x > 0.0 else -1

def f(x1, x2):
    return sign(x1 ** 2 + x2 ** 2 - 0.6)

def gen_data():
    X = []
    Y = []
    for _ in range(N):
        X.append([1.0, ] + [np.random.uniform(-1.0, 1.0) for i in range(2)])

    for x in X:
        y = f(x[1], x[2])
        Y.append([y if random.random() >= 0.1 else -y, ])

    return np.array(X), np.array(Y)

def calc_ein(X, Y, W):
    P = X @ W
    err = 0
    for y, y_hat in zip(Y, P):
        if sign(y_hat[0]) != y[0]:
            err += 1
    return err / N

def main():
    avg = 0.0
    for t in range(T):
        X, Y = gen_data()
        W = np.linalg.pinv(X) @ Y
        E_in = calc_ein(X, Y, W)
        avg += E_in / T
    print(avg)

if __name__ == '__main__':
    main()

Coursera Q14

import random
import numpy as np

N = 1000
T = 1000

G = [_ for _ in range(5)]

G[0] = np.array([[-1,], [-0.05,], [0.08,], [0.13,], [1.5,], [15.0,]])
G[1] = np.array([[-1,], [-0.05,], [0.08,], [0.13,], [1.5,], [1.5,]])
G[2] = np.array([[-1,], [-1.5,], [0.08,], [0.13,], [0.05,], [1.5,]])
G[3] = np.array([[-1,], [-1.5,], [0.08,], [0.13,], [0.05,], [0.05,]])
G[4] = np.array([[-1,], [-0.05,], [0.08,], [0.13,], [15.0,], [1.5,]])

def sign(x):
    return 1 if x > 0.0 else -1

def f(x1, x2):
    return sign(x1 ** 2 + x2 ** 2 - 0.6)

def gen_data():
    X = []
    Y = []
    for _ in range(N):
        X.append([1.0, ] + [np.random.uniform(-1.0, 1.0) for i in range(2)])

    for x in X:
        y = f(x[1], x[2])
        Y.append([y if random.random() >= 0.1 else -y, ])

    return np.array(X), np.array(Y)

def transform(X):
    Z = []
    for x in X:
        Z.append([1.0, x[1], x[2], x[1] * x[2], x[1] ** 2, x[2] ** 2])
    return np.array(Z)

def calc_ein(Z, Y, W):
    P = Z @ W
    err = 0
    for y, y_hat in zip(Y, P):
        if sign(y_hat[0]) != y[0]:
            err += 1
    return err / N

def main():
    X, Y = gen_data()
    Z = transform(X)
    W = np.linalg.pinv(Z) @ Y
    E_in = calc_ein(Z, Y, W)
    print(E_in)
    for i, g in enumerate(G):
        print(i, calc_ein(Z, Y, g))

if __name__ == '__main__':
    main()

Coursera Q15

import random
import numpy as np

N = 1000
T = 1000

G = [_ for _ in range(5)]

G[0] = np.array([[-1,], [-0.05,], [0.08,], [0.13,], [1.5,], [15.0,]])
G[1] = np.array([[-1,], [-0.05,], [0.08,], [0.13,], [1.5,], [1.5,]])
G[2] = np.array([[-1,], [-1.5,], [0.08,], [0.13,], [0.05,], [1.5,]])
G[3] = np.array([[-1,], [-1.5,], [0.08,], [0.13,], [0.05,], [0.05,]])
G[4] = np.array([[-1,], [-0.05,], [0.08,], [0.13,], [15.0,], [1.5,]])

def sign(x):
    return 1 if x > 0.0 else -1

def f(x1, x2):
    return sign(x1 ** 2 + x2 ** 2 - 0.6)

def gen_data():
    X = []
    Y = []
    for _ in range(N):
        X.append([1.0, ] + [np.random.uniform(-1.0, 1.0) for i in range(2)])

    for x in X:
        y = f(x[1], x[2])
        Y.append([y if random.random() >= 0.1 else -y, ])

    return np.array(X), np.array(Y)

def transform(X):
    Z = []
    for x in X:
        Z.append([1.0, x[1], x[2], x[1] * x[2], x[1] ** 2, x[2] ** 2])
    return np.array(Z)

def calc_err(Z, Y, W):
    P = Z @ W
    err = 0
    for y, y_hat in zip(Y, P):
        if sign(y_hat[0]) != y[0]:
            err += 1
    return err / N

def main():
    avg = 0.0
    for i in range(T):
        X, Y = gen_data()
        Z = transform(X)
        W = np.linalg.pinv(Z) @ Y
        Xtest, Ytest = gen_data()
        Ztest = transform(Xtest)
        avg += calc_err(Ztest, Ytest, W) / T
    print(avg)

if __name__ == '__main__':
    main()

Coursera Q18

import numpy as np

training_data_file_name = "hw3_train.dat"
test_data_file_name = "hw3_test.dat"

eta = 0.001
T = 2000
N = 0
dim = 20

def read_data(fname):
    X = []
    Y = []
    with open(fname, "r") as f:
        for ln in f.readlines():
            ln = ln.split()
            X.append([1.0,] + [ float(x) for x in ln[:-1] ])
            Y.append([int(ln[-1]),])
    global N
    N = len(X)
    return np.array(X), np.array(Y)

def theta(s):
    return 1.0 / (1.0 + np.exp(-s))

def train(X, Y):
    w = np.zeros(dim + 1)
    for _ in range(T):
        grad = np.zeros(dim + 1)
        for x, y in zip(X, Y):
            grad += -1.0 / N * theta(-y * np.dot(w, x)) * (y * x)
        w -= eta * grad
    return w

def calc_err(X, Y, W):
    P = X @ W
    err = 0
    for y, p in zip(Y, P):
        p = theta(p)
        yp = 1 if p > 0.5 else -1
        if yp != y:
            err += 1
    return err / N

def main():
    X, Y = read_data(training_data_file_name)
    W = train(X, Y)
    X, Y = read_data(test_data_file_name)
    E_out = calc_err(X, Y, W)
    print(E_out)

if __name__ == '__main__':
    main()

Coursera Q19

import numpy as np

training_data_file_name = "hw3_train.dat"
test_data_file_name = "hw3_test.dat"

eta = 0.01
T = 2000
N = 0
dim = 20

def read_data(fname):
    X = []
    Y = []
    with open(fname, "r") as f:
        for ln in f.readlines():
            ln = ln.split()
            X.append([1.0,] + [ float(x) for x in ln[:-1] ])
            Y.append([int(ln[-1]),])
    global N
    N = len(X)
    return np.array(X), np.array(Y)

def theta(s):
    return 1.0 / (1.0 + np.exp(-s))

def train(X, Y):
    w = np.zeros(dim + 1)
    for _ in range(T):
        grad = np.zeros(dim + 1)
        for x, y in zip(X, Y):
            grad += -1.0 / N * theta(-y * np.dot(w, x)) * (y * x)
        w -= eta * grad
    return w

def calc_err(X, Y, W):
    P = X @ W
    err = 0
    for y, p in zip(Y, P):
        p = theta(p)
        yp = 1 if p > 0.5 else -1
        if yp != y:
            err += 1
    return err / N

def main():
    X, Y = read_data(training_data_file_name)
    W = train(X, Y)
    Xtest, Ytest = read_data(test_data_file_name)
    E_out = calc_err(Xtest, Ytest, W)
    print(E_out)

if __name__ == '__main__':
    main()

Coursera Q20

import numpy as np

training_data_file_name = "hw3_train.dat"
test_data_file_name = "hw3_test.dat"

eta = 0.001
T = 2000
N = 0
dim = 20

def read_data(fname):
    X = []
    Y = []
    with open(fname, "r") as f:
        for ln in f.readlines():
            ln = ln.split()
            X.append([1.0,] + [ float(x) for x in ln[:-1] ])
            Y.append([int(ln[-1]),])
    global N
    N = len(X)
    return np.array(X), np.array(Y)

def theta(s):
    return 1.0 / (1.0 + np.exp(-s))

def train(X, Y):
    w = np.zeros(dim + 1)
    samples = [n % N for n in range(T)]
    for t, n in enumerate(samples):
        grad = -theta(-Y[n] * np.dot(w, X[n])) * (Y[n] * X[n])
        w -= eta * grad
    return w

def calc_err(X, Y, W):
    P = X @ W
    err = 0
    for y, p in zip(Y, P):
        p = theta(p)
        yp = 1 if p > 0.5 else -1
        if yp != y:
            err += 1
    return err / N

def main():
    X, Y = read_data(training_data_file_name)
    W = train(X, Y)
    Xtest, Ytest = read_data(test_data_file_name)
    E_out = calc_err(Xtest, Ytest, W)
    print(E_out)

if __name__ == '__main__':
    main()

Problem 7

import numpy as np
import matplotlib.pyplot as plt

training_data_file_name = "hw3_train.dat"
test_data_file_name = "hw3_test.dat"

T = 2000
dim = 20

class Problem7:
    def __init__(self):
        self.N = 0
        self.X = None
        self.Y = None
        self.Ntest = 0
        self.Xtest = None
        self.Ytest = None

    @staticmethod
    def read(fname, X, Y):
        with open(fname, "r") as f:
            for ln in f.readlines():
                ln = ln.split()
                X.append([1.0,] + [ float(x) for x in ln[:-1] ])
                Y.append([int(ln[-1]),])

    def read_data(self):
        self.X = []
        self.Y = []
        self.read(training_data_file_name, self.X, self.Y)
        self.N = len(self.X)
        self.X = np.array(self.X)
        self.Y = np.array(self.Y)

        self.Xtest = []
        self.Ytest = []
        self.read(test_data_file_name, self.Xtest, self.Ytest)
        self.Ntest = len(self.Xtest)
        self.Xtest = np.array(self.Xtest)
        self.Ytest = np.array(self.Ytest)

    @staticmethod
    def theta(s):
        return 1.0 / (1.0 + np.exp(-s))

    def calc_err(self, X, Y, W):
        P = X @ W
        err = 0
        for y, p in zip(Y, P):
            p = self.theta(p)
            yp = 1 if p > 0.5 else -1
            if yp != y:
                err += 1
        return err / self.N

    def trainGD(self):
        w = np.zeros(dim + 1)
        record = []
        for _ in range(T):
            grad = np.zeros(dim + 1)
            for x, y in zip(self.X, self.Y):
                grad += -1.0 / self.N * self.theta(-y * np.dot(w, x)) * (y * x)
            w -= 0.01 * grad
            record.append(self.calc_err(self.X, self.Y, w))
        self.GD_Ein = np.array(record)

    def trainSGD(self):
        w = np.zeros(dim + 1)
        record = []
        samples = [n % self.N for n in range(T)]
        for n in samples:
            grad = -self.theta(-self.Y[n] * np.dot(w, self.X[n])) * (self.Y[n] * self.X[n])
            w -= 0.001 * grad
            record.append(self.calc_err(self.X, self.Y, w))
        self.SGD_Ein = np.array(record)

    def plot(self):
        time = np.array([t for t in range(1, T+1)])
        #np.save("t_axis.npy", time)
        #np.save("gd_ein.npy", self.GD_Ein)
        #np.save("sgd_ein.npy", self.SGD_Ein)
        fig, ax = plt.subplots()
        ax.plot(time, self.GD_Ein, label=r"GD  ($\eta=0.01$)", color="steelblue", alpha=0.7, linewidth=2)
        ax.plot(time, self.SGD_Ein, label=r"SGD($\eta=0.001$)", color="skyblue", alpha=0.7, linewidth=2)
        plt.title(r"Comparison of $E_{in}(\mathbf{w}_t): $Gradient Descent(GD) v.s. Stochastic Gradient Descent(SGD)")
        plt.xlabel(r"$t$")
        plt.ylabel(r"$E_{in}(\mathbf{w}_t)$")
        plt.legend()
        plt.show()

def main():
    trainer = Problem7()
    trainer.read_data()
    trainer.trainGD()
    trainer.trainSGD()
    trainer.plot()

if __name__ == '__main__':
    main()

Problem 8

import numpy as np
import matplotlib.pyplot as plt

training_data_file_name = "hw3_train.dat"
test_data_file_name = "hw3_test.dat"

T = 2000
dim = 20

class Problem8:
    def __init__(self):
        self.N = 0
        self.X = None
        self.Y = None
        self.Ntest = 0
        self.Xtest = None
        self.Ytest = None

    @staticmethod
    def read(fname, X, Y):
        with open(fname, "r") as f:
            for ln in f.readlines():
                ln = ln.split()
                X.append([1.0,] + [ float(x) for x in ln[:-1] ])
                Y.append([int(ln[-1]),])

    def read_data(self):
        self.X = []
        self.Y = []
        self.read(training_data_file_name, self.X, self.Y)
        self.N = len(self.X)
        self.X = np.array(self.X)
        self.Y = np.array(self.Y)

        self.Xtest = []
        self.Ytest = []
        self.read(test_data_file_name, self.Xtest, self.Ytest)
        self.Ntest = len(self.Xtest)
        self.Xtest = np.array(self.Xtest)
        self.Ytest = np.array(self.Ytest)

    @staticmethod
    def theta(s):
        return 1.0 / (1.0 + np.exp(-s))

    def calc_err(self, X, Y, W):
        P = X @ W
        err = 0
        for y, p in zip(Y, P):
            p = self.theta(p)
            yp = 1 if p > 0.5 else -1
            if yp != y:
                err += 1
        return err / self.Ntest

    def trainGD(self):
        w = np.zeros(dim + 1)
        record = []
        for _ in range(T):
            grad = np.zeros(dim + 1)
            for x, y in zip(self.X, self.Y):
                grad += -1.0 / self.N * self.theta(-y * np.dot(w, x)) * (y * x)
            w -= 0.01 * grad
            record.append(self.calc_err(self.Xtest, self.Ytest, w))
        self.GD_Eout = np.array(record)

    def trainSGD(self):
        w = np.zeros(dim + 1)
        record = []
        samples = [n % self.N for n in range(T)]
        for n in samples:
            grad = -self.theta(-self.Y[n] * np.dot(w, self.X[n])) * (self.Y[n] * self.X[n])
            w -= 0.001 * grad
            record.append(self.calc_err(self.Xtest, self.Ytest, w))
        self.SGD_Eout = np.array(record)

    def plot(self):
        time = np.array([t for t in range(1, T+1)])
        #np.save("t_axis.npy", time)
        #np.save("gd_eout.npy", self.GD_Eout)
        #np.save("sgd_eout.npy", self.SGD_Eout)
        fig, ax = plt.subplots()
        ax.plot(time, self.GD_Eout, label=r"GD  ($\eta=0.01$)", color="purple", alpha=0.7, linewidth=2)
        ax.plot(time, self.SGD_Eout, label=r"SGD($\eta=0.001$)", color="orchid", alpha=0.7, linewidth=2)
        plt.title(r"Comparison of $E_{out}(\mathbf{w}_t): $Gradient Descent(GD) v.s. Stochastic Gradient Descent(SGD)")
        plt.xlabel(r"$t$")
        plt.ylabel(r"$E_{out}(\mathbf{w}_t)$")
        plt.legend()
        plt.show()

def main():
    trainer = Problem8()
    trainer.read_data()
    trainer.trainGD()
    trainer.trainSGD()
    trainer.plot()

if __name__ == '__main__':
    main()