31:T7ac,## The max margin can be expressed as: > 1. The distance between point to the hyperplane:

${tex.block` \operatorname{distance}\left(w, b, x_{i}\right)=\frac{\left|w^{T} x+b\right|}{\|w\| } `} > 2. Margin: ${tex.block` \operatorname{margin}(w, b)=\min_{x_{i}} \operatorname{distance}\left(w, b, x_{i}\right)= \\~\\ \min_{x_{i}} \frac{\left|w^{T} x_{i}+b\right|}{\|w\|}, i=1,2, \cdots, N \\~\\ `} > 3. Max margin: ${tex.block` \max _{w, b} \operatorname{margin}(w, b)=\max _{w, b} \min _{x_{i}} \frac{\left|w^{T} x_{i}+b\right|}{\|w\|} \\~\\ =\max _{w, b} \min _{x_{i}} \frac{y_{i}\left(w^{T} x_{i}+b\right)}{\|w\|}, i=1,2, \cdots, N \\~\\ `} > Now, the problem of solving support vector is transferred to solve the problem of optimization with constraints. > ${tex.block` \max_{w, b} \operatorname{margin}(w, b)=\max_{w, b} \min_{x_{i}} \frac{y_{i}\left(w^{T} x_{i}+b\right)}{\|w\|}, i=1,2, \cdots, N \\~\\ \text { s.t. } y_{i}\left(w^{T} x_{i}+b\right)>0, i=1,2, \cdots, N \\~\\ `} > For any hyperplane in the space, we can always find a corresponding (w,b) that satisfies ${tex`wx_i+b=1`} since we can always multiply an arbitrary constant to both w and b without changing the hyperplane it represents. > Therefore, a specific value of ${tex`\gamma`} (in this case ${tex`\gamma=1`} ) doesn't really impose any additional constraint on the candidate hyperplanes in this optimization problem. > ${tex.block` \max _{w, b} \operatorname{margin}(w, b) \\~\\ =\max _{w, b} \min _{x_{i}} \frac{y_{i}\left(w^{T} x_{i}+b\right)}{\|w\|} \\~\\ =\max_{w, b} \frac{1}{\|w\|} \underbrace{\min_{x_i} y_i \left(w^Tx_i+b\right)}_{\gamma = 1} \\~\\ =\max_{w,b} \frac{1}{\|w\|} \\~\\ =\min_{w,b} \frac{1}{2} w^T w \\~\\ i=1,2, \cdots, N\\~\\ \left\{\begin{array}{c} \min _{w, b} \frac{1}{2} w^{T} w \\~\\ \text { s.t. } y_{i}\left(w^{T} x_{i}+b\right) \geq 1, i=1,2, \cdots, N \end{array}\right. \\~\\ `} > This is a convex optimization problem with N constraints.32:T9fc,## Optimization problem > Use the Lagrange multiplier method to construct the Lagrange function (by adding a Lagrange multiplier to each constraint to mix function and all constraints in one new function) > ${tex.block` L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) \\ \lambda=\left(\begin{array}{llll}\lambda_{1} & \lambda_{2} & \cdots & \lambda_{N}\end{array}\right)^{T} \\~\\ \Downarrow \\~\\ \text { when } 1-y_{i}\left(w^{T} x_{i}+b\right)>0 \text { since } \lambda_{i} \geq 0 \Rightarrow \max _{\lambda} L(w, b, \lambda)=\infty \\~\\ \text { when } 1-y_{i}\left(w^{T} x_{i}+b\right) \leq 0 \text { since } \lambda_{i} \geq 0 \Rightarrow \max _{\lambda} L(w, b, \lambda)=\frac{1}{2} w^{T} w \\~\\ \text { Therefore } \min _{w, b} \max _{\lambda} L(w, b, \lambda)=\min _{w, b}\left\{\frac{1}{2} w^{T} w, \infty\right\}=\frac{1}{2} w^{T} w \\~\\ \Downarrow \\~\\ \left\{\begin{array}{l} \min _{w, b} \max _{\lambda} L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) \\~\\ \text { s.t. } \lambda_{i} \geq 0, i=1,2, \cdots, N \end{array}\right. \\~\\ `} > In the duality problem, we always have: ${tex.block` \min \max L \geq \max \min L \\~\\ \therefore \left\{\begin{array}{c} \max _{\lambda} \min _{w, b} L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) \\~\\ \text { s.t. } \lambda_{i} \geq 0, i=1,2, \cdots, N \end{array}\right. \\~\\ `} > **Summarize the process:** > 1. optimization problem **with** constraints ${tex.block` \max_{w, b} \operatorname{margin}(w, b)=\max_{w, b} \min_{x_{i}} \frac{y_{i}\left(w^{T} x_{i}+b\right)}{\|w\|}, i=1,2, \cdots, N \\~\\ \text { s.t. } y_{i}\left(w^{T} x_{i}+b\right)>0, i=1,2, \cdots, N \\~\\ `} > 2. optimization problem **with** constraints ${tex.block` \min _{w, b} \frac{1}{2} w^{T} w \\~\\ \text { s.t. } y_{i}\left(w^{T} x_{i}+b\right) \geq 1, i=1,2, \cdots, N \\~\\ `} > 3. optimization problem **without** constraints ${tex.block` \min _{w, b} \max _{\lambda} L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) \\~\\ \text { s.t. } \lambda_{i} \geq 0, i=1,2, \cdots, N \\~\\ `} > 4. optimization problem **without** constraints ${tex.block` \max _{\lambda} \min _{w, b} L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) \\~\\ \text { s.t. } \lambda_{i} \geq 0, i=1,2, \cdots, N \\~\\ `}33:T8e9,## Model solver > **Derivative of ${tex`b`}** > ${tex.block` \frac{\partial L}{\partial b}=\frac{\partial \sum_{i=1}^{N} \lambda_{i}-\sum_{i=1}^{N} \lambda_{i} y_{i}\left(w^{T} x_{i}+b\right)}{\partial b}=\frac{\partial-\sum_{i=1}^{N} \lambda_{i} y_{i} b}{\partial b}=-\sum_{i=1}^{N} \lambda_{i} y_{i}=0 \\~\\ \Rightarrow \sum_{i=1}^{N} \lambda_{i} y_{i}=0 \\~\\ `} > ${tex.block` \therefore \ L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}-\sum_{i=1}^{N} \lambda_{i} y_{i} w^{T} x_{i}-\underbrace{\sum_{i=1}^{N} \lambda_{i} y_{i} b}_{=0} \\ =\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}-\sum_{i=1}^{N} \lambda_{i} y_{i} w^{T} x_{i} \\ `} > **Derivative of ${tex`w`}** > ${tex.block` \frac{\partial L}{\partial w}=w-\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}=0 \\~\\ \Rightarrow w^* = \sum_{i=1}^{N} \lambda_{i} y_{i} x_{i} \\~\\ `} > **Substitute ${tex`w`} with ${tex`\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}`}** > ${tex.block` \min _{w, b} L(w, b, \lambda)=\frac{1}{2}\left(\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}\right)^{T}\left(\sum_{j=1}^{N} \lambda_{j} y_{j} x_{j}\right)+\sum_{i=1}^{N} \lambda_{i}-\sum_{i=1}^{N} \lambda_{i} y_{i}\left(\sum_{j=1}^{N} \lambda_{j} y_{j} x_{j}\right)^{T} x_{i} \\~\\ =\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}-\sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{j}^{T} x_{i}+\sum_{i=1}^{N} \lambda_{i} \\~\\ =\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}-\sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}+\sum_{i=1}^{N} \lambda_{i} \\~\\ =-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}+\sum_{i=1}^{N} \lambda_{i} `} > **The optimization is:** > ${tex.block` \max _{\lambda}-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}+\sum_{i=1}^{N} \lambda_{i}, i=1,2, \cdots, N \\ \text { s.t. } \lambda_{i} \geq 0, i=1,2, \cdots, N `} > and equivalent to > ${tex.block` \min _{\lambda} \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}-\sum_{i=1}^{N} \lambda_{i}, i=1,2, \cdots, N \\ \text { s.t. } \lambda_{i} \geq 0, i=1,2, \cdots, N \\~\\ `} 34:T556,## Karush–Kuhn–Tucker (KKT) conditions > ${tex.block` \\~\\ \left\{\begin{array}{l} \frac{\partial L}{\partial w}=0, \frac{\partial L}{\partial b}=0 \\~\\ \lambda_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right)=0 \ (\text {complementary slackness}) \\~\\ \lambda_{i} \geq 0 \\~\\ 1-y_{i}\left(w^{T} x_{i}+b\right) \leq 0 \end{array}\right. \\~\\ `} > based on the complementary slackness:
> either ${tex`\lambda_i = 0`} or ${tex`\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right)=0`}.

