{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Digit Recognition with SVM\n","metadata":{}},{"cell_type":"markdown","source":"### Table of contents\n1. [Libraries](#libraries)\n2. [Data preprocessing](#data-prep)\n\n    2.1. [Parsing the raw dataset](#parsing)\n    \n    2.2. [Feature Scaling](#scaling)\n    \n    2.3. [Training-Validation split](#split)\n    \n3. [Maths behind the model](#maths)\n\n    3.1. [Hard Margin SVM](#hard-margin)\n    \n    3.2. [Soft Margin SVM](#soft-margin)\n    \n4. [Training and Evaluation](#traineval)\n\n    4.1. [Training using Linear kernel](#linear)\n    \n    4.2. [Training using RBF kernel](#rbf)\n    \n5. [Submitting a solution](#submit)","metadata":{}},{"cell_type":"markdown","source":"<a id=\"libraries\"></a>\n# 1. Libraries","metadata":{}},{"cell_type":"code","source":"import os\n\nimport numpy as np\nimport pandas as pd\nfrom sklearn.model_selection import train_test_split\nfrom sklearn.svm import SVC\nfrom sklearn.preprocessing import StandardScaler\nfrom sklearn.metrics import classification_report\nfrom scipy import sparse","metadata":{"execution":{"iopub.status.busy":"2023-01-06T20:46:06.186534Z","iopub.execute_input":"2023-01-06T20:46:06.186998Z","iopub.status.idle":"2023-01-06T20:46:07.582706Z","shell.execute_reply.started":"2023-01-06T20:46:06.186904Z","shell.execute_reply":"2023-01-06T20:46:07.581695Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"<a id=\"data-prep\"></a>\n# 2. Data preprocessing","metadata":{}},{"cell_type":"code","source":"for dirname, _, filenames in os.walk('/kaggle/input'):\n    for filename in filenames:\n        print(os.path.join(dirname, filename))","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2023-01-06T14:20:01.357580Z","iopub.execute_input":"2023-01-06T14:20:01.358875Z","iopub.status.idle":"2023-01-06T14:20:01.386295Z","shell.execute_reply.started":"2023-01-06T14:20:01.358801Z","shell.execute_reply":"2023-01-06T14:20:01.384374Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"<a id=\"parsing\"></a>\n## 2.1. Parsing the raw dataset","metadata":{}},{"cell_type":"code","source":"train_df = pd.read_csv(\"/kaggle/input/digit-recognizer/train.csv\")\ntest_df = pd.read_csv(\"/kaggle/input/digit-recognizer/test.csv\")\n\n# For the testing dataset we know that we don't have labels,\n# there is only a feature matrix.\nX_test = test_df.to_numpy()\n\nX = train_df.iloc[:, 1:].to_numpy()\ny = train_df.iloc[:, 0].to_numpy()\n\nprint(\"Training dataset shapes:\")\nprint(\"X.shape\", X.shape)\nprint(\"y.shape\", y.shape)\n\nprint(\"\\nTesting dataset shapes:\")\nprint(\"X_test.shape:\", X_test.shape)","metadata":{"execution":{"iopub.status.busy":"2023-01-06T20:46:07.584322Z","iopub.execute_input":"2023-01-06T20:46:07.585065Z","iopub.status.idle":"2023-01-06T20:46:13.926662Z","shell.execute_reply.started":"2023-01-06T20:46:07.585029Z","shell.execute_reply":"2023-01-06T20:46:13.925322Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"<a id=\"scaling\"></a>\n## 2.2. Feature Scaling\nStandardizing the feature matrix. Basically that means that we subtract the mean and divide by the standard deviation (*for each feature*). Therefore each feature in the dataset has a mean of $0$ and standard deviation of $1$.","metadata":{}},{"cell_type":"code","source":"# Feature Scaling\nscaler = StandardScaler()\nX = scaler.fit_transform(X)\n\n# Making the matrix sparse, since most of the pixels are 0s.\nX = sparse.csr_matrix(X)","metadata":{"execution":{"iopub.status.busy":"2023-01-06T14:20:05.637353Z","iopub.execute_input":"2023-01-06T14:20:05.637872Z","iopub.status.idle":"2023-01-06T14:20:07.752120Z","shell.execute_reply.started":"2023-01-06T14:20:05.637840Z","shell.execute_reply":"2023-01-06T14:20:07.750749Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"<a id=\"split\"></a>\n## 2.3. Training-Validation split\nI am choosing a validation size of $10\\%$ of the whole dataset.","metadata":{}},{"cell_type":"code","source":"X_train, X_valid, y_train, y_valid = train_test_split(X, y, test_size=0.1)\nprint(\"Training samples:\", X_train.shape[0])\nprint(\"Validation samples:\", X_valid.shape[0])","metadata":{"execution":{"iopub.status.busy":"2023-01-06T14:20:07.755368Z","iopub.execute_input":"2023-01-06T14:20:07.756258Z","iopub.status.idle":"2023-01-06T14:20:07.874144Z","shell.execute_reply.started":"2023-01-06T14:20:07.756214Z","shell.execute_reply":"2023-01-06T14:20:07.872960Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"<a id=\"maths\"></a>\n# 3. Maths behind the model\n\nThe idea behind the standard (binary) SVM is to find a decision boundary between two different classes. Then, based on this boundary, we can differentiate them.\n\n<a id=\"hard-margin\"></a>\n## 3.1. Hard Margin SVM\nFirstly, we will look at the more primitive way of solving this problem. It is called the *Hard Margin* SVM. Let's start by defining the *feature matrix* $X \\in \\mathbb{R}^{m \\times n}$, the ground truth vector $\\textbf{y} \\in \\mathbb{R}^{m \\times 1}$ and the weights vector $\\textbf{w} \\in \\mathbb{R}^{n \\times 1}$.\n\nAs we know every hyperplane can be described as the set of points $\\textbf{x}_i \\in \\mathbb{R}^{n}$ that satisfy the equation $\\textbf{w}^{\\intercal}\\textbf{x} - b = 0$, where $\\textbf{w}$ is the normal vector to the hyperplane.\nInstead of using a separate vector for the bias $\\textbf{b}$, we will change the structure of $X$ and $\\textbf{w}$:\n$$ X = concat \\left( X, \\textbf{1} \\right) = concat \\left(\n    \\left[ {\\begin{array}{cc}\n      x_{11} & \\dots & x_{1n}\\\\\n      \\vdots & \\ddots & \\vdots \\\\\n      x_{m1} & \\dots & x_{mn}\\\\\n    \\end{array} } \n    \\right], \n    \\left[\n      \\begin{array}{cc}\n      1 \\\\ \\vdots \\\\ 1\n      \\end{array}\n    \\right]\n  \\right) = \\left[ {\\begin{array}{cc}\n      x_{11} & \\dots & x_{1n} & 1 \\\\\n      \\vdots & \\ddots & \\vdots & \\vdots \\\\\n      x_{m1} & \\dots & x_{mn} & 1 \\\\\n    \\end{array} } \n    \\right]\n$$\n\nand since the shape of $\\textbf{w}$ depends on the dimensions of $X$, $\\textbf{w} \\in \\mathbb{R}^{n + 1 \\times 1} $, it's $n + 1$ because we've added a new column vector to $X$. \n\nAfter the changes above, the hyperplane equation is $\\textbf{w}^\\intercal \\textbf{x} = 0$.\nSimilarly, we can define two other hyperplanes:\n- $\\textbf{w}^\\intercal \\textbf{x} = 1$ - anything on or above this hyperplane is classified as 1\n- $\\textbf{w}^\\intercal \\textbf{x} = -1$ - anything on or above this hyperplane is classified as -1\n\nThe region bounded by these two hyperplanes is called the **margin**. Its size is $\\frac{2}{||\\textbf{w}||}$, where $||\\textbf{w}||$ is the L2 norm of $\\textbf{w}$.\nA great overall explanation and derivation can be found in this [MIT lecture](https://www.youtube.com/watch?v=_PwhiWxHK8o).\n\nAfter we've found out what the margin is, we realize that our objective is to maximize $\\frac{2}{||\\textbf{w}||}$, which is equal to minimizing $||\\textbf{w}||$. To prevent data points from falling into the margin, we add these constraints:\n- $\\textbf{w}^\\intercal \\textbf{x} \\ge 1$, when $y_i = 1$\n- $\\textbf{w}^\\intercal \\textbf{x} \\le -1$, when $y_i = -1$\n\nThese constraints can be merge into one:\n$$ y_i(\\textbf{w}^\\intercal\\textbf{x}_i) \\ge 1 $$\nwhich in matrix-vector form is:\n$$ \\textbf{y}\\left( X\\textbf{w} \\right) \\ge 1 $$\n\nThen, the *Hard Margin* optimization problem can be concisely written as:\n$$ \\min_{\\textbf{w}} \\quad ||\\textbf{w}|| $$\n$$ \\textrm{subject to} \\quad \\textbf{y}\\left( X\\textbf{w} \\right) \\ge 1 $$\n\n<a id=\"soft-margin\"></a>\n## 3.2. Soft Margin SVM\nSince the data in the real world is rarely perfectly linearly separable, the *Hinge Loss function* $hl$ is introduced:\n$$ hl(x) = \\max(0,1 - x) $$\nMaybe the best intuitive explanation that I've found about why we use $hl$ is [this video](https://www.youtube.com/watch?v=IjSfa7Q8ngs).\n\nIf the *Hard Margin* equation is transformed into its *Soft Margin* form (using the *Hinge Loss*), we arrive at this minimization problem:\n$$ \\min_{\\textbf{w}} \\quad \\frac{1}{m}hl\\left(\\textbf{y}\\left( X\\textbf{w} \\right) \\right) + \\lambda||\\textbf{w}||^2 $$\nwhere $\\lambda$ is a positive number that allows us to tune how much we care about maximizing the margin $\\frac{2}{||\\textbf{w}||}$, with respect to minimizing the error $\\frac{1}{m}hl\\left(\\textbf{y}\\left( X\\textbf{w} \\right) \\right)$.","metadata":{}},{"cell_type":"markdown","source":"<a id=\"traineval\"></a>\n# 4. Training and Evaluation","metadata":{}},{"cell_type":"markdown","source":"<a id=\"linear\"></a>\n## 4.1. Training using Linear kernel","metadata":{}},{"cell_type":"markdown","source":"A good rule of thumb is to first assume that the dataset is linearly separable. Making this assumption, we imply that we're going to use the *Linear Kernel*.\nTake a look at the cell below:","metadata":{}},{"cell_type":"code","source":"lin_svm = SVC(C=1.0, kernel=\"linear\")\nlin_svm.fit(X_train, y_train)\n\n# Evaluating based on the validation set\nprint(classification_report(y_valid, lin_svm.predict(X_valid)))","metadata":{"execution":{"iopub.status.busy":"2023-01-06T14:20:07.876007Z","iopub.execute_input":"2023-01-06T14:20:07.876850Z","iopub.status.idle":"2023-01-06T14:20:10.878198Z","shell.execute_reply.started":"2023-01-06T14:20:07.876806Z","shell.execute_reply":"2023-01-06T14:20:10.877037Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"<a id=\"rbf\"></a>\n## 4.2. Training using RBF kernel","metadata":{}},{"cell_type":"markdown","source":"The metrics with the *Linear Kernel* look great! It wouldn't hurt to try with the *RBF Kernel*, though!","metadata":{}},{"cell_type":"code","source":"rbf_svm = SVC(C=1.0, kernel=\"rbf\")\nrbf_svm.fit(X_train, y_train)\n\nprint(classification_report(y_valid, rbf_svm.predict(X_valid)))","metadata":{"execution":{"iopub.status.busy":"2023-01-06T14:20:10.879681Z","iopub.execute_input":"2023-01-06T14:20:10.880036Z","iopub.status.idle":"2023-01-06T14:20:14.413507Z","shell.execute_reply.started":"2023-01-06T14:20:10.880005Z","shell.execute_reply":"2023-01-06T14:20:14.412348Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"<a id=\"submit\"></a>\n# 5. Submitting a solution","metadata":{}},{"cell_type":"code","source":"# Feature scaling and creating a sparse matrix out of X_test.\ntest_scaler = StandardScaler()\nX_test = test_scaler.fit_transform(X_test)\nX_test = sparse.csr_matrix(X_test)\n\n# Making a prediction using the RBF Kernel SVM.\ny_pred = rbf_svm.predict(X_test)\nsubmission_df = pd.DataFrame(y_pred)\n\nexpected_submission_df = pd.read_csv(\"/kaggle/input/digit-recognizer/sample_submission.csv\")\nprint(\"Expected submission format:\")\nprint(expected_submission_df.head())\nprint(f\"Size: {len(expected_submission_df)}\")\n\nsubmission_df['ImageId'] = submission_df.index\nsubmission_df[\"Label\"] = submission_df.iloc[:, 0]\nsubmission_df = submission_df[[\"ImageId\", \"Label\"]]\nsubmission_df['ImageId'] += 1\n\nprint(\"\\nSubmission DataFrame:\")\nprint(submission_df.head())\nprint(f\"Size: {len(submission_df)}\")\n\nsubmission_df.to_csv(\"submission.csv\", index=False)\nprint(\"Submission successfully uploaded!\")","metadata":{"execution":{"iopub.status.busy":"2023-01-06T14:29:14.747340Z","iopub.execute_input":"2023-01-06T14:29:14.747678Z","iopub.status.idle":"2023-01-06T14:29:17.986779Z","shell.execute_reply.started":"2023-01-06T14:29:14.747620Z","shell.execute_reply":"2023-01-06T14:29:17.985632Z"},"trusted":true},"execution_count":null,"outputs":[]}]}