Notes

:PROPERTIES: :CUSTOM_ID: matrix-norm :END: Matrix norms Given a matrix $X \in \mathbb{R}^{m \times n}$, $\sigma_{i}(X)$ denotes the $i$-th largest singular value of $X$ and is equal to the square root of the $i$-th largest eigenvalue of $XX’$. The rank of $X$, denoted as $\mathrm{rank}(X) = r$ is the number of non-zero singular values. Inner Product Given $X, Y \in \mathbb{R}^{m \times n}$, the inner product between $X$ and $Y$, denoted by $\langle X, Y\rangle$, is defined as $$ \langle X, Y \rangle := \mathrm{Tr}(X’Y) = \sum_{i=1}^m \sum_{j=1}^n X_{ij}Y_{ij} = \mathrm{Tr}(Y’X).

Estimating LP bounds Given an optimization problem $$ \begin{align} \max_{f, s} &\quad 12f + 9s \ \st &\quad 4f + 2s \leq 4800 \ &\quad f + s \leq 1750 \ &\quad 0 \leq f \leq 1000 \ &\quad 0 \leq s \leq 1500 \ \end{align} $$ Suppose the maximum profit is $p^\star$. How can we bound $p^\star$? The lower bound of $p^\star$ can be found by picking any feasible point (since maximization).

Networks Network Interface Controllers (NICs) can connect a computer to different physical mediums, such as Ethernet and Wi-Fi. Every NIC in the world has a unique MAC (media access control) address. It consists of 48 bits. Therefore, there are 28 trillion possible MAC addresses. Some devices randomly change their MAC address for privacy. You can use command ifconfig to check you network interface controller and its corresponding MAC address. There exists virtual interfaces as well.

Virtualization Virtualization is the illusion of private resources, provided by the software. We have virtual memory, virtual machine (hardware), virtual machine (languages), virtual operating system (container). Each process using a virtual address space is not aware of other processes using memory (illusion of private memory). Virtualized resources include CPU, RAM, disks, network devices, etc. VMs rarely use all their allocated resources, so overbooking is possible. If each program is deployed to a different VM, operating system overheads dominate.

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.

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.

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.