# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3 (ipykernel)
#     language: python
#     name: python3
# ---

# ---
# title: '曾经的神：Support Vector Machine'
# date: 2021-07-30
# permalink: /posts/2021/07/svmyyds/
# tags:
#   - Machine Learning
# ---
# # Intro
# 最近申请工作的时候被问到了，自己这个菜鸡🐔对国内工作不熟悉加上没有充分准备，感觉回答的不是很好😭，
# 今天，我们就来好好梳理一下什么是SVM，怎么用，原理和trick～
#
# ---

# # Support Vector Machine (Classifier)
# suggest readings:
# - Alpaydin: 10.3, 13.1, 13.2
# - Murphy: 172.16.17.32
# - Geron: chapter 5, appendix C

# ## Alpaydin 阅读笔记
#
# ### [10.3] Geometry of the Linear Discriminant （线性可区分的图像）
# - 从一个简单的 two classes 情况开始解析，在这种情况下，单个的区分方程已经足够：
# - Discriminant between two classes:
# $$
# \begin{equation}\label{Discriminant_between_two_classes}
# \begin{split}
# g(\chi) &= g_1(\chi) - g_2(\chi)\\
#         &= ((w_1)^T\chi + w_{10}) - ((w_2)^T\chi + w_{20})\\
#         &= (w_1 - w_2)^T\chi + (w_{10} - w_{20})\\
#         &= w^T\chi + w_0
# \end{split}
# \end{equation}
# $$
# - we choose
# $$
# \left\{
#         \begin{matrix}
#             C_1,\text{ }g(\chi) > 0\\
#             C_2,\text{ }otherwise
#         \end{matrix}
# \right.
# $$
#
# `weight vector threshold`:
# - defines a hyperplane where $w$ is the weight vector and $w_0$ is the threshold.
#
# ### Decision rule
# - choose $C_1$ if $w^T\chi > -w_0$, and choose $C_2$ otherwise. The hyperplane divides the input space into two half-spaces: decision region $R_1$ for $C_1$ and $R_2$ for $C_2$. Any $\chi$ in $R_1$ is on the `positive` side of the hyperplane and any $\chi$ in $R_2$ is on the `negative` side.
# ![IMG_B352B4820514-1.jpeg](attachment:IMG_B352B4820514-1.jpeg)
#
# ### Decision bounduary equation
# - Let's take 2 points on the decision surface; that is, $g(\chi_1) = g(\chi_2) = 0$, then
#
# $$
# \begin{equation}
# \begin{split}
#     w^T\chi_1 + w_0 &= w^T\chi_2 + w_0\\
#     w^T(\chi_1 - \chi_2) &= 0
# \end{split}
# \end{equation}
# $$
#
# and we see that $w$ is *normal* to any vector lying on the hyperplane. Let's rewrite $\chi$ as
#
# $$
# \begin{equation}
#     \chi = \chi_p + r\frac{w}{||w||}
# \end{equation}
# $$
#
# - $\chi_p$: normal projection of $\chi$ onto the hyperplane
# - $r$: the distance from $\chi$ to the hyperplane
#     - $<0$ if $\chi$ is on the negative side
#     - $>0$ if $\chi$ is on the positive side
#     
# $$
# \begin{equation}
#     r = \frac{g(\chi)}{||w||}
# \end{equation}
# $$
#
# So, at the origin the distance $r_0$ will be
#
# $$
# \begin{equation}
#     r_0 = \frac{w_0}{||w||}
# \end{equation}
# $$
#
# Thus $w_0$ determines the `location` of the hyperplane with respect to the origin, and $w$ determines its `orientation`.

# ![IMG_686E4B07D60D-1.jpeg](attachment:IMG_686E4B07D60D-1.jpeg)

# ### Multiple Classes
#
# When there are K>2 classes, there are K discriminant（可辨别的）funtions. When they are linear, we have
#
# $$
# \begin{equation}
# g_i(\chi|w_i, w_{i0}) = w^{T}_i\chi + w_{i0}
# \end{equation}
# $$

# ![IMG_7F0A959AD62D-1.jpeg](attachment:IMG_7F0A959AD62D-1.jpeg)

# We assume that the parameters, $w_i$, $w_i0$, are computed so as to have
# $$
# g_i(\chi)=
# \left\{
#         \begin{matrix}
#             C_1,\text{ }g(\chi) > 0\\
#             C_2,\text{ }otherwise
#         \end{matrix}
# \right.
# $$
#
# for all $\chi$ in the training set. 
#
# - Using such discriminant functions corresponds to *assuming* that ``all calsses are linearly separable``
#
# - Sometimes not all the points can lies either in (+) or (-) class. The susal approach is to assign $\chi$ to the class having the highest discriminant:
#     - choose $C_i$ if $g_i(\chi) = max^K_{j=1}g_j(\chi)$
#         - <font color=red>linear classifier</font>: recall the $\frac{|g_i(\chi)|}{||w_i||}$ is the ``distance from the input point to the hyperplane``, assuming $w_i$ have similar length, this assigns the point to the class(among all $g_j(\chi) > 0$) to whose hyperplane the point is most distant.
#         - linear classifier cont: it geometrically divides the feature space into K convex decision regions $R_i$ 

# ### [13.1] Kernel Machines
# > *Kernel Machines* are `maximum margin methods` that allow the model to be written as a sum of the influences of a subset of the training instances. These influences are given by application-specific similarity kernels, and we discuss "kernelized" <font color=blue>classification</font>, <font color=orange>regression</font>, <font color=purple>outlier detection</font>, and <font color=red>dimensionality reduction</font>, as well as *how to choose and use kernels*.
#
# ---
#
# - Each learning algorithm has a different `inductive bias`, makes different `assumptions`, and defines a different `objective function` and thus may find a different *linear model*.
# - The model `support vector machine`(SVM) was generalized under the name `kernel machine`
#
#   It is popular because:
# - It never solve a more complex problem as a `first step` before the actual problem(Vapnik 1995)
# - Goal: We only need to find the <font color=red>boundary</font> separating those $\chi$ that have low $p(\chi)$, that is, $\chi$ where $p(x) < \theta$, for some threshold <font color=blue>$\theta \in (0,1)$</font>

# ### Linear Discriminant

# - Generative vs. Discriminative
#     * Generative model
#         - lkj

# ### Support Vector Machine (SVM)

# ### Primal & Dual Unconstrained Optimization



StarcoderdataJupyterScriptsDedupFiltered