|
/
|
[Home]
|
|
|
/notes/
|
[Notes]
|
|
|
/publications/
|
[Publications]
|
|
|
/projects/
|
[Projects]
|
|
|
/notes/nuclear-norm-sdp/
|
Nuclear Norm via SDP
|
|
|
/notes/nuclear-norm-sdp/
|
<p><p>:PROPERTIES:
:CUSTOM_ID: matrix-norm
:END:</p><h1 id="matrix-norms">Matrix norms</h1><p>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.</p><h2 id="inner-product">Inner Product</h2><p>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).
$$</p>
|
|
|
/notes/lp-duality/
|
LP Duality
|
|
|
/notes/lp-duality/
|
<p><h1 id="estimating-lp-bounds">Estimating LP bounds</h1><p>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). For example,
${f=0, s=0}$ is feasible. Therefore, $p^\star \geq 12f + 9s = 0$. Since any feasible point yields a lower bound of $p^\star$ and $p^\star$ itself is yielded by an feasible point, then finding the largest lower bound of $p^\star$ is equivalent to solving the LP.</p>
|
|
|
/notes/rpc/
|
RPC
|
|
|
/notes/rpc/
|
<p><h1 id="networks">Networks</h1><p>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.</p><p>You can use command <code>ifconfig</code> to check you network interface controller and its corresponding MAC address. There exists virtual interfaces as well. For example, <code>lo</code>, the loopback device, is a virtual interface. It connects your computer to a mini network containing just your computer.</p>
|
|
|
/notes/docker/
|
Docker
|
|
|
/notes/docker/
|
<p><h1 id="virtualization">Virtualization</h1><p>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).</p><ul><li>Each process using a virtual address space is not aware of other processes using memory (illusion of private memory).</li><li>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.</li><li>JVM or PVM runs Java Bytecode and Python Bytecode. Programs written in Java and Python are compiled to their corresponding byte code instead of a specific machine code.</li><li>Virtual operating systems, or a containers, are run on a some flavor of Linux. You can have a container of Ubuntu and a container on Debian (but not Windows, since they are running on top of Linux). Containers are more efficient than virtual machines, but less flexible.</li></ul><p>Containers and Virtual Machines are Sandboxes.</p>
|
|
|
/notes/pla/
|
Perceptron Learning Algorithm
|
|
|
/notes/pla/
|
<p><p>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}\).</p><div id="outline-container-credit-card-approve-problem" class="outline-3"><h3 id="credit-card-approve-problem">Credit Card Approve Problem</h3><div id="outline-text-credit-card-approve-problem" class="outline-text-3"><p>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.</p></div></div>
|
|
|
/notes/clustering/
|
Clustering
|
|
|
/notes/clustering/
|
<p><p>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.</p><p>There are 3 types of clustering 1. Partitional (centroid,
graph-theoretic, spectral) 1. Hierarchical (agglomerative, divisive) 2.
Bayesian (decision-based, non-parametric)</p><div id="outline-container-partitional-clustering" class="outline-3"><h3 id="partitional-clustering">Partitional Clustering</h3><div id="outline-text-partitional-clustering" class="outline-text-3"><div id="outline-container-k-means" class="outline-4"><h4 id="k-means">\(k\)-means</h4><div id="outline-text-k-means" class="outline-text-4"><p>\(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.</p></div></div></div></div>
|
|
|
/notes/k-means/
|
K-means in Python
|
|
|
/notes/k-means/
|
<p><p>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.</p><div id="outline-container-inputs" class="outline-3"><h3 id="inputs">Inputs</h3><div id="outline-text-inputs" class="outline-text-3"><p>Suppose we have a dataset looks like this:</p><div class="src src-python"><div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;-webkit-text-size-adjust:none"><code class="language-python" data-lang="python"><span style="display:flex"><span>dataset <span style="color:#f92672">=</span> np<span style="color:#f92672">.</span>array([[<span style="color:#ae81ff">5</span>, <span style="color:#ae81ff">6</span>],
</span></span><span style="display:flex"><span> [<span style="color:#ae81ff">6</span>, <span style="color:#ae81ff">5</span>],
</span></span><span style="display:flex"><span> [<span style="color:#ae81ff">0</span>, <span style="color:#ae81ff">1</span>],
</span></span><span style="display:flex"><span> [<span style="color:#ae81ff">1</span>, <span style="color:#ae81ff">0</span>],
</span></span><span style="display:flex"><span> [<span style="color:#ae81ff">3</span>, <span style="color:#ae81ff">3</span>]])</span></span></code></pre></div></div><p>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:</p></div></div>
|
|
