Answers.Body: <p>Based on this repository:</p>
  <p><a href="https://github.com/arkm97/svm-from-scratch/blob/master/SVM_from_scratch.ipynb" rel="nofollow noreferrer">https://github.com/arkm97/svm-from-scratch/blob/master/SVM_from_scratch.ipynb</a></p>
  <p>I will try to reverse engineering that concept:</p>
  <p>So firstly there is issue for <strong>DataCleaning</strong>(removing 0,values, serialize, normalize)</p>
  <p>normalizing dataset (replaced by its difference from the mean)</p>
  <pre><code>credit_df_norm = (credit_df - credit_df.mean())/(credit_df.std())
  </code></pre>
  <p>Divide dataset into Train &amp; Test:</p>
  <pre><code>train_df = credit_df_norm.drop(target, axis=1).loc[:training_points]
  train_target = credit_df_norm[target].replace(0, -1).loc[:training_points]
  </code></pre>
  <p>And here is starting the clue of that algorithms (with maths etc.)</p>
  <blockquote>
  <p>given data points <span class="math-container">$\vec x_j \in \mathbb{R}^{1 \times N}$</span> and targets
  <span class="math-container">$y_j = \pm 1$</span>, where <span class="math-container">$j = 1, \dots, M$</span>, find the maximum-margin
  hyperplane that separates the two classes (<span class="math-container">$y_j = 1$</span> and <span class="math-container">$y_j = -1$</span>).</p>
  <p>Let <span class="math-container">$\vec w$</span> be the vector normal to the hyperplane. We want to find
  <span class="math-container">$\vec w$</span> that satisfies</p>
  <p><span class="math-container">$$ y_j (\vec w \cdot \vec x_j + b) \geq 1 $$</span> The dual formulation of
  the above is equivalent to maximizing the following over the
  multipliers <span class="math-container">$\vec \alpha$</span>:</p>
  <p><span class="math-container">$$ L(\vec \alpha) = \vec y \cdot \vec \alpha  - \frac 1 2  \vec \alpha
  &gt; K \vec \alpha^T$$</span> subject to the constraints <span class="math-container">$\sum_{j=1}^M \alpha_j =
  &gt; 0$</span> and <span class="math-container">$y_j \alpha_j \geq 0$</span>. The matrix <span class="math-container">$K$</span> defines the kernel of the
  SVM; I've chosen <span class="math-container">$K_{jk} = k(\vec x_j, \vec x_k) = \vec x_j \cdot \vec
  &gt; x_k$</span>. The parameters of the plane are recovered from <span class="math-container">$\vec w = \vec
  &gt; \alpha \cdot \vec x$</span> and <span class="math-container">$b = y_j = \vec w \cdot \alpha_j$</span> for <span class="math-container">$j$</span>
  such that <span class="math-container">$\alpha_j \neq 0$</span></p>
  </blockquote>
  <p>Let's divide it to the single factors:</p>
  <p>we need to find <a href="https://www.quora.com/What-is-the-maximum-margin-hyperplane-in-SVM" rel="nofollow noreferrer">maximum-margin-hyperplane</a> for separate into two classes:
  Separation cause SVN is classification - so we need to classify elements into categories.</p>
  <p> = 1</p>
  <p> = −1</p>
  <p>This pattern allow to find hyperplane(?)</p>
  <p>(⃗ ⋅⃗ +)≥1</p>
  <p>The next pattern:</p>
  <p>(⃗ )=⃗ ⋅⃗ −12⃗ &gt;⃗ </p>
  <p>The author for kernel SVN choose those pattern:</p>
  <p>=(⃗ ,⃗ )=⃗ ⋅&gt;⃗ </p>
  <p>And the parameters for plane are here:</p>
  <p>⃗ =&gt;⃗ ⋅⃗  and ==⃗ ⋅ for  such that ≠0</p>
  <p>Reference:
  <a href="https://arxiv.org/pdf/1307.0471.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1307.0471.pdf</a></p>
  <hr />
  <p>In this line are added the kernel</p>
  <p>Popular kernels are:</p>
  <ul>
  <li><p>Polynomial Kernel,</p>
  </li>
  <li><p>Gaussian Kernel,</p>
  </li>
  <li><p>Radial Basis Function (RBF),</p>
  </li>
  <li><p>Laplace RBF Kernel,</p>
  </li>
  <li><p>Sigmoid Kernel,</p>
  </li>
  <li><p>Anove RBF Kernel</p>
  <p>k_value = np.array(train_df @ train_df.T + np.identity(len(train_target))*1e-12)</p>
  </li>
  </ul>
  <p>The structure of k_value (kernel matrix) is an array.</p>
  <p><a href="https://i.sstatic.net/1j4fN.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1j4fN.png" alt="enter image description here" /></a></p>
  <p>Next there is use of <a href="https://www.geeksforgeeks.org/cholesky-decomposition-matrix-decomposition/" rel="nofollow noreferrer">cholesky decomposition—cholesky</a> - which is next complicated concept.</p>
  <pre><code>np.linalg.cholesky(k_value)
  </code></pre>
  <p>Next some bits of data converting:</p>
  <p>alpha = cp.Variable(shape=train_target.shape)</p>
  <p>beta = cp.multiply(alpha, train_target) # to simplify notation</p>
  <pre><code>K = cp.Parameter(shape=k_value.shape, PSD=True, value=k_value)
  
  # objective function
  obj = .5 * cp.quad_form(beta, K) - np.ones(alpha.shape).T @ alpha
  
  # constraints
  const = [np.array(train_target.T) @ alpha == 0,
          -alpha &lt;= np.zeros(alpha.shape),
          alpha &lt;= 10*np.ones(shape=alpha.shape)]
  prob = cp.Problem(cp.Minimize(obj), const)
  </code></pre>
  <p>The next step is recreate the hyperplane:</p>
  <pre><code>w = np.multiply(train_target, alpha.value).T @ train_df
  S = (alpha.value &gt; 1e-4).flatten()
  b = train_target[S] - train_df[S] @ w
  b = b[0]
  # b = np.mean(b)
  </code></pre>
  <p>And finally - the classification and evaluation:</p>
  <pre><code>def classify(x):
      result = w @ x + b
      return np.sign(result)
  
  correct = 0
  incorrect = 0
  validation_set = credit_df_norm.drop(target, axis=1)
  predictions = []
  for i, x in validation_set.iterrows():
      my_svm = classify(x)
      if my_svm==credit_df_norm[target].replace(0, -1)[i]: correct +=1
      else: incorrect +=1
      predictions.append(my_svm)
  predictions = np.array(predictions)
  
  
  print(f&quot;fraction correct: {correct/(correct + incorrect)}&quot;)
  </code></pre>
  <hr />
  <p>That was the more detailed implementation - for shorcut there is an interesting article:</p>
  <p><a href="https://towardsdatascience.com/svm-and-kernel-svm-fed02bef1200" rel="nofollow noreferrer">https://towardsdatascience.com/svm-and-kernel-svm-fed02bef1200</a></p>
  <p>There are existing function from another library - that can be reused in simple manner:</p>
  <pre><code># Fitting SVM to the Training set
  from sklearn.svm import SVC
  classifier = SVC(kernel = 'rbf', C = 0.1, gamma = 0.1)
  classifier.fit(X_train, y_train)
  
  %matplotlib inline
  import numpy as np
  import matplotlib.pyplot as plt
  from scipy import stats
  
  # use seaborn plotting defaults
  import seaborn as sns; sns.set()
  </code></pre>
  <p>Visualized Dataset:
  <a href="https://i.sstatic.net/T2eMH.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/T2eMH.png" alt="enter image description here" /></a></p>
  <p>Dataset after apply hyperplanes:
  <a href="https://i.sstatic.net/WUzFT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WUzFT.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-01T14:11:04.967Z