> That is to say, only support vectors (data points on ${tex`w^{T} x_{i}+b = 1`} or ${tex`w^{T} x_{i}+b = -1`}) have ${tex`\lambda_i \neq 0`}. The ${tex`\lambda_i`} of the other data points are 0. > We already got ${tex`w^{*}`}. To find ${tex`b^{*}`}, for one support vector > ${tex.block` x_k, y_k \Rightarrow \ 1-y_{i}\left(w^{T} x_{i}+b\right) = 0 \\~\\ y_k (w^T x_k + b) = 1 \\~\\ \Rightarrow \ y_k^2 (w^T x_k + b) = y_k \ \text{ where } y_k^2 = 1 \\~\\ b^* = y_k - w^T x_k \\~\\ b^* =y_{k}-\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}^{T} x_{k} `} > **Finally, the hyperplane and discriminant function are:** > ${tex.block` \large w^{*T}x + b^{*} \\~\\ \large f(x) = sign(w^{*T}x + b^{*}) \\~\\ `} > Where > ${tex.block` \large w^* = \sum_{i=1}^{N} \lambda_{i} y_{i} x_{i} \\~\\ \large b^* =y_{k}-\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}^{T} x_{k} `} 35:T41f,> **optimization** > ${tex.block` \\~\\ \min _{w, b} \frac{1}{2} w^{T} w+C \sum_{i=1}^{N} \max \left\{0,1-y_{i}\left(w^{T} x_{i}+b\right)\right\} \\~\\ \text { s.t. } y_{i}\left(w^{T} x_{i}+b\right) \geq 1, i=1,2, \cdots, N \\~\\ `} > C is a hypermeter to control error. In general, low C means less error and large C means high error. Note that it does not mean that low error means we have a good model. It totally depends upon on datasets that how much error dataset consists. There is no thumb of rules that low C will work always or high C or medium C. > (Source: C and Gamma in SVM) > ${tex` \\~\\ \text{let } \xi_{i}=1-y_{i}\left(w^{T} x_{i}+b\right), \quad \xi_{i} \geq 0, \quad i=1,2, \cdots, N \\~\\ `} > The objective function can be transformed to: > ${tex.block` \\~\\ \min _{w, b} \frac{1}{2} w^{T} w+C \sum_{i=1}^{N} \xi_{i} \\~\\ \text { s.t. } y_{i}\left(w^{T} x_{i}+b\right) \geq 1-\xi_{i}, \quad i=1,2, \cdots, N \\~\\ `} 36:[{"id":"647a2968cd872981e1dbaa072ed71c2cf3001324d13ecc40bdd35a4515afd76c99018d93fa8a3415efb7c6db914b0229eca4906afa64165bd83b7f7d36ae1147","href":"https://static.observableusercontent.com/files/647a2968cd872981e1dbaa072ed71c2cf3001324d13ecc40bdd35a4515afd76c99018d93fa8a3415efb7c6db914b0229eca4906afa64165bd83b7f7d36ae1147","name":"svm.png","type":"image/png","lastModified":1649128112237.541,"size":86591},{"id":"6e61ac4e02eb8677b8e1b48b0ad9e49d532716b510248d970719750a5a355dc8166fb082f2fdd1c9d59a1f580946f96bbcb778c2bd03a8056f667fc0e77c78b3","href":"https://static.observableusercontent.com/files/6e61ac4e02eb8677b8e1b48b0ad9e49d532716b510248d970719750a5a355dc8166fb082f2fdd1c9d59a1f580946f96bbcb778c2bd03a8056f667fc0e77c78b3","name":"svm_loss.png","type":"image/png","lastModified":1649210901426.515,"size":29702}] 2f:{"title":"ML | 5 Support Vector Machine","cells":[{"id":0,"value":"# ML | 5 Support Vector Machine\n
","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"> Data:\n>
\n> ${tex.block`\n\\left\\{\\left(x_{i}, y_{i}\\right)\\right\\}_{i=1}^{N}, x_{i} \\in \\mathbb{R}^{p}, y_{i} \\in\\{+1,-1\\} \\\\~\\\\\n`}","pinned":false,"hidden":false,"mode":"md"},{"id":10,"value":"> The main idea of SVM is to find a hyperplane with max margin in the feature space to classify the binary outcome. SVM is a discriminant model. The margin refers to the minimal value of the distance between sample data point to the hyperplane: ${tex`margin(w, b)`}. The sample points on the ${tex`w \\cdot x+b=1`} and ${tex`w \\cdot x+b=-1`} are called support vectors.\n>

","pinned":false,"hidden":false,"mode":"md"},{"id":24,"value":"FileAttachment(\"svm.png\").image()","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"> The hyperplane separates the positive class and negative class points:\n>

\n> ${tex.block`\n\\left.\\begin{array}{l}\ny_{i}=+1, w^{T} x_{i}+b>0 \\\\~\\\\\ny_{i}=-1, w^{T} x_{i}+b<0\n\\end{array}\\right\\} y_{i}\\left(w^{T} x_{i}+b\\right)>0, \\text { for } \\forall i=1,2, \\cdots, N \\\\~\\\\\n`}","pinned":false,"hidden":false,"mode":"md"},{"id":33,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":113,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":175,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":205,"value":"$34","pinned":false,"hidden":false,"mode":"md"},{"id":261,"value":"## Soft Margin SVM\n\n> Our training data are usually not ideally linearly separable. For some data where noise is present, we should allow a little classification error, so we need to make some adjustments to the objective function.
\n> ${tex.block`\n\\min _{w, b} \\frac{1}{2} w^{T} w+l o s s \\\\~\\\\\n`}\n> 1. Use the number of misclassified points as loss:\n> ${tex.block`\n\\text { loss }=\\sum_{i=1}^{N} I\\left\\{y_{i}\\left(w^{T} x_{i}+b\\right)<1\\right\\} \\\\\n`}\n> Obviously the indicator function is discontinuous (0-1 Loss).

\n> 2. use the distance as loss:\n> ${tex.block`\n\\left.\\begin{array}{r}\n\\text { if } y_{i}\\left(w^{T} x_{i}+b\\right) \\geq 1, \\text { loss }=0 \\\\~\\\\\n\\text { if } y_{i}\\left(w^{T} x_{i}+b\\right)<1, \\text { loss }=1-y_{i}\\left(w^{T} x_{i}+b\\right)\n\\end{array}\\right\\} \\text { loss }=\\max \\left\\{0,1-y_{i}\\left(w^{T} x_{i}+b\\right)\\right\\} \\\\~\\\\\n`}\n> This loss function is also called hinge loss.\n> ","pinned":false,"hidden":false,"mode":"md"},{"id":280,"value":"FileAttachment(\"svm_loss.png\").image()","pinned":false,"hidden":false,"mode":"ojs"},{"id":284,"value":"$35","pinned":false,"hidden":false,"mode":"md"}],"files":"$W36","stdlib":"1","titling":"auto"}