Life with Physics

Problem:  (1) Toss a dice. You can get face value in dollars or you can choose to try again twice. What is the expected payoff according to the best strategy? (2) Compare the payoff in (1) to the expectation of the maximum face value of two tosses without calculation. (3) What if you can try again at most 50 times? Estimate the number to the 3 decimal. (4) What if you can try again for infinite times but each toss will cost you 1 dollar? The first toss is free. Solution: (1) Let $f(n)$ be the expected payoff when we can roll at most $n$ times, $f(1)=(1+2+3+4+5+6)/6=3.5$.  For $f(n+1)$, the strategy is to try again if the face value is less than $f(n)$, otherwise take the face value: \begin{equation}f(n+1) = \frac{1}{6}\sum_{i=1}^6\max\left[i, f(n)\right]\,.\tag{1}\end{equation} As a result, $f(2)=(3.5 + 3.5 + 3.5 + 4+5+6) / 6=4.25$. (2) The payoff in (1) should be smaller since we cannot take the face value of the previous roll. (3) We continue to calculate (1): $f(3)=4.67$, $...

L1 regularization is to add a L1-norm term: \begin{equation}\hat{\boldsymbol{\beta}}^{\text{lasso}}=\text{argmin}_{\boldsymbol{\beta}}\left\{\sum_{i=1}^n\left(y^{(i)}-\beta_0-\sum_{j=1}^p \beta_jx^{(i)}_{j}\right)^2+\lambda\sum_{j=1}^p \left|\beta_j\right|\right\}\,.\end{equation} Note that there is no regularization for the interception term $\beta_0$ since $\beta_0$ is a global shift to all $y$. We can remove $\beta_0$ by making $\mathbf{y}$ and $\mathbf{X}$ centered.  With centered inputs , we have \begin{equation}\hat{\boldsymbol{\beta}}^{\text{lasso}}=\text{argmin}_{\boldsymbol{\beta}}\left\{(\mathbf{y}-\mathbf{X}\boldsymbol{\beta})^T(\mathbf{y}-\mathbf{X}\boldsymbol{\beta})+\lambda \left|\left|\boldsymbol{\beta}\right|\right|_1\right\}\,.\tag{1}\end{equation} Compared with ridge , lasso can be used for continuous subset (feature) selection besides regularization since it leads to sparse coefficients. The argument is from an equivalent optimization problem of (1): \begin{...

L2 regularization is to add a L2-norm term to the optimization problem $\min_{\mathbf{x}}f(\mathbf{x})$ as \begin{equation}\min_{\mathbf{x}}\,l_{\lambda}(\mathbf{x})\equiv f(\mathbf{x})+\frac{\lambda}{2} \left|\left| \mathbf{x}\right|\right|^2_2\,.\tag{1}\end{equation} Remarks: In deep learning, L2 regularization is also referred as weight decay . This is because in the vallina SGD \begin{eqnarray}\mathbf{x}^{(t+1)} = \mathbf{x}^{(t)}-\gamma\left[\nabla f(\mathbf{x}^{(t)})+\lambda\mathbf{x}^{(t)}\right]=(1-\gamma\, \lambda)\,\mathbf{x}^{(t)}-\gamma\,\nabla f(\mathbf{x}^{(t)})\,,\end{eqnarray} L_2 regularization is to decay the weight $\mathbf{x}^{(t)}$ by a factor $1-\gamma \lambda$. In more sophisticated optimizers beyond vanilla SGD, L2 regularization is different from weight decay: L2 regularization: replace each $\nabla f(\mathbf{x})$ in the optimizer by $\nabla f(\mathbf{x})+\lambda\mathbf{x}$; Weight decay: replace each $\nabla f(\mathbf{x})$ in the optimizer by $\nabla ...

Given $n$ samples $y^{(k)}$ and the corresponding fitting values $\hat{y}^{(k)}$, one can evaluate the goodness-of-fit by \begin{equation} R^2 = 1 - \frac{\sum_{k=1}^n \left(y^{(k)}-\hat{y}^{(k)}\right)^2}{\sum_{k=1}^n\left(y^{(k)}-\bar{y}\right)^2}\,,\tag{1}\end{equation} where $\bar{y}\equiv \frac{1}{n}\sum_{i=1}^n y^{(k)}$.  Let $Y=\hat{Y}+e$, we can write $R^2$ in short as \begin{equation}R^2=1-\frac{\mathbb{E}(e^2)}{\text{Var}(Y)}\,.\end{equation} In the following, we will discuss $R^2$ in the scope of linear regression. With interception term, as shown in this post , we have $\mathbb{E}(e)=0$ and $\text{Var}(Y)=\text{Var}(\hat{Y})+\text{Var}(e)$. As a result, \begin{equation}R^2=1-\frac{\text{Var}(e)}{\text{Var}(Y)}=\frac{\text{Var}(\hat{Y})}{\text{Var}(Y)}\geq 0\,.\tag{2}\end{equation} Without interception term, as shown in this  post , we can only have $\mathbb{E}(Y^2)=\mathbb{E}(\hat{Y}^2)+\mathbb{E}(e^2)$. As a result, \begin{equation} R^2=\frac{\mathbb{E}\left(...

Hilbert space Given a linear space $V$ over the field $\mathbb{C}$, we define an inner product , i.e, a map $\langle \cdot, \cdot\rangle : \, V\times V \rightarrow \mathbb{C}$ that satisfies the following axioms for all vectors $\mathbf{x}, \mathbf{y}, \mathbf{z}\in V$ and all scalars $\alpha \in \mathbb{C}$: $\langle \mathbf{x}, \mathbf{y}\rangle =\langle \mathbf{y}, \mathbf{x}\rangle^*$ $\langle \mathbf{x}+\mathbf{y}, \mathbf{z}\rangle = \langle \mathbf{x}, \mathbf{z}\rangle + \langle \mathbf{y}, \mathbf{z}\rangle$ $\langle \alpha\,\mathbf{x}, \mathbf{y}\rangle=\alpha \langle \mathbf{x}, \mathbf{y}\rangle$ $\langle \mathbf{x}, \mathbf{x}\rangle \geq 0$. Equality holds iff $\mathbf{x}=\mathbf{0}\,.$ We can then define the norm $\left|\left|\mathbf{x}\right|\right|^2\equiv \langle \mathbf{x}, \mathbf{x}\rangle$. The norm satisfies the following two properties: Cauchy-Schwarz inequality: $\left|\langle \mathbf{x}, \mathbf{y}\rangle\right|^2\leq \left|\left|\mathbf{x}\right|\right|^2\,\...

Problems: (1) Why correlation matrix is positive semi-definite?  (2) For n random variables, if all their pairwise correlations are $\rho$, what is the range of $\rho$? (3) For three random variables X, Y and Z, the correlation between X and Y is $a$ and the correlation between X and Z is $b$. What is the range of correlation between Y and Z? Solve it in three ways. (4) For two covariance matrices A and B, is AB a covariance matrix when AB=BA.  Solution: (1) Since $\text{Var}(\sum_{i} a_iX_i)=\sum_{i,j}a_ia_j\text{Cov}(X_i, X_j) \geq 0$, covariance matrix is positive semi-definite. So does correlation matrix since it is a covariance matrix when all random variables have unit variance.   (2) The correlation matrix is of the form $\boldsymbol{\Sigma}=(1-\rho)\mathbf{I}+\rho\, \mathbf{e}\mathbf{e}^T$ where $\mathbf{e}\equiv[1, \cdots, 1]^T$. $\mathbf{e}\mathbf{e}^T$ has one eigenvector $\mathbf{e}$ with eigenvalue $n$ and $n-1$ eigenvectors th...

PCA is a common technique to reduce data in high dimensions to a lower dimensional subspace, either for visualization or data compression.  Suppose we have a dataset consisting of $n$ samples and each sample is of $p$ features. We represent the dataset by a $n\times p$ matrix $\mathbf{X}$. We also assume that $\mathbf{X}$ is centered so that the sample covariance matrix $\boldsymbol{\Sigma}$ in the feature space is: \begin{eqnarray} \boldsymbol{\Sigma} = \frac{1}{n}\mathbf{X}^T\mathbf{X}\,.\tag{1}\end{eqnarray} PCA is to find a set of $k\leq p$ feature vectors $\mathbf{v}_1, \cdots, \mathbf{v}_k$ (called principal component directions) such that these new feature vectors have the largest $k$ sample variances $\mathbf{v}^T_1 \boldsymbol{\Sigma} \mathbf{v}_1,\cdots, \mathbf{v}^T_k \boldsymbol{\Sigma} \mathbf{v}_k$. That is, $\mathbf{v}_1, \cdots, \mathbf{v}_k$ are the eigenvectors of $\boldsymbol{\Sigma}$ corresponding to the $k$ largest eigenvalues $\lambda_1\geq \cdots \geq \la...