Answers.LastActivityDate: 2021-05-01T14:11:04.967Z
Answers.UserDisplayName: Piotr Żak
Body: <p>I'm a computer scientist who's studying support vector machines (SVMs) in a machine learning course. I have some understanding of how SVMs are designed, thanks to <a href="https://www.youtube.com/watch?v=_PwhiWxHK8o" rel="nofollow noreferrer">16. Learning: Support Vector Machines - MIT</a>. However, what I'm not understanding is the transition from the optimization problem of the Lagrangian function to its implementation in any programming language. Basically, what I need to understand is how to build, from scratch, the decision function, given a training set. In particular, how do I find Lagrange multipliers in order to know which points are to be considered to define support vectors and the decision function?</p>
  <p>Can anyone explain this to me?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-02-16T05:41:50.740Z
Comments.Text: We're you ever able to answer your question because I have arrived at a similar point?
Comments.UserDisplayName: FeedMeInformation
Tags: <machine-learning><implementation><support-vector-machine>
Title: How to implement SVM algorithm from scratch in a programming language?
UserDisplayName: Marco
ThreadText: # How to implement SVM algorithm from scratch in a programming language?
  
  (Asked by: username_0 on 2019-08-23)
  
  I'm a computer scientist who's studying support vector machines (SVMs) in a machine learning course. I have some understanding of how SVMs are designed, thanks to [16. Learning: Support Vector Machines - MIT](https://www.youtube.com/watch?v=_PwhiWxHK8o). However, what I'm not understanding is the transition from the optimization problem of the Lagrangian function to its implementation in any programming language. Basically, what I need to understand is how to build, from scratch, the decision function, given a training set. In particular, how do I find Lagrange multipliers in order to know which points are to be considered to define support vectors and the decision function?
  
  Can anyone explain this to me?
  
  **Tags:** machine-learning, implementation, support-vector-machine
  > **Comments:**
  > **username_1**: We're you ever able to answer your question because I have arrived at a similar point?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-05-01. Score: 1
  
  Based on this repository:
  https://github.com/arkm97/svm-from-scratch/blob/master/SVM_from_scratch.ipynb
  I will try to reverse engineering that concept:
  So firstly there is issue for DataCleaning(removing 0,values, serialize, normalize)
  normalizing dataset (replaced by its difference from the mean)
  credit_df_norm = (credit_df - credit_df.mean())/(credit_df.std())
  
  Divide dataset into Train & Test:
  train_df = credit_df_norm.drop(target, axis=1).loc[:training_points]
  train_target = credit_df_norm[target].replace(0, -1).loc[:training_points]
  
  And here is starting the clue of that algorithms (with maths etc.)
  
  given data points $\vec x_j \in \mathbb{R}^{1 \times N}$ and targets
  $y_j = \pm 1$, where $j = 1, \dots, M$, find the maximum-margin
  hyperplane that separates the two classes ($y_j = 1$ and $y_j = -1$).
  Let $\vec w$ be the vector normal to the hyperplane. We want to find
  $\vec w$ that satisfies
  $$ y_j (\vec w \cdot \vec x_j + b) \geq 1 $$ The dual formulation of
  the above is equivalent to maximizing the following over the
  multipliers $\vec \alpha$:
  $$ L(\vec \alpha) = \vec y \cdot \vec \alpha  - \frac 1 2  \vec \alpha
  > K \vec \alpha^T$$ subject to the constraints $\sum_{j=1}^M \alpha_j =
  > 0$ and $y_j \alpha_j \geq 0$. The matrix $K$ defines the kernel of the
  SVM; I've chosen $K_{jk} = k(\vec x_j, \vec x_k) = \vec x_j \cdot \vec
  > x_k$. The parameters of the plane are recovered from $\vec w = \vec
  > \alpha \cdot \vec x$ and $b = y_j = \vec w \cdot \alpha_j$ for $j$
  such that $\alpha_j \neq 0$
  
  Let's divide it to the single factors:
  we need to find maximum-margin-hyperplane for separate into two classes:
  Separation cause SVN is classification - so we need to classify elements into categories.
   = 1
   = −1
  This pattern allow to find hyperplane(?)
  (⃗ ⋅⃗ +)≥1
  The next pattern:
  (⃗ )=⃗ ⋅⃗ −12⃗ >⃗ 
  The author for kernel SVN choose those pattern:
  =(⃗ ,⃗ )=⃗ ⋅>⃗ 
  And the parameters for plane are here:
  ⃗ =>⃗ ⋅⃗  and ==⃗ ⋅ for  such that ≠0
  Reference:
  https://arxiv.org/pdf/1307.0471.pdf
  
  In this line are added the kernel
  Popular kernels are:
  
  Polynomial Kernel,
  
  Gaussian Kernel,
  
  Radial Basis Function (RBF),
  
  Laplace RBF Kernel,
  
  Sigmoid Kernel,
  
  Anove RBF Kernel
  k_value = np.array(train_df @ train_df.T + np.identity(len(train_target))*1e-12)
  
  
  The structure of k_value (kernel matrix) is an array.
  
  Next there is use of cholesky decomposition—cholesky - which is next complicated concept.
  np.linalg.cholesky(k_value)
  
  Next some bits of data converting:
  alpha = cp.Variable(shape=train_target.shape)
  beta = cp.multiply(alpha, train_target) # to simplify notation
  K = cp.Parameter(shape=k_value.shape, PSD=True, value=k_value)
  
  # objective function
  obj = .5 * cp.quad_form(beta, K) - np.ones(alpha.shape).T @ alpha
  
  # constraints
  const = [np.array(train_target.T) @ alpha == 0,
          -alpha <= np.zeros(alpha.shape),
          alpha <= 10*np.ones(shape=alpha.shape)]
  prob = cp.Problem(cp.Minimize(obj), const)
  
  The next step is recreate the hyperplane:
  w = np.multiply(train_target, alpha.value).T @ train_df
  S = (alpha.value > 1e-4).flatten()
  b = train_target[S] - train_df[S] @ w
  b = b[0]
  # b = np.mean(b)
  
  And finally - the classification and evaluation:
  def classify(x):
      result = w @ x + b
      return np.sign(result)
  
  correct = 0
  incorrect = 0
  validation_set = credit_df_norm.drop(target, axis=1)
  predictions = []
  for i, x in validation_set.iterrows():
      my_svm = classify(x)
      if my_svm==credit_df_norm[target].replace(0, -1)[i]: correct +=1
      else: incorrect +=1
      predictions.append(my_svm)
  predictions = np.array(predictions)
  
  
  print(f"fraction correct: {correct/(correct + incorrect)}")
  
  
  That was the more detailed implementation - for shorcut there is an interesting article:
  https://towardsdatascience.com/svm-and-kernel-svm-fed02bef1200
  There are existing function from another library - that can be reused in simple manner:
  # Fitting SVM to the Training set
  from sklearn.svm import SVC
  classifier = SVC(kernel = 'rbf', C = 0.1, gamma = 0.1)
  classifier.fit(X_train, y_train)
  
  %matplotlib inline
  import numpy as np
  import matplotlib.pyplot as plt
  from scipy import stats
  
  # use seaborn plotting defaults
  import seaborn as sns; sns.set()
  
  Visualized Dataset:
  
  Dataset after apply hyperplanes:
  
  
  ---
  
  