cs229_ps1

a-c-dream 发布于

1. [40 points] Linear Classifiers (logistic regression and GDA)

b

相关公式

用牛顿法实现逻辑回归
$$
h(x)={1 \over {1+e^{-\theta^T*x}}}
$$
雅可比矩阵（一阶导数矩阵）
$$
G={1 \over m}X^T(h(X)-Y)
$$
海森矩阵（二阶导数矩阵）
$$
H = {1 \over m}X^Th(X)(1-h(X))X
$$
思路

首先初始化 $ \theta = 0$,然后使用牛顿法更新$\theta$，直到$||\theta||_1<1e^{-5}$。

更新规则：
$$
\theta_k = \theta_{k-1}-{f’(x) \over f’’(x)}
$$
公式的矩阵形式：
$$
\theta_k=\theta_{k-1}-H^{-1}_kG_k
$$

代码

main函数

比较简单，util.py中已经提供了加载数据集和绘图的函数，直接调用即可。训练和预测和调用sklearn包差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def main(train_path, eval_path, pred_path):
    """Problem 1(b): Logistic regression with Newton's Method.

    Args:
        train_path: Path to CSV file containing dataset for training.
        eval_path: Path to CSV file containing dataset for evaluation.
        pred_path: Path to save predictions.
    """
    x_train, y_train = util.load_dataset(train_path, add_intercept=True)

    # *** START CODE HERE ***
    # theta_0 = np.zeros(x_train.shape()).T
    logistic = LogisticRegression()
    logistic.fit(x_train, y_train)

    util.plot(x_train, y_train, logistic.theta, f'output/p01b_{pred_path[-5]}.png')

    x_eval, y_eval = util.load_dataset(eval_path, add_intercept=True)
    y_hat = logistic.predict(x_eval)
    np.savetxt(pred_path, y_hat, fmt='%d')
    # *** END CODE HERE ***

fit

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
def fit(self, x, y):
    """Run Newton's Method to minimize J(theta) for logistic regression.

    Args:
        x: Training example inputs. Shape (m, n).
        y: Training example labels. Shape (m,).
    """
    # *** START CODE HERE ***
    m, n = x.shape
    self.theta = np.zeros(n)
    while 1:
        theta_old = np.copy(self.theta)

        h_x = 1 / (1 + np.exp(np.dot(-x, self.theta)))
        # print(h_x.shape)
        g = np.dot(x.T, (h_x - y)) / m
        # H = x.T*h_x*(1-h_x)*x/m
        H = (x.T * h_x * (1 - h_x)).dot(x) / m
        self.theta = theta_old - np.linalg.inv(H).dot(g)

        if np.linalg.norm(self.theta - theta_old, ord=1) < self.eps:
            break

    # *** END CODE HERE ***

predict

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def predict(self, x):
       """Make a prediction given new inputs x.

       Args:
           x: Inputs of shape (m, n).

       Returns:
           Outputs of shape (m,).
       """
       # *** START CODE HERE ***
       m, n = x.shape
       y = np.zeros(m)
       h_x = 1 / (1 + np.exp(np.dot(-x, self.theta)))
       y[h_x >= 0.5] = 1
       y[h_x < 0.5] = 0
       return y
       # *** END CODE HERE ***

完整代码

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
import numpy as np
import util

from linear_model import LinearModel


def main(train_path, eval_path, pred_path):
    """Problem 1(b): Logistic regression with Newton's Method.

    Args:
        train_path: Path to CSV file containing dataset for training.
        eval_path: Path to CSV file containing dataset for evaluation.
        pred_path: Path to save predictions.
    """
    x_train, y_train = util.load_dataset(train_path, add_intercept=True)

    # *** START CODE HERE ***
    # theta_0 = np.zeros(x_train.shape()).T
    logistic = LogisticRegression()
    logistic.fit(x_train, y_train)

    util.plot(x_train, y_train, logistic.theta, f'output/p01b_{pred_path[-5]}.png')

    x_eval, y_eval = util.load_dataset(eval_path, add_intercept=True)
    y_hat = logistic.predict(x_eval)
    np.savetxt(pred_path, y_hat, fmt='%d')
    # *** END CODE HERE ***


