24:null 25:["$","title",null,{"children":"ML | 4 Dimensionality Reduction | Zhihao Yao | Observable"}] 2a:Te15,

## Sample mean and sample variance
>Data:
> ${tex.block` x_i \in \mathbb{R}^{p}, i = 1,2, \cdots , N\\~\\ X=\left(x_{1}, x_{1}, \cdots, x_{N}\right)^{T}=\left(\begin{array}{c} x_{1}^{T} \\ x_{2}^{T} \\ \vdots \\ x_{N}^{T} \end{array}\right)=\left(\begin{array}{cccc} x_{11} & x_{12} & \cdots & x_{1 p} \\ x_{21} & x_{22} & \cdots & x_{2 p} \\ \vdots & \vdots & \ddots & \vdots \\ x_{N 1} & x_{N 2} & \cdots & x_{N p} \end{array}\right)_{N \times p} \\~\\~\\ \text { Sample Mean }: \bar{x}_{p \times 1}=\frac{1}{N} \sum_{i=1}^{N} x_{i} \\ \text { Sample Covariance }: S_{p \times p}=\frac{1}{N} \sum_{i=1}^{N}\left(x_{i}-\bar{x}\right)\left(x_{i}-\bar{x}\right)^{T} \\~\\ `} >** Centering Matrix** >> ${tex` \text { let vector: } I_{N}=\left(\begin{array}{c}1 \\1 \\\vdots \\1\end{array}\right)_{N \times 1} \\~\\ `} > ${tex.block` \bar{x}=\frac{1}{N} \sum_{i=1}^{N} x_{i}=\frac{1}{N} \underbrace{\left(\begin{array}{llll}x_{1} & x_{2} \cdots x_{N}\end{array}\right)}_{X^{T}}\left(\begin{array}{c}1 \\1 \\\vdots \\1\end{array}\right)=\frac{1}{N} X^{T} I_{N} \\~\\ S=\frac{1}{N} \sum_{i=1}^{N}\left(x_{i}-\bar{x}\right)\left(x_{i}-\bar{x}\right)^{T} \\~\\ =\frac{1}{N} \left(\begin{array}{llll}x_{1}-\bar{x} & x_{2}-\bar{x} \quad \cdots \quad x_{N}-\bar{x}\end{array}\right) \left(\begin{array}{c}(x_{1}-\bar{x})^T \\(x_{2}-\bar{x})^T \\\vdots \\(x_{N}-\bar{x})^T \end{array}\right) \\~\\ `} > In the equation above:
> ${tex.block` \left(\begin{array}{llll}x_{1}-\bar{x} & x_{2}-\bar{x} \quad \cdots \quad x_{N}-\bar{x}\end{array}\right) \\~\\ =\left(\begin{array}{llll}x_{1} & x_{2} \cdots x_{N}\end{array}\right) - \left(\begin{array}{llll}\bar{x} & \bar{x} \cdots \bar{x}\end{array}\right) \\~\\ =X^T - \bar{x}1_{N}^T \\~\\ =X^T - \frac{1}{N}X^T1_{N}1_{N}^T \\~\\ =X^T\left(I_N - \frac{1}{N}1_{N}1_{N}^T\right) \\~\\~\\ \therefore \ S=\frac{1}{N} X^{T} \underbrace{\left(I_{N}-\frac{1}{N} 1_{N} 1_{N}^{T}\right)}_{H}\left(I_{N}-\frac{1}{N} 1_{N} 1_{N}^{T}\right)^{T} X \\~\\ (H \text { is centering matrix }) \\~\\ =\frac{1}{N} X^{T} H H^{T} X \\~\\ `} > Centering matrix has the following properties:

> ${tex`\text {(1) } H^{T}=H`} > ${tex.block` H^{T}=\left(I_{N}-\frac{1}{N} 1_{N} 1_{N}^{T}\right)^{T}=I_{N}-\frac{1}{N} 1_{N} 1_{N}^{T}=H `} ${tex`\text {(2) } H^{n}=H`} > ${tex.block` H^{2}=H \cdot H=\left(I_{N}-\frac{1}{N} 1_{N} 1_{N}^{T}\right)\left(I_{N}-\frac{1}{N} 1_{N} 1_{N}^{T}\right) \\~\\ =I_{N}-\frac{2}{N} 1_{N} 1_{N}^{T}+\frac{1}{N^{2}} 1_{N} 1_{N}^{T} 1_{N} 1_{N}^{T} \\~\\ =I_{N}-\frac{2}{N}\left(\begin{array}{c}1 \\1 \\\vdots \\1\end{array}\right)\left(\begin{array}{llll}1 & 1 & \cdots & 1\end{array}\right)+\frac{1}{N^{2}}\left(\begin{array}{c}1 \\1 \\\vdots \\1\end{array}\right)\left(\begin{array}{llll}1 & 1 & \cdots & 1\end{array}\right)\left(\begin{array}{c}1 \\1 \\\vdots \\1\end{array}\right)\left(\begin{array}{llll}1 & 1 \cdots & 1\end{array}\right) \\~\\ =I_{N}-\frac{2}{N}\left[\begin{array}{cccc}1 & 1 & \cdots & 1 \\1 & 1 & \cdots & 1 \\\vdots & \vdots & \ddots & \vdots \\1 & 1 & \cdots & 1\end{array}\right]_{N \times N}+\frac{1}{N^{2}}\left[\begin{array}{cccc}1 & 1 & \cdots & 1 \\1 & 1 & \cdots & 1 \\\vdots & \vdots & \ddots & \vdots \\1 & 1 & \cdots & 1\end{array}\right]_{N \times N}\left[\begin{array}{cccc}1 & 1 & \cdots & 1 \\1 & 1 & \cdots & 1 \\\vdots & \vdots & \ddots & \vdots \\1 & 1 & \cdots & 1\end{array}\right]_{N \times N} \\~\\ \Rightarrow H^{n}=H \\~\\~\\ `} ${tex.block`\large \text { Sample Mean: } \bar{x} =\frac{1}{N} X^{T} 1_{N} \\~\\ \text { Sample Covariance: } S =\frac{1}{N} X^{T} H X \\~\\ `}2b:T5a8,> ${tex.block` \text {Projection } = \vec{|a|} \cdot \cos{\theta} \\~\\ \text {let } \vec{|b|} = 1 \Longleftrightarrow b^{T}b = 1 \\~\\ a^{T} b =\vec{a} \cdot \vec{b} = \vec{|a|} \cdot \vec{|b|} \cdot \cos{\theta} = \vec{|a|} \cdot \cos{\theta} \\~\\ `} > The projection of the centralized data in the u-direction is ${tex`\left(x_{i}-\bar{x}\right)^{T} u`}

