<jupyter_start><jupyter_text>$$ \LaTeX \text{ command declarations here.}\newcommand{\N}{\mathcal{N}}\newcommand{\R}{\mathbb{R}}\renewcommand{\vec}[1]{\mathbf{1}}\newcommand{\norm}[1]{\|1\|_2}\newcommand{\d}{\mathop{}\!\mathrm{d}}\newcommand{\qed}{\qquad \mathbf{Q.E.D.}}\newcommand{\vx}{\mathbf{x}}\newcommand{\vy}{\mathbf{y}}\newcommand{\vt}{\mathbf{t}}\newcommand{\vb}{\mathbf{b}}\newcommand{\vw}{\mathbf{w}}$$<jupyter_code>%matplotlib inline
from Lec07 import *<jupyter_output><empty_output><jupyter_text>EECS 445: Introduction to Machine Learning Lecture 06:  Logistic Regression * Instructor:  **<NAME>** and **<NAME>*** Date:  September 26, 2016*Lecture Exposition Credit:*  <NAME>, <NAME>  Outline- Concept of Classification- Logistic Regression    - Intuition, Motivation    - Newton's Method     Reading List- Suggested:    - **[MLAPP]**, Chapter 8: Logistic Regression     > In this lecture, we will move from regression to classification.Unlike of predicting some value for data in regression, we predict what category data belongs to in classification. And we will introduce logistic regression. In logistic regression, we will show how to find the optimal coefficients $\vw$ using Newton's method.  Review: Supervised Learning- Goal    - Given data $X$ in feature sapce and the labels $Y$    - Learn to predict $Y$ from $X$- Labels could be discrete or continuous    - Discrete-valued labels:  Classification    - Continuous-valued labels:  Regression        Classification Problem  Classification Problem: Basics- Given an input vector $\vx$, assign it to one of $K$ distinct classes $C_k$, where $k = 1,\dots,K$.- The case $K=2$ is **Binary Classification**    - Label $t=1$ means $x \in C_1$    - Label $t=0$ means $x \in C_2$ (or sometimes $t=-1$)    - **Training:**  Learn a classifier $y(\vx)$ from data,    $$ \text{Training Data} \quad \{ (\vx_1, t_1), \dots, (\vx_N, t_N) \} \implies \text{Classifier} \ y(\vx) $$    - **Prediction:** Predict labels of new data,    $$ \text{New Data} \quad \{ (\vx^{new}_1, t^{new}_1), \dots, (\vx^{new}_m, t^{new}_m) \} \stackrel{h}{\implies} \{ y(\vx^{new}_1), \dots, y(x^{new}_m) \} $$- **Performance Evaluation:** Evaluate learned classifier on test data,    $$ \text{Test Data} \quad \{ (\vx^{test}_1, t^{test}_1), \dots, (\vx^{test}_m, t^{test}_m) \} \stackrel{y}{\implies} \{ y(\vx^{test}_1), \dots, y(\vx^{test}_m) \} \implies \text{Error Estimate} $$    - To estimate **classification error**, we could use e.g. *zero-one loss*:        $$        E = \frac{1}{m} \sum_{j=1}^m \mathbb{1} [ y(\vx^{test}_j) \neq t^{test}_j) ]        $$        i.e. number of misclassified data.  Classification Problems:  Strategies- **Nearest-Neighbors:**  Given query data $\vx$, find closest training points and do a majority vote.- **Discriminant Functions:**  Learn a function $y(\vx)$ mapping $\vx$ to some class $C_k$.- **Probabilistic Model:**  Learn the distributions $P(C_k | \vx)$    - *Discriminative Models* directly model $P(C_k | \vx)$ and learn parameters from the training set.    - *Generative Models* learn class-conditional densities $P(\vx | C_k)$ and priors $P(C_k)$  Logistic Regression> - Logistic Regression is a technique for **classification**!> - We will focus on *binary* classification  Logistic Regression: Preliminary—Logistic Sigmoid Function- The **logistic sigmoid function** is     $$    \sigma(a)    = \frac{1}{1 + \exp(-a)}    = \frac{\exp(a)}{1 + \exp(a)}    $$- Sigmoid function $\sigma(a)$ maps $(-\infty, +\infty) \to (0,1)$    Logistic Regression:  Why use Logistic Sigmoid Function?- Prediction is picking the larger one of $P(y=1 | \vx)$ and $P(y=0 | \vx)$.- This can be implemented by evaluating **log odds**    $$    a = \ln \frac{P(y=1 | \vx)}{P(y=0  | \vx)}    $$    - So the prediction is    $$    y =     \left\{\begin{matrix}    1& a\geq 0\\    0& a< 0    \end{matrix}\right.    $$        - Since $P(y=1 | \vx) + P(y=0  | \vx)=1$, we could solve for    $$    P(y=1 | \vx) = \frac{\exp(a)}{1+\exp(a)} = \sigma(a)    $$     *Logistic Function* appears!   - A heuristic choice for log odds is a separating **hyper plane** $a = \vw^T \phi(\vx)$. So the criterion becomes    $$    \boxed{    y =     \left\{\begin{matrix}    1& \vw^T \phi(\vx)\geq 0, \quad \text{i.e.} \quad \sigma(\vw^T\phi(\vx)\geq 0) \geq 0.5\\    0& \vw^T \phi(\vx)< 0 , \quad \text{i.e.} \quad \sigma(\vw^T\phi(\vx)\geq 0) < 0.5    \end{matrix}\right.}    $$    - In this case, $P(y=1 | \vx) = \sigma(\vw^T \phi(\vx))$ and $P(y=0 | \vx) = 1-\sigma(\vw^T \phi(\vx))$.  Logistic Regression: Underlying Model- We already have    $$    \begin{align}    P(y=1 | \vx, \vw) &= \sigma(\vw^T \phi(\vx)) \\    P(y=0 | \vx, \vw) &= 1-\sigma(\vw^T \phi(\vx))    \end{align}    $$- So we could model **class posterior** using Bernoulli random variable    $$    y | \vx ,\vw \sim \mathrm{Bernoulli}( \sigma(\vw^T \phi(\vx)) )    $$- We can obtain the best paramter $\vw$ by maximizing the likelihood of the training data.(Later)- Logistic regression is simpest discriminative model that is **linear**in the parameters.  Logistic Regression: Example<jupyter_code>plt.figure(figsize=(10,6)); plot_linear_boundary();<jupyter_output><empty_output><jupyter_text>- We could clearly see the linear boundary corresponding to $\vw^T \phi(\vx)$  Logistic Regression:  Likelihood- We saw before that the **likelihood** for each binary label is:    $$    \begin{align}    P(y = 1 | \vx,\vw) &= \sigma(\vw^T \phi(\vx)) \\    P(y = 0 | \vx,\vw) &= 1 - \sigma(\vw^T \phi(\vx))    \end{align}    $$- With a clever trick, this    $$    P(y | x,w) = \sigma(\vw^T \phi(\vx))^y \cdot (1 - \sigma(\vw^T \phi(\vx)))^{1-y}    $$- For a data set $\{(\vx_n, t_n) \}_{n=1}^N$ where $t_n \in \{ 0,1 \}$, the **likelihood function** is    $$    P(\vy = \vt| \mathcal{X}, \vw) = \prod_{n=1}^N P(y=t_n | \vx_n, \vw) =\prod_{n=1}^N \sigma(\vw^T \phi(\vx_n))^{t_n} [1 - \sigma(\vw^T \phi(\vx_n))] ^{1-t_n}    $$    - where $\mathcal{X} = \{\vx_n \}_{n=1}^N$- The optimal $\vw$ can be obtained by maximizing this likelihood.- Maximum likelihood estimate $\vw_{ML}$ makse sense because $\vw_{ML}$ is the coefficient that are most likely to produce $\{t_n \}_{n=1}^N$ given $\mathcal{X}$.- Define **negative log-likelihood** as the **loss**    $$    E(\vw) \triangleq -\ln P(\vy = \vt| \mathcal{X}, \vw)    $$- Maximizing **likelihood** is equivalent to minimizing **loss** $E(\vw)$  Logistic Regression:  Gradient of Loss- Loss function $E(\vw)$ can be transformed:    $$    \begin{align}    E(\vw)     &= -\ln P(\vy = \vt| \mathcal{X}, \vw) \\    &= -\ln \prod \nolimits_{n=1}^N \sigma(\vw^T \phi(\vx_n))^{t_n} [1 - \sigma(\vw^T \phi(\vx_n))] ^{1-t_n} \\    &= -\sum \nolimits_{n=1}^N \left[ t_n \ln \sigma(\vw^T \phi(\vx_n)) + (1-t_n) \ln(1-\sigma(\vw^T \phi(\vx_n))) \right] \\    &= -\sum \nolimits_{n=1}^N \left[ t_n \ln \frac{\exp(\vw^T\phi(\vx_n))}{1+\exp(\vw^T\phi(\vx_n))} + (1-t_n) \ln(\frac{1}{1+\exp(\vw^T\phi(\vx_n))}) \right] \\    &= -\sum \nolimits_{n=1}^N \left[ t_n \ln \frac{1}{1+\exp(-\vw^T\phi(\vx_n))} + (1-t_n) \ln(\frac{1}{1+\exp(\vw^T\phi(\vx_n))}) \right] \\    &= \boxed{\sum \nolimits_{n=1}^N \left[ t_n \ln (1+\exp(-\vw^T\phi(\vx_n))) + (1-t_n) \ln(1+\exp(\vw^T\phi(\vx_n))) \right] }\\    \end{align}    $$ - Gradient of loss $\nabla_\vw E(\vw)$    $$    \begin{align}    \nabla_\vw E(\vw)    &= \nabla_\vw \sum \nolimits_{n=1}^N \left[ t_n \ln (1+\exp(-\vw^T\phi(\vx_n))) + (1-t_n) \ln(1+\exp(\vw^T\phi(\vx_n))) \right] \\    &= \sum \nolimits_{n=1}^N \left[-t_n \frac{\exp(-\vw^T\phi(\vx_n))}{1+\exp(-\vw^T\phi(\vx_n))} \phi(\vx_n)+ (1-t_n) \frac{\exp(\vw^T\phi(\vx_n))}{1+\exp(\vw^T\phi(\vx_n))} \phi(\vx_n) \right] \\    &= \sum \nolimits_{n=1}^N \left[-t_n (1-\sigma(\vw^T\phi(\vx_n)))+ (1-t_n) \sigma(\vw^T\phi(\vx_n)) \right] \phi(\vx_n) \\    &= \sum \nolimits_{n=1}^N \left[\sigma(\vw^T\phi(\vx_n)) - t_n \right] \phi(\vx_n) \\    &= \boxed{ \Phi^T \left( \sigma(\Phi \vw) - \vt \right) }    \end{align}    $$    of which    $$    \Phi = \begin{bmatrix} - & \phi(\vx_1)^T & -\\  & \vdots & \\  - & \phi(\vx_N)^T & - \end{bmatrix}_{N \times M}    \qquad    \sigma(\Phi \vw)=\begin{bmatrix}    \sigma(\vw^T\phi(\vx_1))\\     \vdots\\    \sigma(\vw^T\phi(\vx_N))    \end{bmatrix}_{N \times 1}    \qquad    \vt = \begin{bmatrix}    t_1\\     \vdots\\    t_N    \end{bmatrix}_{N \times 1}    $$       - With the gradient of loss, we could perform *gradient descent* to find $\vw_{ML}$.- But we will use a new method by finding roots of first order derivative! > Remark> - Note that this gradient resembles the gradient in linear regression with least squares (Check Lecture 4)    $$    \begin{align}    \text{Logistic Regression} \quad & \nabla_\vw E(\vw) = \Phi^T \left( \sigma(\Phi \vw) - \vt \right) \\    \text{Linear Regression} \quad & \nabla_\vw E(\vw) = \Phi^T \left( \Phi \vw - \vt \right)    \end{align}    $$  Newton's Method:  Overview- First let's consider one dimension case.- **Goal:** Finding *root* of a general function $f(x)$, i.e. solve for $x$ such that $$f(x)=0$$- **Newton's Method:** Repeat until convergence:    $$    x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}    $$  Newton's Method:  Geometric Intuition- Find the roots of $f(x)$ by following its **tangent lines**. The tangent line of $f(x)$ at $x_n$ has equation    $$    \ell(x) = f(x_n) + (x-x_n) f'(x_n)    $$- Set next iterate $x_{n+1}$ to be **root** of tangent line:    $$    \begin{gather}    f(x_n) + (x-x_n) f'(x_n) = 0 \\    \implies \boxed{ x_{n+1}= x_n - \frac{f(x_n)}{f'(x_n)} }    \end{gather}    $$                Newton's Method: Example<jupyter_code>def fn(x): 
    return (x-2)**3; 
def d1(x): 
    return 3*(x-2)**2; 
newton_example(fn,d1)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.21834465719579987, 'fraction_numerical': 0.014309244389540869, 'mean_word_length': 3.1165254237288136, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '570709', 'license': 'MIT', 'n_tokens_mistral': 3875, 'n_tokens_neox': 3617, 'n_words': 974, 'path': 'lecture06_logistic_regression/lecture06_logistic-regression.ipynb', 'repo_name': 'xipengwang/umich-eecs445-f16', 'size': '9740'}