class LogisticRegression(LinearModel):
    """Logistic regression with Newton's Method as the solver.

    Example usage:
        > clf = LogisticRegression()
        > clf.fit(x_train, y_train)
        > clf.predict(x_eval)
    """

    def fit(self, x, y):
        """Run Newton's Method to minimize J(theta) for logistic regression.

        Args:
            x: Training example inputs. Shape (m, n).
            y: Training example labels. Shape (m,).
        """
        # *** START CODE HERE ***
        m, n = x.shape
        self.theta = np.zeros(n)
        while 1:
            theta_old = np.copy(self.theta)

            h_x = 1 / (1 + np.exp(np.dot(-x, self.theta)))
            # print(h_x.shape)
            g = np.dot(x.T, (h_x - y)) / m
            # H = x.T*h_x*(1-h_x)*x/m
            H = (x.T * h_x * (1 - h_x)).dot(x) / m
            self.theta = theta_old - np.linalg.inv(H).dot(g)

            if np.linalg.norm(self.theta - theta_old, ord=1) < self.eps:
                break

        # *** END CODE HERE ***

    def predict(self, x):
        """Make a prediction given new inputs x.

        Args:
            x: Inputs of shape (m, n).

        Returns:
            Outputs of shape (m,).
        """
        # *** START CODE HERE ***
        m, n = x.shape
        y = np.zeros(m)
        h_x = 1 / (1 + np.exp(np.dot(-x, self.theta)))
        y[h_x >= 0.5] = 1
        y[h_x < 0.5] = 0
        return y
        # *** END CODE HERE ***

e

使用高斯判别分析解决上面的问题

关于$\phi,\mu_0,\mu_1,\Sigma$的求法在pdf中已经给出了

预测时使用的公式
$$
p(y=1|x;$\phi,\mu_0,\mu_1,\Sigma)={1 \over 1+e^{(-(\theta^Tx+\theta_0))}}
$$
其中$\theta$使用在问题c中的结果
$$
\theta_0 = {1\over2}(\mu_0+\mu_1)^T\Sigma^{-1}(\mu_0+\mu_1)-ln({1-\phi \over \phi})
$$

$$
\theta=\Sigma^{-1}(\mu_1-\mu_0)
$$

代码

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
import numpy as np
import util

from linear_model import LinearModel


def main(train_path, eval_path, pred_path):
    """Problem 1(e): Gaussian discriminant analysis (GDA)

    Args:
        train_path: Path to CSV file containing dataset for training.
        eval_path: Path to CSV file containing dataset for evaluation.
        pred_path: Path to save predictions.
    """
    # Load dataset
    x_train, y_train = util.load_dataset(train_path, add_intercept=False)

    # *** START CODE HERE ***
    gda = GDA()
    gda.fit(x_train, y_train)
    util.plot(x_train,y_train,gda.theta,f'output/p01e_{pred_path[-5]}.png')
    x_eval, y_eval = util.load_dataset(eval_path, add_intercept=False)
    y_hat = gda.predict(x_eval)
    np.savetxt(pred_path, y_hat, fmt='%d')

    # *** END CODE HERE ***


class GDA(LinearModel):
    """Gaussian Discriminant Analysis.

    Example usage:
        > clf = GDA()
        > clf.fit(x_train, y_train)
        > clf.predict(x_eval)
    """

    def fit(self, x, y):
        """Fit a GDA model to training set given by x and y.

        Args:
            x: Training example inputs. Shape (m, n).
            y: Training example labels. Shape (m,).

        Returns:
            theta: GDA model parameters.
        """
        # *** START CODE HERE ***
        m, n = x.shape
        self.theta = np.zeros(n + 1)

        y_0 = np.sum(y == 0)
        y_1 = np.sum(y == 1)
        phi = y_1 / m

        mu_0 = np.sum(x[y == 0], axis=0) / y_0
        mu_1 = np.sum(x[y == 1], axis=0) / y_1

        t_0 = (x[y == 0] - mu_0)
        t_1 = (x[y == 1] - mu_1)
        sigma = (t_0.T.dot(t_0)+t_1.T.dot(t_1))/m
        sigma_inv = np.linalg.inv(sigma)
        self.theta[0] = (mu_0 + mu_1).T.dot(sigma_inv).dot(mu_0 - mu_1) / 2 - np.log((1 - phi) / phi)
        self.theta[1:] = sigma_inv.dot(mu_1 - mu_0)
        return self.theta
        # *** END CODE HERE ***

    def predict(self, x):
        """Make a prediction given new inputs x.

        Args:
            x: Inputs of shape (m, n).

        Returns:
            Outputs of shape (m,).
        """
        # *** START CODE HERE ***
        y = 1 / (1 + np.exp(-(np.dot(x,self.theta[1:]) + self.theta[0])))
        y[y >= 0.5] = 1
        y[y < 0.5] = 0
        return y
        # *** END CODE HERE

a-c-dream

a-c-dream

贵在坚持

93
13
0
CATEGORYS
TAGS