{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"name":"python","version":"3.10.12","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"kaggle":{"accelerator":"none","dataSources":[{"sourceId":3004,"databundleVersionId":861823,"sourceType":"competition"}],"dockerImageVersionId":30918,"isInternetEnabled":false,"language":"python","sourceType":"notebook","isGpuEnabled":false}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# ML March : Implementing Machine Learning algorithms from scratch\n\n(c) Aritro 'sortira' Shome 2025 - Present\n\n","metadata":{}},{"cell_type":"markdown","source":"## Simple Linear Regression\n\nGiven a line $y = mx + c$ where $m$, $c$ and $x$ are the features and $y$ is the label, our aim is to create a simple linear regressor based on stochastic gradient descent algorithm to learn the slope and the intercept, i.e., $m$ and $c$ respectively. \n\n\nHere we use the stochastic gradient descent algorithm, which computes the error function based on the current parameters of the model, and then differentiates the error function wrt to the parameter, multiplies the differentiated result with the learning rate and subtracts it from the current parameter value (refer to the physical notebook)\n\nSince the error function is a a squared function, we know there is one global minima only.\n\n\n$J(\\theta) = \\frac{1}{2} \\sum_{i=1}^{n} \\left( h_{\\theta}(x_i) - y_i \\right)^2$ is the error function where $h_{\\theta}(x)$ is the function whose parameters (here $m$ and $c$) we are trying to estimate. \n\nthe learning update rule is $\\theta_j := \\theta_j - \\alpha \\sum_{i=1}^{n} \\left( h_{\\theta}(x^{(i)}) - y^{(i)} \\right) x_j^{(i)}$\n\nwhere $\\sum_{i=1}^{n} \\left( h_{\\theta}(x^{(i)}) - y^{(i)} \\right) x_j^{(i)}$ is the differentiation of $J(\\theta)$ with respect to $\\theta_j$\n\nhere $n$ is the number of parameters, for SLR it is 2. ","metadata":{}},{"cell_type":"code","source":"import numpy as np # this provides all the nice utilities to work with, although simple linear regressor may not need it\n\"\"\"\n    Simple Linear regressor\n    x_train: a numpy array consisting of (2,) shaped numpy arrays each of which denote a single input (x,1)\n    y_train: a python list of same length as x_train containing the corresponding output values \n    learning_rate: hyperparameter for adjusting how fast/slow the parameters are to be changed by stochastic gradient descent\n    epochs: the number of times the model will train over the dataset \n\"\"\"\ndef simple_linear_regressor(x_train, y_train, learning_rate=0.01, epochs=50):\n    if len(x_train) != len(y_train):\n        print('ERROR: Training vectors or Testing vectors differ in length.')\n        return None\n    params = np.zeros(2, dtype='f') # initially we assume m and c to be 0 hence our parameters array is a 1 x 2 row vector (0,0)\n    length = len(x_train)\n    # here the idea is that let our parameters be a row vector [m c] and the input be a column vector[x 1]\n    # multiplying these two we get the value mx + c\n    for epoch in range(0, epochs):\n        for i in range(0, length):\n            input_val = x_train[i]\n            output = np.dot(params, input_val) - y_train[i] # scalar value\n            params = params - (learning_rate * output) * np.transpose(input_val) # here we have to take transpose because input_val is column vector but params is row vector\n    return params\n    ","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T13:25:56.567812Z","iopub.execute_input":"2025-03-13T13:25:56.568202Z","iopub.status.idle":"2025-03-13T13:25:56.576327Z","shell.execute_reply.started":"2025-03-13T13:25:56.568167Z","shell.execute_reply":"2025-03-13T13:25:56.575341Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import numpy as np\nimport matplotlib.pyplot as plt\n\n# Define parameters\nm = 2.50\nc = 67.23\n\n# Generate training data\nx_train_list = []\ny_train = []\nfor x in range(10000):\n    curr = np.array([x / 1000, 1]).transpose()  # x2 = 1 for intercept term\n    x_train_list.append(curr)\n    y_train.append(m * (x / 1000) + c)\n\n# Convert to NumPy arrays\nx_train = np.array(x_train_list, dtype=np.float32)\ny_train = np.array(y_train)\n\n# Train simple linear regression \nparams = simple_linear_regressor(x_train, y_train, learning_rate=0.01, epochs=50)\n\n# Extract predicted slope & intercept\npred_m, pred_c = params[0], params[1]\n\nprint(f'Actual slope = {m}, Actual intercept = {c}')\nprint(f'Predicted slope = {pred_m}, Predicted intercept = {pred_c}')\n\n# ---- Visualization ----\nplt.figure(figsize=(8, 6))\n\n# Scatter plot of training data\nplt.scatter(x_train[:, 0], y_train, color='blue', alpha=0.3, label=\"Training Data\")\n\n# Actual regression line (ground truth)\nx_vals = np.linspace(0, 10, 100)  # Covering full x-range\ny_actual = m * x_vals + c\nplt.plot(x_vals, y_actual, color='green', linestyle='--', label=\"Actual Line (Ground Truth)\")\n\n# Predicted regression line\ny_pred = pred_m * x_vals + pred_c\nplt.plot(x_vals, y_pred, color='red', label=\"Predicted Line (Model)\")\n\n# Labels, legend, and title\nplt.xlabel(\"X\")\nplt.ylabel(\"Y\")\nplt.title(\"Simple Linear Regression - Actual vs Predicted\")\nplt.legend()\nplt.grid(True)\n\nplt.show()\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T14:08:07.972511Z","iopub.execute_input":"2025-03-13T14:08:07.972900Z","iopub.status.idle":"2025-03-13T14:08:11.043944Z","shell.execute_reply.started":"2025-03-13T14:08:07.972854Z","shell.execute_reply":"2025-03-13T14:08:11.042859Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## Multiple Linear Regression\n\nSame concept, except we have $n$ independent variables this time.\n$y = m_0 + m_1x_1 + m_2x_2 + m_3x_3 + \\dots + m_nx_n$\n","metadata":{}},{"cell_type":"code","source":"import numpy as np # this provides all the nice utilities to work with\n\"\"\"\n    Multiple Linear Regressor\n    x_train: a numpy array consisting of (n + 1,) shaped numpy arrays each of which denote a single input (x1, x2, .., xn, 1)\n    y_train: a python list of same length as x_train containing the corresponding output values \n    learning_rate: hyperparameter for adjusting how fast/slow the parameters are to be changed by stochastic gradient descent\n    epochs: the number of times the model will train over the dataset \n\"\"\"\ndef multiple_linear_regressor(x_train, y_train, learning_rate=0.01, epochs=50):\n    if len(x_train) != len(y_train):\n        print('ERROR: Training vectors or Testing vectors differ in length.')\n        return None\n    length, features = x_train.shape\n    params = np.zeros(features, dtype='f') # initially we assume all values of parameters to be 0 \n    # here the idea is that let our parameters be a row vector [m1 m2 m3 ....] and the input be a column vector[x1 x2 ...... ]\n    # multiplying these two we get the value m1x1 + m2x2 + m3x3 + ... + mnxn + mn+1xn+1 where xn+1 = 1 for all other values\n    for epoch in range(0, epochs):\n        for i in range(0, length):\n            input_val = x_train[i]\n            output = np.dot(params, input_val) - y_train[i] # scalar value\n            params = params - (learning_rate * output) * np.transpose(input_val) # here we have to take transpose because input_val is column vector but params is row vector\n    return params\n    ","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T13:26:00.353464Z","iopub.execute_input":"2025-03-13T13:26:00.353857Z","iopub.status.idle":"2025-03-13T13:26:00.360641Z","shell.execute_reply.started":"2025-03-13T13:26:00.353817Z","shell.execute_reply":"2025-03-13T13:26:00.359457Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import numpy as np\nimport matplotlib.pyplot as plt\n\n# Define parameters\nn = 5\nm1, m2, m3, m4, m5 = 1.34, 6.90, 42.01, 123.54, 567.99  # Includes intercept\n\n# Generate training data\nx_train_list = []\ny_train = []\nfor i in range(1000):\n    curr = np.array([np.random.rand(), np.random.rand(), np.random.rand(), np.random.rand(), 1])  # Last term = intercept\n    x_train_list.append(curr)\n    y_train.append(m1 * curr[0] + m2 * curr[1] + m3 * curr[2] + m4 * curr[3] + m5 * curr[4])\n\n# Train multiple linear regression (assumed to be defined)\nparams = multiple_linear_regressor(x_train=np.array(x_train_list, dtype=np.float32), y_train=y_train, learning_rate=0.01, epochs=50)\n\nprint(f'Actual slopes = {m1, m2, m3, m4, m5}')\nprint(f'Predicted slopes = {params}')\n\n# Convert to NumPy arrays for visualization\nx_train = np.array(x_train_list)\ny_train = np.array(y_train)\n\n# ---- Visualization ----\nfig, axes = plt.subplots(1, 5, figsize=(18, 4))  # One subplot per feature\n\nfeature_names = [\"X1\", \"X2\", \"X3\", \"X4\", \"Intercept\"]\n\nfor i in range(4):  # Only plot X1 to X4 (ignore intercept)\n    axes[i].scatter(x_train[:, i], y_train, color='blue', alpha=0.5, label=f'Feature {i+1}')\n    axes[i].set_xlabel(feature_names[i])\n    axes[i].set_ylabel(\"Target (Y)\")\n    axes[i].set_title(f\"{feature_names[i]} vs. Y\")\n    axes[i].grid(True)\n\n# ---- Predicted vs. Actual ----\nax = axes[4]  # Last subplot for predictions\ny_pred = x_train @ params  # Compute predicted y\nax.scatter(y_train, y_pred, color='red', alpha=0.5, label=\"Predicted vs Actual\")\nax.plot([min(y_train), max(y_train)], [min(y_train), max(y_train)], 'k--', label=\"Perfect Fit\")  # Diagonal reference line\nax.set_xlabel(\"Actual Y\")\nax.set_ylabel(\"Predicted Y\")\nax.set_title(\"Predicted vs. Actual\")\nax.legend()\nax.grid(True)\n\nplt.tight_layout()\nplt.show()\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T14:07:03.366041Z","iopub.execute_input":"2025-03-13T14:07:03.366365Z","iopub.status.idle":"2025-03-13T14:07:04.775597Z","shell.execute_reply.started":"2025-03-13T14:07:03.366341Z","shell.execute_reply":"2025-03-13T14:07:04.774489Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## Logistic Regression  \n\nGiven a logistic model, we define the hypothesis function using the **sigmoid function**:  \n\n$h_{\\theta}(x) = \\frac{1}{1 + e^{-\\theta^T x}}$  \n\nwhere $\\theta$ is the parameter vector and $x$ represents the feature vector. The sigmoid function ensures that the output is always in the range $(0,1)$, making it suitable for binary classification.  \n\n### Maximum Likelihood Estimation  \n\nIn logistic regression, we use the **likelihood function** to estimate the parameters:  \n\n$L(\\theta) = \\prod_{i=1}^{m} \\left( h_{\\theta}(x^{(i)}) \\right)^{y^{(i)}} \\left(1 - h_{\\theta}(x^{(i)}) \\right)^{1 - y^{(i)}}$  \n\nSince the likelihood function involves a product, taking the logarithm simplifies computation, leading to the **log-likelihood function**:  \n\n$\\ell(\\theta) = \\sum_{i=1}^{m} \\left[ y^{(i)} \\log h_{\\theta}(x^{(i)}) + (1 - y^{(i)}) \\log (1 - h_{\\theta}(x^{(i)})) \\right]$  \n\n### Error Function (Cost Function)  \n\nSince we maximize the log-likelihood, it is equivalent to minimizing the negative log-likelihood, which gives the **logistic regression cost function**:  \n\n$J(\\theta) = -\\frac{1}{m} \\sum_{i=1}^{m} \\left[ y^{(i)} \\log h_{\\theta}(x^{(i)}) + (1 - y^{(i)}) \\log (1 - h_{\\theta}(x^{(i)})) \\right]$  \n\n### Gradient Descent Update Rule  \n\nTo minimize $J(\\theta)$, we take its derivative with respect to $\\theta_j$:  \n\n$\\frac{\\partial J(\\theta)}{\\partial \\theta_j} = \\sum_{i=1}^{m} \\left( h_{\\theta}(x^{(i)}) - y^{(i)} \\right) x_j^{(i)}$  \n\nThe parameter update rule using **stochastic gradient descent (SGD)** is:  \n\n$\\theta_j := \\theta_j - \\alpha \\sum_{i=1}^{m} \\left( h_{\\theta}(x^{(i)}) - y^{(i)} \\right) x_j^{(i)}$  \n\nwhere $\\alpha$ is the learning rate.  \n\nSince logistic regression is a convex function, it has a single global minimum, ensuring convergence to the optimal parameters.\n","metadata":{}},{"cell_type":"code","source":"import numpy as np\n\ndef sigmoid(theta, x):\n    theta = np.asarray(theta)\n    x = np.asarray(x)\n    dot_product = np.dot(theta, x)\n    if np.isscalar(dot_product) or dot_product.shape == ():\n        return 1 / (1 + np.exp(-dot_product))\n    else:\n        raise ValueError(\"ERROR: dimensions are not multiplying\")\n\ndef logistic_regressor(x_train, y_train, learning_rate=0.01, epochs=50):\n    samples, features = x_train.shape\n    if samples != len(y_train):\n        print('ERROR: Training vectors differ in length.')\n        return None\n    theta = np.zeros(features, dtype=np.float32)\n    for epoch in range(0, epochs):\n        for i in range(0, samples):\n            output = sigmoid(theta, x_train[i]) - y_train[i]\n            theta = theta - (learning_rate * output) * x_train[i].transpose()\n    return theta","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T15:37:48.977981Z","iopub.execute_input":"2025-03-13T15:37:48.978495Z","iopub.status.idle":"2025-03-13T15:37:48.988120Z","shell.execute_reply.started":"2025-03-13T15:37:48.978445Z","shell.execute_reply":"2025-03-13T15:37:48.987024Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import numpy as np\nimport matplotlib.pyplot as plt\n\n# Generate training data\nx_train_list = []\ny_train = []\nfor i in range(0, 1000):\n    curr = np.array([np.random.rand(), np.random.rand()])\n    x_train_list.append(curr)\n    if curr[0] - curr[1] > 0:  # If below line x = y\n        y_train.append(1)\n    else:  # If above line x = y\n        y_train.append(0)\n\nx_train = np.array(x_train_list, dtype=np.float32)\n\n# Testing logistic regression (assumed to be defined)\ntheta = logistic_regressor(x_train, y_train, learning_rate=0.01, epochs=50)\n\n# Example test points\ntest_points = np.array([[1, 2], [-1, -3]])\ntest_predictions = [sigmoid(theta, point) for point in test_points]\n\nprint('Class 0 means above line x = y, Class 1 means below line x = y')\nfor i, point in enumerate(test_points):\n    print(f'Point: {point} Predicted Probability: {test_predictions[i]}')\n\n# Visualization\nplt.figure(figsize=(6, 6))\n\n# Convert lists to NumPy arrays\nx_train = np.array(x_train_list)\ny_train = np.array(y_train)\n\n# Plot training data\nplt.scatter(x_train[y_train == 0, 0], x_train[y_train == 0, 1], color='blue', label='Class 0 (Above x=y)', alpha=0.6)\nplt.scatter(x_train[y_train == 1, 0], x_train[y_train == 1, 1], color='red', label='Class 1 (Below x=y)', alpha=0.6)\n\n# Plot decision boundary (x = y)\nx_vals = np.linspace(-5, 5, 100)\nplt.plot(x_vals, x_vals, color='black', linestyle='--', label='Decision Boundary (x=y)')\n\n# Plot test points\nplt.scatter(test_points[:, 0], test_points[:, 1], color='black', marker='x', s=100, label='Test Points')\n\n# Labels and legend\nplt.xlabel(\"X1\")\nplt.ylabel(\"X2\")\nplt.title(\"Classification and Decision Boundary\")\nplt.legend()\nplt.show()\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T14:05:29.457354Z","iopub.execute_input":"2025-03-13T14:05:29.457671Z","iopub.status.idle":"2025-03-13T14:05:30.172935Z","shell.execute_reply.started":"2025-03-13T14:05:29.457646Z","shell.execute_reply":"2025-03-13T14:05:30.171817Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"x_t = np.array([[0,0], [0,1], [1,0], [1,1]])\ny_t = [0, 0, 0, 1]\ntheta = logistic_regressor(x_t, y_t)\nsigmoid(theta, [1, 1])\n\n# looks like this can't do AND gate : hw why?","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T15:39:47.680946Z","iopub.execute_input":"2025-03-13T15:39:47.681239Z","iopub.status.idle":"2025-03-13T15:39:47.691021Z","shell.execute_reply.started":"2025-03-13T15:39:47.681217Z","shell.execute_reply":"2025-03-13T15:39:47.690170Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## Polynomial Regression\n\nPolynomial regression is an extension of simple linear regression where instead of fitting a straight line, we fit a polynomial curve of degree $d$. The hypothesis function for polynomial regression is given by:\n\n$\nh_{\\theta}(x) = \\theta_0 + \\theta_1 x + \\theta_2 x^2 + \\theta_3 x^3 + ... + \\theta_d x^d\n$\nwhere $\\theta_0, \\theta_1, ..., \\theta_d$ are the parameters of the model, and $x$ is the input feature.\n\nThe goal is to find the best values for $\\theta$ such that the error function is minimized.\n\n### Cost Function\n\nThe error function (also known as the loss function) is the sum of squared differences between the predicted and actual values:\n\n$\nJ(\\theta) = \\frac{1}{2} \\sum_{i=1}^{m} \\left( h_{\\theta}(x^{(i)}) - y^{(i)} \\right)^2\n$\n\nwhere $m$ is the number of training samples, $h_{\\theta}(x)$ is the predicted value, and $y$ is the actual value.\n\n### Gradient Descent Update Rule\n\nTo minimize $J(\\theta)$, we use gradient descent. The update rule for each parameter $\\theta_j$ is:\n\n$\n\\theta_j := \\theta_j - \\alpha \\sum_{i=1}^{m} \\left( h_{\\theta}(x^{(i)}) - y^{(i)} \\right) x_j^{(i)}\n$\nwhere $\\alpha$ is the learning rate.\n\n### Feature Transformation\n\nTo perform polynomial regression using linear regression techniques, we transform the input features into polynomial features:\n\n$\nX_{\\text{poly}} =\n\\begin{bmatrix}\n1 & x_1 & x_1^2 & x_1^3 & ... & x_1^d \\\\\n1 & x_2 & x_2^2 & x_2^3 & ... & x_2^d \\\\\n\\vdots & \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n1 & x_m & x_m^2 & x_m^3 & ... & x_m^d\n\\end{bmatrix}\n$\n\nwhere each row represents a training sample transformed into polynomial features.","metadata":{}},{"cell_type":"code","source":"import numpy as np\n\n\ndef polynomial_regressor(x_train, y_train, degree=2, learning_rate=0.01, epochs=50):\n    \n    if len(x_train) != len(y_train):\n        print(\"ERROR: Training vectors differ in length.\")\n        return None\n    \n    length = len(x_train)\n    params = np.zeros(degree + 1, dtype='f')\n\n    for epoch in range(epochs):\n        for i in range(length):\n            curr_list = []\n            for j in range(0, degree + 1):\n                curr_list.append(pow(x_train[i], j))\n            input_val = np.array(curr_list, dtype=np.float32)\n            output = np.dot(params, input_val) - y_train[i]  # Scalar value\n            params -= learning_rate * output * input_val  # Updating parameters\n\n    return params\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T13:26:01.216464Z","iopub.execute_input":"2025-03-13T13:26:01.216881Z","iopub.status.idle":"2025-03-13T13:26:01.225471Z","shell.execute_reply.started":"2025-03-13T13:26:01.216834Z","shell.execute_reply":"2025-03-13T13:26:01.224060Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import numpy as np\ntrue_coeffs = np.array([5, -3, 7, -10, 4, -2, 8, -6]) # power 0 to 7\ny_train = []\nx_train = np.random.uniform(-1, 1, 1000).tolist()  # Wider range (-1 to 1)\n\nfor x in x_train:\n    val = sum(true_coeffs[j] * (x ** j) for j in range(8))  # Compute polynomial value\n    y_train.append(val)\nparams = polynomial_regressor(x_train, y_train, degree=7, learning_rate=0.001, epochs = 1000)\nparams","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T13:26:01.228580Z","iopub.execute_input":"2025-03-13T13:26:01.228917Z","iopub.status.idle":"2025-03-13T13:26:09.116862Z","shell.execute_reply.started":"2025-03-13T13:26:01.228859Z","shell.execute_reply":"2025-03-13T13:26:09.115843Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## KNN : K-nearest neighbours algorithm\n\nUnlike other algorithms, this doesn't have a training phase. Given a set of points, each of which have been assigned to a certain category, we compute the $k$ closest points to the input point. Of those $k$ points we see which category has the majority of points in this set of $k$ points and assign the input point the same category.","metadata":{}},{"cell_type":"code","source":"import numpy as np\ndef knn(x, y, x_input, k=5):\n    distmap = []\n    if k > len(x):\n        print('ERROR: k is larger than number of samples')\n        return None\n    for i in range(0, len(x)):\n        distmap.append({'index': i, 'dist': np.linalg.norm(x[i] - x_input), 'class': y[i]})\n    def key(obj):\n        return obj['dist']\n    distmap.sort(key=key)\n    top_k = distmap[:k]\n    voting = {}\n    for candidate in top_k:\n        voting[candidate['class']] = voting.get(candidate['class'], 0) + 1\n    max_cat = 0\n    maxx = -1\n    for category, votes in voting.items():\n        if votes > maxx:\n            maxx = votes\n            max_cat = category\n    return max_cat","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T13:48:04.418713Z","iopub.execute_input":"2025-03-13T13:48:04.419084Z","iopub.status.idle":"2025-03-13T13:48:04.425860Z","shell.execute_reply.started":"2025-03-13T13:48:04.419055Z","shell.execute_reply":"2025-03-13T13:48:04.424755Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import numpy as np\nimport matplotlib.pyplot as plt\n\n# Generating synthetic data for 3 distinct clusters\nnp.random.seed(42)  # Answer to life, universe, everything\n\nnum_points = 100\n\n# Cluster 1 (Class 0)\ncluster_1 = np.random.randn(num_points, 2) * 1.5 + np.array([0, 0])\nlabels_1 = np.zeros(num_points, dtype=int)\n\n# Cluster 2 (Class 1)\ncluster_2 = np.random.randn(num_points, 2) * 1.5 + np.array([10, 10])\nlabels_2 = np.ones(num_points, dtype=int)\n\n# Cluster 3 (Class 2)\ncluster_3 = np.random.randn(num_points, 2) * 1.5 + np.array([20, 20])\nlabels_3 = np.full(num_points, 2, dtype=int)\n\n# Combining all clusters\nx_data = np.vstack((cluster_1, cluster_2, cluster_3))\ny_labels = np.concatenate((labels_1, labels_2, labels_3))\n\n# Test points\ntest_points = np.array([\n    [-1, -1],   # Near cluster 1, should be class 0\n    [11, 11],   # Near cluster 2, should be class 1\n    [21, 21],   # Near cluster 3, should be class 2\n])\n\nk = 5\npredictions = [knn(x_data, y_labels, point, k) for point in test_points]\n\nfor i, test_point in enumerate(test_points):\n    print(f\"Test Point {test_point} → Predicted Class: {predictions[i]}\")\n\nplt.figure(figsize=(8, 6))\nplt.scatter(cluster_1[:, 0], cluster_1[:, 1], c='red', label='Class 0')\nplt.scatter(cluster_2[:, 0], cluster_2[:, 1], c='blue', label='Class 1')\nplt.scatter(cluster_3[:, 0], cluster_3[:, 1], c='green', label='Class 2')\nplt.scatter(test_points[:, 0], test_points[:, 1], c='black', marker='x', s=100, label='Test Points')\nplt.legend()\nplt.xlabel(\"X-axis\")\nplt.ylabel(\"Y-axis\")\nplt.title(\"3 Clusters and Test Points for kNN\")\nplt.show()\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-13T13:52:25.120815Z","iopub.execute_input":"2025-03-13T13:52:25.121241Z","iopub.status.idle":"2025-03-13T13:52:25.471474Z","shell.execute_reply.started":"2025-03-13T13:52:25.121212Z","shell.execute_reply":"2025-03-13T13:52:25.470434Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## Multi Layer Perceptron Neural Network\n\nA neural network consists of multiple layers of neurons that transform the input data through weighted connections and activation functions. Below is an explanation of the feedforward and backpropagation process used to train a simple neural network.\n\n### Forward Propagation\n\nThe network consists of three layers:\n- An **input layer** with $n$ features\n- Two **hidden layers** with ReLU activation\n- An **output layer** with softmax activation for classification\n\n#### Activation Functions\n\nThe **ReLU function** is used in the hidden layers:\n\n$$\\text{ReLU}(x) = \\max(0, x)$$\n\nThe **softmax function** is applied to the output layer to normalize the outputs into probabilities:\n\n$$\\sigma(x_i) = \\frac{e^{x_i}}{\\sum_{j} e^{x_j}}$$\n\nwhere $x_i$ is the $i^{th}$ element of the input vector.\n\n### Backpropagation\n\nTo update the weights, we compute gradients using **categorical cross-entropy loss**:\n\n$$J = -\\sum_{i=1}^{m} y^{(i)} \\log(\\hat{y}^{(i)})$$\n\nwhere $y$ is the true label and $\\hat{y}$ is the predicted probability.\n\n#### Gradient Calculation\n\nThe error propagates backward through the layers using the chain rule:\n\n1. **Output layer gradient:**\n\n   $$\\delta_3 = \\hat{y} - y$$\n   $$\\nabla W_3 = A_2^T \\delta_3$$\n   $$\\nabla b_3 = \\sum \\delta_3$$\n\n2. **Hidden layer gradients:**\n\n   $$\\delta_2 = (\\delta_3 W_3^T) \\cdot \\text{ReLU}'(Z_2)$$\n   $$\\nabla W_2 = A_1^T \\delta_2$$\n   $$\\nabla b_2 = \\sum \\delta_2$$\n\n   $$\\delta_1 = (\\delta_2 W_2^T) \\cdot \\text{ReLU}'(Z_1)$$\n   $$\\nabla W_1 = X^T \\delta_1$$\n   $$\\nabla b_1 = \\sum \\delta_1$$\n\nwhere $A$ represents activations, $Z$ represents weighted sums, and $W$ represents weights.\n\n### Gradient Descent Update Rule\n\nEach weight is updated using **stochastic gradient descent (SGD)**:\n\n$$W := W - \\alpha \\nabla W$$\n$$b := b - \\alpha \\nabla b$$\n\nwhere $\\alpha$ is the learning rate.\n\nThis process is repeated for a given number of epochs until convergence.\n\n","metadata":{}},{"cell_type":"code","source":"import numpy as np\n\ndef relu(x):\n    return np.maximum(0, x)\n\ndef relu_derivative(x):\n    return (x > 0).astype(float)\n\ndef softmax(x):\n    exp_x = np.exp(x - np.max(x, axis=-1, keepdims=True)) \n    return exp_x / np.sum(exp_x, axis=-1, keepdims=True)\n\ndef nn(x_train, y_train, learning_rate=0.01, epochs=50):\n    input_size = x_train.shape[1]\n    output_size = 10  # 10 output classes (digits 0-9)\n\n    # Initialize weights and biases\n    w1 = np.random.rand(input_size, 64) * 0.01\n    w2 = np.random.rand(64, 256) * 0.01\n    w3 = np.random.rand(256, output_size) * 0.01\n    b1 = np.zeros((1, 64))\n    b2 = np.zeros((1, 256))\n    b3 = np.zeros((1, output_size))\n\n    for epoch in range(epochs):\n        for i in range(len(x_train)):\n            x_sample = x_train[i].reshape(1, -1)\n            y_sample = y_train[i].reshape(1, -1)\n\n            # Forward propagation\n            z1 = np.dot(x_sample, w1) + b1\n            a1 = relu(z1)\n            z2 = np.dot(a1, w2) + b2\n            a2 = relu(z2)\n            z3 = np.dot(a2, w3) + b3\n            a3 = softmax(z3)  # Final output using softmax\n\n            # Compute categorical cross-entropy loss gradient\n            dz3 = a3 - y_sample  # Softmax + Cross Entropy derivative\n            dw3 = np.dot(a2.T, dz3)\n            db3 = np.sum(dz3, axis=0, keepdims=True)\n\n            dz2 = np.dot(dz3, w3.T) * relu_derivative(z2)\n            dw2 = np.dot(a1.T, dz2)\n            db2 = np.sum(dz2, axis=0, keepdims=True)\n\n            dz1 = np.dot(dz2, w2.T) * relu_derivative(z1)\n            dw1 = np.dot(x_sample.T, dz1)\n            db1 = np.sum(dz1, axis=0, keepdims=True)\n\n            # Gradient descent update\n            w3 -= learning_rate * dw3\n            b3 -= learning_rate * db3\n            w2 -= learning_rate * dw2\n            b2 -= learning_rate * db2\n            w1 -= learning_rate * dw1\n            b1 -= learning_rate * db1\n\n    return w1, w2, w3, b1, b2, b3\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-15T08:54:35.338229Z","iopub.execute_input":"2025-03-15T08:54:35.338568Z","iopub.status.idle":"2025-03-15T08:54:35.349686Z","shell.execute_reply.started":"2025-03-15T08:54:35.338544Z","shell.execute_reply":"2025-03-15T08:54:35.348293Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import numpy as np\nimport pandas as pd\nfrom sklearn.model_selection import train_test_split\nfrom sklearn.preprocessing import OneHotEncoder\nfrom sklearn.metrics import accuracy_score\n\n# Load dataset\ntrain_data = pd.read_csv('/kaggle/input/digit-recognizer/train.csv')\ntest_data = pd.read_csv('/kaggle/input/digit-recognizer/test.csv')\n\n# Split features and labels\nX = train_data.iloc[:, 1:].values  # Pixel values\ny = train_data.iloc[:, 0].values   # Labels\n\n# Normalize pixel values to range [0,1]\nX = X / 255.0\ntest_X = test_data.values / 255.0\n\n# One-hot encode labels\nencoder = OneHotEncoder(sparse=False)\ny_onehot = encoder.fit_transform(y.reshape(-1, 1))\n\n# Split into training and validation sets\nX_train, X_val, y_train, y_val = train_test_split(X, y_onehot, test_size=0.2, random_state=42)\n\n# Train the neural network\nw1, w2, w3, b1, b2, b3 = nn(X_train, y_train, learning_rate=0.01, epochs=50)\n\n# Forward pass for predictions\ndef predict(X, w1, w2, w3, b1, b2, b3):\n    z1 = np.dot(X, w1) + b1\n    a1 = relu(z1)\n    z2 = np.dot(a1, w2) + b2\n    a2 = relu(z2)\n    z3 = np.dot(a2, w3) + b3\n    a3 = softmax(z3)\n    return np.argmax(a3, axis=1)\n\n# Predict on validation set\ny_pred_val = predict(X_val, w1, w2, w3, b1, b2, b3)\ny_val_labels = np.argmax(y_val, axis=1)\n\n# Compute validation accuracy\nval_accuracy = accuracy_score(y_val_labels, y_pred_val)\nprint(f\"Validation Accuracy: {val_accuracy * 100:.2f}%\")\n\n# Predict on test set\ny_pred_test = predict(test_X, w1, w2, w3, b1, b2, b3)\n\n# Since Kaggle test set has no labels, we can't compute accuracy, but we display predictions\nprint(\"Sample Test Predictions:\", y_pred_test[:10])  # Show first 10 predictions\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-15T07:02:29.975979Z","iopub.execute_input":"2025-03-15T07:02:29.976525Z","iopub.status.idle":"2025-03-15T07:12:00.213149Z","shell.execute_reply.started":"2025-03-15T07:02:29.976485Z","shell.execute_reply":"2025-03-15T07:12:00.211869Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## K-Means Clustering\n\nK-Means is an unsupervised clustering algorithm that partitions data into $k$ clusters. The algorithm iteratively assigns points to clusters and updates the centroids until convergence.\n\n### Algorithm Steps\n\n#### Step 1: Initialize Centroids\n\nWe randomly select $k$ data points as initial cluster centroids:\n\n$$C_j = X_{r_j} \\quad \\text{for } j = 1, 2, \\dots, k$$\n\nwhere $X_{r_j}$ is a randomly chosen sample from the dataset.\n\n#### Step 2: Assign Points to Closest Centroid\n\nEach data point $X_i$ is assigned to the cluster of the nearest centroid using the **Euclidean distance**:\n\n$$d(X_i, C_j) = \\sqrt{\\sum_{d=1}^{n} (X_{i,d} - C_{j,d})^2}$$\n\nThe cluster assignment for a sample $X_i$ is:\n\n$$\\text{label}(X_i) = \\arg\\min_j d(X_i, C_j)$$\n\n#### Step 3: Compute New Centroids\n\nThe new centroids are updated as the mean of all points in the cluster:\n\n$$C_j = \\frac{1}{|S_j|} \\sum_{X_i \\in S_j} X_i$$\n\nwhere $S_j$ is the set of points assigned to cluster $j$.\n\n#### Step 4: Check for Convergence\n\nConvergence is determined by the shift in centroids:\n\n$$\\text{shift} = \\sum_{j=1}^{k} \\sqrt{\\sum_{d=1}^{n} (C_{j,d}^{\\text{new}} - C_{j,d}^{\\text{old}})^2}$$\n\nIf the shift is below a given tolerance $\\epsilon$, the algorithm stops:\n\n$$\\text{if } \\text{shift} < \\epsilon, \\text{ then stop.}$$\n\n### Complexity and Convergence\n\n- Each iteration requires $O(n k d)$ operations.\n- The algorithm converges when centroids stabilize.\n- K-Means may converge to local minima depending on centroid initialization.\n\n","metadata":{}},{"cell_type":"code","source":"import numpy as np\nimport math\n\ndef kmeans_clustering(x_train, k=3, max_iter=100000, tol=1e-4):\n    n_samples, n_features = x_train.shape\n    \n    # first we will randomly initialize centroids\n    random_indices = np.random.choice(n_samples, k, replace=False)\n    centroids = x_train[random_indices]\n\n    for _ in range(max_iter):\n        # Step 1: we will assign each point to the closest centroid\n        labels = [-1] * n_samples  # initialize labels\n        \n        for i in range(n_samples):\n            min_distance = float('inf')\n            closest_centroid = -1\n            \n            for j in range(k):\n                # we shall then compute Euclidean distance manually\n                distance = math.sqrt(sum((x_train[i][d] - centroids[j][d]) ** 2 for d in range(n_features)))\n                \n                if distance < min_distance:\n                    min_distance = distance\n                    closest_centroid = j\n\n            labels[i] = closest_centroid\n\n        # Step 2: we will compute new centroids manually\n        new_centroids = [[0] * n_features for _ in range(k)]\n        counts = [0] * k  # Track number of points in each cluster\n\n\n\n        # here, we will see for every point in training data, what cluster it belongs to by checking the label\n        # then we shall increment the counts array so as to keep track of the per-cluster population\n        # also since the new centroid will have the mean of the values at dimension d of all the data points in a cluster\n        # the inner d loop does exactly that.\n        for i in range(n_samples):\n            cluster = labels[i]\n            counts[cluster] += 1\n            for d in range(n_features):\n                new_centroids[cluster][d] += x_train[i][d]\n\n        # Avoid division by zero and compute means\n        for j in range(k):\n            if counts[j] > 0:\n                for d in range(n_features):\n                    new_centroids[j][d] /= counts[j]\n\n        # Compute manual convergence check\n        shift = 0\n        for j in range(k):\n            shift += math.sqrt(sum((new_centroids[j][d] - centroids[j][d]) ** 2 for d in range(n_features)))\n\n        if shift < tol:\n            break\n        \n        centroids = new_centroids\n\n    return np.array(centroids), np.array(labels)\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-15T15:47:49.849745Z","iopub.execute_input":"2025-03-15T15:47:49.850182Z","iopub.status.idle":"2025-03-15T15:47:49.860701Z","shell.execute_reply.started":"2025-03-15T15:47:49.850150Z","shell.execute_reply":"2025-03-15T15:47:49.859315Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import numpy as np\nimport matplotlib.pyplot as plt\n\n# Generate distinct clusters\nnp.random.seed(42)  # For reproducibility\n\n# Create three clusters with distinct centers\ncluster1 = np.random.randn(50, 2) * 0.75 + np.array([2, 2])\ncluster2 = np.random.randn(50, 2) * 0.75 + np.array([8, 8])\ncluster3 = np.random.randn(50, 2) * 0.75 + np.array([2, 8])\n\n# Stack the clusters to form the dataset\nx_train = np.vstack((cluster1, cluster2, cluster3))\n\n# Run K-Means clustering\nk = 3  # Number of clusters\ncentroids, labels = kmeans_clustering(x_train, k)\n\n# Plot results\nplt.figure(figsize=(8, 6))\ncolors = ['r', 'g', 'b']\n\n# Plot data points with cluster colors\nfor i in range(k):\n    cluster_points = x_train[np.array(labels) == i]\n    plt.scatter(cluster_points[:, 0], cluster_points[:, 1], color=colors[i], label=f'Cluster {i+1}', alpha=0.6)\n\n# Plot centroids\nplt.scatter(centroids[:, 0], centroids[:, 1], color='black', marker='X', s=200, label='Centroids')\n\nplt.legend()\nplt.title(\"K-Means Clustering Results\")\nplt.xlabel(\"Feature 1\")\nplt.ylabel(\"Feature 2\")\nplt.grid()\nplt.show()\n","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-15T15:48:52.950585Z","iopub.execute_input":"2025-03-15T15:48:52.951041Z","iopub.status.idle":"2025-03-15T15:48:53.369895Z","shell.execute_reply.started":"2025-03-15T15:48:52.951009Z","shell.execute_reply":"2025-03-15T15:48:53.368594Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## Softmax Regression\n\nSoftmax regression, also known as **multinomial logistic regression**, is a generalization of logistic regression for multi-class classification.\n\n### Hypothesis Function\n\nFor an input feature vector $x \\in \\mathbb{R}^d$, we define the **logits** as:\n\n$$z_j = \\theta_j^T x \\quad \\text{for } j = 1, 2, \\dots, k$$\n\nwhere $\\theta_j$ is the weight vector corresponding to class $j$. The **softmax function** normalizes these logits into probabilities:\n\n$$P(y = j | x) = \\frac{e^{z_j}}{\\sum_{m=1}^{k} e^{z_m}}$$\n\n### Cost Function (Cross-Entropy Loss)\n\nThe loss function for softmax regression is the **categorical cross-entropy**:\n\n$$J(\\theta) = -\\frac{1}{m} \\sum_{i=1}^{m} \\sum_{j=1}^{k} y_j^{(i)} \\log P(y = j | x^{(i)})$$\n\nwhere:\n- $m$ is the number of training samples,\n- $y_j^{(i)}$ is the one-hot encoded ground truth label for sample $i$.\n\n### Gradient Descent Update Rule\n\nThe gradient of the loss with respect to $\\theta_j$ is given by:\n\n$$\\frac{\\partial J(\\theta)}{\\partial \\theta_j} = \\frac{1}{m} \\sum_{i=1}^{m} (P(y = j | x^{(i)}) - y_j^{(i)}) x^{(i)}$$\n\nThe weight update rule using gradient descent is:\n\n$$\\theta_j := \\theta_j - \\alpha \\frac{1}{m} \\sum_{i=1}^{m} (P(y = j | x^{(i)}) - y_j^{(i)}) x^{(i)}$$\n\nwhere $\\alpha$ is the learning rate.\n\n### Properties of Softmax Regression\n\n- Outputs a probability distribution across $k$ classes.\n- Uses cross-entropy as the loss function.\n- Optimized via gradient descent (or variants like Adam, SGD).\n\n","metadata":{}},{"cell_type":"code","source":"import numpy as np\nimport math\n\ndef softmax(x):\n    \"\"\"Compute softmax values manually for a vector x.\"\"\"\n    exp_values = [math.exp(i) for i in x]\n    total = sum(exp_values)\n    return [i / total for i in exp_values]\n\ndef softmax_regression(x_train, y_train, learning_rate=0.01, epochs=50):\n    samples, features = x_train.shape\n    _, outputs = y_train.shape\n\n    # Initialize theta (weights) with zeros\n    theta = [[0] * outputs for _ in range(features)]  # Shape: (features, outputs)\n\n    for epoch in range(epochs):\n        # Initialize gradients to zero\n        grad = [[0] * outputs for _ in range(features)]\n\n        for i in range(samples):  # Loop over each sample\n            x = x_train[i]  # Feature vector of sample i\n            y = y_train[i]  # One-hot label of sample i\n\n            # Compute logits: theta.T @ x\n            logits = [sum(x[d] * theta[d][j] for d in range(features)) for j in range(outputs)]\n\n            # Compute softmax probabilities\n            probs = softmax(logits)\n\n            # Compute gradient\n            for j in range(outputs):\n                error = probs[j] - y[j]  # Error for class j\n                for d in range(features):\n                    grad[d][j] += error * x[d]  # Accumulate gradient\n\n        # Update theta using gradient descent\n        for d in range(features):\n            for j in range(outputs):\n                theta[d][j] -= learning_rate * (grad[d][j] / samples)  # Normalize by sample count\n\n    return np.array(theta)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-15T16:11:00.560842Z","iopub.execute_input":"2025-03-15T16:11:00.561294Z","iopub.status.idle":"2025-03-15T16:11:00.571669Z","shell.execute_reply.started":"2025-03-15T16:11:00.561264Z","shell.execute_reply":"2025-03-15T16:11:00.570267Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"\ndef predict(x_test, theta):\n    \"\"\"Predict class probabilities for new data.\"\"\"\n    predictions = []\n    for x in x_test:\n        logits = [sum(x[d] * theta[d][j] for d in range(len(x))) for j in range(theta.shape[1])]\n        probs = softmax(logits)\n        predictions.append(probs)\n    return np.array(predictions)\n\n# Generate dataset\nnp.random.seed(42)\n\n# Generate 50 random points with x, y values between -5 and 5\nx_train = np.random.uniform(-5, 5, (50, 2))\n\n# Encode labels\ny_train = []\nfor x, y in x_train:\n    is_integer = int(x.is_integer() and y.is_integer())  # 1 if both are integers, else 0\n    is_first_quadrant = int(x > 0 and y > 0)  # 1 if in first quadrant, else 0\n    y_train.append([is_integer, is_first_quadrant])  # Binary one-hot vector\n\nx_train = np.array(x_train)\ny_train = np.array(y_train)\n\n# Train softmax regression\ntheta = softmax_regression(x_train, y_train)\n\nprint(\"Final Weights (Theta):\\n\", theta)\n\n# Generate test data\nx_test = np.array([\n    [-3.34, -2.34343],  # Not integer, not in first quadrant\n    [2.234234, 3.23423423],    # Not integer, but in first quadrant\n    [4, 4],    # Integer, in first quadrant\n    [0, 0],    # Integer, not in first quadrant\n    [-5, -5]   # Integer, not in first quadrant\n])\n\n# Predict probabilities for test data\npredictions = predict(x_test, theta)\nprint(\"\\nPredictions on test data:\\n\", predictions)\n\n# Assign colors based on labels\ncolors = ['red' if y[0] == 1 else 'blue' for y in y_train]  # Red = integer, Blue = first quadrant\n\n# Plot training data\nplt.figure(figsize=(8, 6))\nplt.scatter(x_train[:, 0], x_train[:, 1], c=colors, marker='o', label='Training Data')\n\n# Plot test data with predicted classes\nfor i, (x, y) in enumerate(x_test):\n    pred_label = np.argmax(predictions[i])  # Predicted class (0 = integer, 1 = first quadrant)\n    color = 'red' if pred_label == 0 else 'blue'\n    plt.scatter(x, y, c=color, marker='s', edgecolors='black', s=100, label=f'Test {i+1}')\n\nplt.axhline(0, color='gray', linestyle='--')\nplt.axvline(0, color='gray', linestyle='--')\nplt.xlabel(\"X Coordinate\")\nplt.ylabel(\"Y Coordinate\")\nplt.title(\"Softmax Regression Classification\")\nplt.legend()\n\nprint('predictions are square boxes: red means point has integer coords, blue means it is in first quadrant')\nplt.show()","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-15T16:22:41.505606Z","iopub.execute_input":"2025-03-15T16:22:41.506031Z","iopub.status.idle":"2025-03-15T16:22:41.841495Z","shell.execute_reply.started":"2025-03-15T16:22:41.506002Z","shell.execute_reply":"2025-03-15T16:22:41.840279Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## ToDo : algorithms\n- Support Vector Machines\n- DBScan\n- Decision Trees\n- Random Forests\n- Kernel Based Stuff\n- More advanced NN (dropout layers, convolutional, etc.)\n- Deep Learning Algorithms","metadata":{}}]}