Ml
Given a dataset \(\mathcal{D} = \{(\vec{x}_1, y_1), \cdots, (\vec{x}_N, y_N)\}\) and a hypothesis set \(\mathcal{H}\), our learning algorithm \(\mathcal{A}\) tries to learn a function \(g \in \mathcal{H}\) that approximates the underlying, true function \(f: \mathcal{X} \to \mathcal{Y}\), which generates the points in \(\mathcal{D}\).
Credit Card Approve Problem Given a customer who is applying for a credit card, we want to build a system that determines if we should grant the application or not based on the customer's information such as age, annual salary, year in job, etc. The bank's historical credit approval data can be seen as a dataset \(\mathcal{D} = \{(\vec{x}_i, y_i)\}_{i=1}^N\)where each \(\vx_i \in \mathcal{X}\) and each represents a customer. There is a target function \(f: \mathcal{X} \to \mathcal{Y}\) that gives \(\vx\)'s credit behavior \(f(\vec{x}) = y\). Each \(\vx\) is a multidimensional vector where each component is a feature (age, for example). Our learning algorithm \(\mathcal{A}\) considers a hypothesis class \(\mathcal{H}\) and takes the dataset \(\mathcal{D}\) and tries to give a function \(g \in \mathcal{H}\) so that \(g\) performs similar to \(f\). We will use \(g\) as our system of approving credit card.
Read note →In unsupervised learning, there are no labels associated with features. Generally speaking, the ultimate goal of unsupervised learning is to find patterns and structures that help us to better understand data. Sometimes, we also use unsupervised learning to model a distribution. But we generally will not make predictions.
There are 3 types of clustering 1. Partitional (centroid, graph-theoretic, spectral) 1. Hierarchical (agglomerative, divisive) 2. Bayesian (decision-based, non-parametric)
Partitional Clustering \(k\)-means \(k\)-means is a type of partitional centroid-based clustering algorithm. The algorithm is described as follows: 1. Randomly pick \(k\) cluster centers; 2. Find the closest center for each point; 3. Update cluster centers by computing centroids; 4. While not converging, jump to step 2.
Graph-based Let \(G = (V, E)\) has vertex set \(V\) and edge set \(E\). Each \(e \in E\) can be weighted or unweighted, and it encodes the similarity between data points.
If each vertex represents a data point, then finding a clustering amongst these points is isomorphic to partition \(V\) into \(V_1\) and \(V_2\) (when \(k = 2\)). The partition of \(V\) implies that we need to split the graph. We can define an objective function to determine the best way to split the edges of a graph. Then, we can optimize the objective function in order to find the optimal partition. Consider the objective function to be \(\text{Cut}(V_1, V_2) = \sum_{i \in V_1, j \in V_2} w_{ij}\), then we would like to have split \(V\) so that the \(\text{Cut}\) is minimized. Of course, such a greedy approach could lead to a less ideal solution: \(|V_1| \ll |V_2| (|V_2| = |V| - 1)\). We want to balance the cardinality of \(V_1\) and \(V_2\). A way to balance it is to use "balanced" cut like:
\[ \text{Ratio Cut}(V_1, V_2) = \frac{\text{Cut}(V_1, V_2)}{|V_1|} + \frac{\text{Cut}(V_1, V_2)}{|V_2|}, \]
or
\[ \text{Normalized Cut}(V_1, V_2) = \frac{\text{Cut}(V_1, V_2)}{\sum_{i \in V_1} d_i} + \frac{\text{Cut}(V_1, V_2)}{\sum_{j \in V_2} d_j}, \]
where \(d_i = \sum_j w_{ij}\).
Spectral Clustering We start with a similarity/adjacency matrix, \(A\), of a graph \(G\). Let \(D\) be diagonal matrix \(D\) such that the i-\(th\) diagonal entry is \(\sum^n_{k=1} w_{ik}\). Define graph Laplacian matrix \(L = D - A\). \(L\) has the 2 following properties: 1. L is symmetric 2. L is positive semi-definite The second properties implies that all eigenvalues of \(L\) are non-negative. Then, compute the \(k\) smallest eigenvectors and stack them as columns into a matrix \(V\). Finally, we run \(k\)-means on the rows of \(V\) to obtain the clustering result.
Read note →There are two major steps in the K-means algorithm. The first one is to calculate the representatives (centroids) of a given partition. The second one is to find the partition based on the representatives.
Inputs Suppose we have a dataset looks like this:
dataset = np.array([[5, 6], [6, 5], [0, 1], [1, 0], [3, 3]]) Each row in this dataset matrix is an observation and each column in this matrix represents a feature. So, in this example, we have 5 points from a plane. And we define partition in the following way:
partition = [[0, 3, 4], [1, 2]] Observe that partition has a length of 2, which implies that the $k$ for the K-means algorithm is 2. Each list in partition represents a cluster. Elements within each list is the corresponding index of that observation in the dataset. So, with respect to this partition, the first cluster has 3 elements, namely [5, 6], [1, 0], [3, 3], and the second cluster contains [6, 5] and [0, 1].
Read note →