> **Loss function:** ${tex.block` J(u)=\frac{1}{N} \sum_{i=1}^{N}\left(\left(x_{i}-\hat{x}\right)^{T} u\right)^{2} \\~\\ =\sum_{i=1}^{N} \frac{1}{N} u^{T}\left(x_{i}-\hat{x}\right)\left(x_{i}-\hat{x}\right)^{T} u \\~\\ =u^{T}\underbrace{\left[\frac{1}{N} \sum_{i=1}^{N}\left(x_{i}-\hat{x}\right)\left(x_{i}-\hat{x}\right)^{T}\right]}_{S} u \\~\\ =u^{T} S u `} > Thus this has been transformed to a optimization problem:

${tex.block` \left\{\begin{array}{c} \hat{u}=\underset{u}{\operatorname{argmax}} u^{T} S u \\~\\ \text { s.t. } u^{T} u=1 \end{array}\right. \\~\\ `} > Using Lagrange multiplier method:

${tex.block` L(u, \lambda)=u^{T} S u+\lambda\left(1-u^{T} u\right) \\~\\ \frac{\partial L}{\partial u}=2 S u-2 \lambda u=0 \\~\\ S \underbrace{u}_{\text {Eigenvector }}=\underbrace{\lambda}_{\text {Eigenvalue }} u \\~\\ `} > Therefore, the solution is the eigenvector of the covariance matrix. if we want to reduce to the q-dimensions, we need to take out the first q eigenvectors with the largest corresponding eigenvalues as the projection direction.2c:[] 28:{"id":"4d8877eaf9b7a148","slug":"ml-4-dimensionality-reduction","title":"ML | 4 Dimensionality Reduction","thumbnail":"ebeb77e7bbd133da099dd302cdbd028bada75a15e664faa0e7054b37bcb4b229","access_level":"public","create_time":"$D2022-04-01T17:01:36.183Z","update_time":"$D2022-04-01T20:27:40.027Z","view_time":null,"first_public_time":"$D2022-04-01T20:16:32.306Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":"starter_2024"},"version":203,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"01b5d984f2428b1a","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":null}],"members":[{"type":"individual","id":"01b5d984f2428b1a","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":null,"role":"editor"},{"type":"team","id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"102982dc3961aa5a","slug":"machine-learning-notes","title":"Machine Learning Notes","owner":{"id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao"}},"type":"notebook","body":{"title":"ML | 4 Dimensionality Reduction","cells":[{"id":0,"value":"# ML | 4 Dimensionality Reduction\n

","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"## Methods of dimensionality reduction\n\n${tex.block`\n\\text { Dimensionality reduction }\\left\\{\\begin{array}{c}\n\\text { Feature selection} \\\\~\\\\\n\\text { Linear dimensionality reduction }(P C A 、 M D S ） \\\\~\\\\\n\\text { Nonlinear dimensionality reduction }\n\\end{array}\\right.\n`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":20,"value":"$2a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":89,"value":"

\n## Principal component analysis (PCA)\n
\n> PCA is to reconstruct the original feature space (converting the original linearly correlated vector into a linearly uncorrelated vector) to maximize the projection variance or to minimize the reconstruction distance.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":113,"value":"{\n let w = 300;\n let p = plotter({\n grid: false,\n yDomain: [6, -1],\n xDomain: [0, 7],\n axises: false,\n width: w,\n height: w * 0.8,\n });\n\n p.arrow(0,0, 6,0, { stroke: 'purple'});\n p.arrow(0,0, 5,4, { stroke: 'blue'});\n p.text('θ', 2, 0.5, { size: 16, stroke: 'blue', baseline: 'middle' });\n p.text('a', 4, 4, { size: 16, stroke: 'blue', baseline: 'middle' });\n p.text('b', 6.5, 0, { size: 16, stroke: 'purple', baseline: 'middle' });\n p.segment(5, 4, 5, 0, { \n stroke: 'blue', \n dash: '8,2'\n });\n\n return p.node;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"$2b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":100,"value":"

\n## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":97,"value":"import { plotter } from '50dadfdec01c15a8'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W2c","stdlib":"1","titling":"auto"}} 29:"$28:body"