18.065 Lecture 1
课程主页:https://ocw.mit.edu/courses/mathematics/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/index.htm
之前在Gilbert Strang教授的主页上注意到新课Matrix Methods in Data Analysis, Signal Processing, and Machine Learning,上周终于上线了,最近计划暑假前把这门课刷完,记录一些笔记和习题解析。
这一讲的主题是The Column Space of $A$ Contains All Vectors $Ax$。
例1首先回顾$Ax$的解释,其中$A$是矩阵,$x$是向量,考虑如下例子:
Ax = \left[
\begin{matrix}
2 & 1 &3 \\
3 & 1 & 4 \\
5 & 7 & 12
\end{matrix}
\right]\left[
\begin{matrix}
x_1\\
x_2\ ...
EE263 Homework 3
课程主页:https://see.stanford.edu/Course/EE263
这次回顾EE263作业3。
2.17(a)因为
f(x)=\sum_{i=1}^n a_i x_i +b所以
\frac{\partial f}{\partial x_k} =a_k因此
\begin{aligned}
\nabla f(x)&=\left[ \begin{matrix}{\frac{\partial f}{\partial x_{1}}} \\ {\vdots} \\ {\frac{\partial f}{\partial x_{n}}}\end{matrix}\right]\\
&=\left[ \begin{matrix}
a_1 \\
{\vdots} \\
a_n
\end{matrix}\right]\\
&=a
\end{aligned}(b)因为
f(x)=\sum_{i=1}^n\sum_{j=1}^n x_i a_{ij} x_j所以
\frac{\partial f}{\partial x_k}=\sum_{j=1}^n a_{kj} x_j
+ ...
EE263 Lecture 6 Least-squares applications
课程主页:https://see.stanford.edu/Course/EE263
这次回顾第六讲,这一讲介绍最小二乘法以及其应用。
几何解释$A x_{\text{ls}}$是$\mathcal{R}(A)$中最接近$y$的点($A x_{\text{ls}}$是$y$在$\mathcal{R}(A)$上的投影):
最小二乘(近似)求解
假设$A$是满秩,瘦矩阵
为了找到$x_{\text{ls}}$,我们将最小化残差的平方,
\|r\|^{2}=x^{T} A^{T} A x-2 y^{T} A x+y^{T} y
令关于$x$的梯度为$0$得到:
\nabla_{x}\|r\|^{2}=2 A^{T} A x-2 A^{T} y=0
这产生正规方程:
A^{T} A x=A^{T} y
假设$A^TA$可逆,那么我们有
x_{\text{ls}}=\left(A^{T} A\right)^{-1} A^{T} y
从上式不难看出$x_{\text{ls}}$是$y$的线性函数
如果$A$是方阵并且可逆,那么
x_{\text{ls}}=\left( ...
一道有趣的期望题
记录一道有趣的期望题,是一道构造性的问题,题目来自Mit公开课Session 33。
问题$R$是取正整数的随机变量,如果$\mathbb E[R]=2$,那么$\text{Var}[R]$最多能多少?
这题我的第一反应是正无穷,但是一开始没构造出来,后来查阅资料也没有相关例子,最后思考了一个多小时才构造出例子,这里记录下思路。
构造如下:
\begin{aligned}
\mathbb P[R=i] &=\frac 4 {i(i+1)(i+2)} ,i \in \mathbb N
\end{aligned}下面分别验证条件:
\begin{aligned}
\sum_{i=1}^\infty \mathbb P[R=i] &=\sum_{i=1}^\infty \frac 4 {i(i+1)(i+2)}\\
&= 2\sum_{i=1}^\infty \left(\frac{1}{i(i+1)} - \frac {1}{(i+1)(i+2)}\right) \\
&=2 \sum_{i=1}^\infty \left(\frac{1}{i(i+1)} - \frac {1}{( ...
EE263 Lecture 5 Least-squares
课程主页:https://see.stanford.edu/Course/EE263
这次回顾第五讲,这一讲介绍了正交以及最小二乘法。
几何性质假设$U=\left[ \begin{array}{lll}{u_{1}} & {\cdots} & {u_{k}}\end{array}\right]$正交,如果$w=Uz$,那么$|w|=|z|$,这说明
乘以$U$不改变范数
$w=Uz$是保距的:保持距离不变
性质的证明:
\|w\|^{2}=\|U z\|^{2}=(U z)^{T}(U z)=z^{T} U^{T} U z=z^{T} z=\|z\|^{2}
内积同样保持不变:$\langle U z, U \tilde{z}\rangle=\langle z, \tilde{z}\rangle$
如果$w=Uz,\tilde{w}=U \tilde{z}$,那么
\langle w, \tilde{w}\rangle=\langle U z, U \tilde{z}\rangle=(U z)^{T}(U \tilde{z})=z^{T} U^{T} ...
From Nand to Tetris week 6
这次回顾第六章的内容,这一章介绍了如何编写汇编编译器。
课程官网:
https://www.nand2tetris.org/
视频地址:
https://www.coursera.org/learn/build-a-computer
Part 1:课程回顾这部分从略,主题内容在Project部分。
Part 2:项目该项目我使用的语言是Python,只要按照提示实现每个接口即可。
CodeCode将C指令翻译为2进制字符,接口如下:
根据课件29叶的对应关系进行替换即可:
class Code():
def __init__(self):
pass
def dest(self, mnemonic):
res = ""
if mnemonic == "M":
res = "001"
elif mnemonic == "D":
res = "010"
elif mnemonic == "MD":
res = " ...
EE263 Homework 2
课程主页:https://see.stanford.edu/Course/EE263
这次回顾EE263作业2。
3.2(a)令
A=\left[ \begin{array}{lllll}{l_{1}} & {l_{2}} & {l_{3}} & {\cdots} & {l_{20}} \\ {m_{1}} & {m_{2}} & {m_{3}} & {\cdots} & {m_{20}} \\ {s_{1}} & {s_{2}} & {s_{3}} & {\cdots} & {s_{20}}\end{array}\right]如果$p,\tilde p$无法识别,那么
\begin{aligned}
Ap &=A\tilde p\\
A(p-\tilde p) & =0
\end{aligned}即$p-\tilde p \in \mathcal N(A)$。
(b)题目的含义是问,是否存在非负系数$a_1,a_2,a_3$,使得
Ap_{\text{test}} = A p_{\text{match}}=A\left[ \begin{array}{lll}{u} & { ...
EE263 Lecture 4 Orthonormal sets of vectors and QR factorization
课程主页:https://see.stanford.edu/Course/EE263
这次回顾第四讲,这一讲继续复习线性代数,然后介绍了正交的概念。
矩阵的零空间$A\in \mathbb R^{m\times n}$的零空间定义为
\mathcal{N}(A)=\left\{x \in \mathbb{R}^{n} | A x=0\right\}
$\mathcal N(A)$是通过$y=Ax$映射到零向量的向量
$\mathcal N(A) $是和$A$的所有行向量都正交的向量的集合
如果$y=Ax,z\in \mathcal N(A)$,那么$y=A(x+z)$
相反,如果$y=Ax, y=\tilde A x$,那么存在某个$z\in \mathcal N(A)$,使得$\tilde x = x+z$
zero零空间$A$称为一对一如果$\mathcal N(A) = \{0\}$,这等价于:
$x$可以由$y=Ax$唯一决定(即,线性变换$y=Ax$不损失信息。)
从$x$到$Ax$的映射是一对一的:不同的$x$映射到不同的$y$
$A$的列向量线性无关
$A$存在 ...
一道有趣的概率题
记录一道有趣的概率题,题目来自Mit公开课Session 29。
问题假设投一枚均匀的硬币,用H表示正面,T表示反面。现在不停地投硬币直至看到HTT或HHT,问先看到HHT的概率?
这题乍一看还是挺难的,后来查阅了网上的资料才有思路,主要是运用条件概率,还有很多类似的问题也可以同样处理。
参考资料:
https://dicedcoins.wordpress.com/2012/07/19/flip-hhh-before-htt/
定义HHT出现在HTT之前的事件为$A$,那么
\begin{aligned}
\mathbb P[A]
&=\mathbb P[A|H]\mathbb P[H]+ \mathbb P[A|T]\mathbb P[T]\\
&=\frac 1 2 \mathbb P[A|H] +\frac 1 2 \mathbb P[A]
\end{aligned}所以
\mathbb P[A] =\mathbb P[A|H]另一方面
\begin{aligned}
\mathbb P[A|H]
&=\mathbb P[A|HH] \mathbb P[H]+\math ...
EE263 Lecture 3 Linear algebra review
课程主页:https://see.stanford.edu/Course/EE263
这次回顾第三讲,这一讲继续复习线性代数。
线性化如果$f:\mathbb R^n \to \mathbb R^m$在$x_0\in \mathbb R^n$可微,那么
x \text { near } x_{0} \Longrightarrow f(x) \text { very near } f\left(x_{0}\right)+D f\left(x_{0}\right)\left(x-x_{0}\right)其中
D f\left(x_{0}\right)_{i j}=\left.\frac{\partial f_{i}}{\partial x_{j}}\right|_{x_{0}}是导数(雅克比)矩阵。
如果定义$y=f(x), y_{0}=f\left(x_{0}\right), \delta x:=x-x_0,\delta y:=y-y_0$,那么上述近似可以写为
\delta y \approx D f\left(x_{0}\right) \delta x通过范围测量导航来看一个 ...
From Nand to Tetris week 5
这次回顾第五章的内容,这一章介绍了计算机体系结构,完整搭建了一个计算机。
课程官网:
https://www.nand2tetris.org/
视频地址:
https://www.coursera.org/learn/build-a-computer
Chapter 5 计算机体系结构Part 1:课程回顾这部分内容从略,这一章的主要内容为项目部分。
Part 2:项目MemoryMemory的架构如下:
关键问题是判断address和16383以及24576的关系,注意到上述数字的二进制表示为:
\begin{aligned}
16383 :& 011111111111111 \\
16384 :& 100000000000000\\
24575:&101111111111111\\
24576:&110000000000000
\end{aligned}所以可以根据address[14]和address[13]判断操作的位置,对应代码如下:
//判断是否小于16384, 利用address的最高位判断
DMux(in=load, sel=address[14], a=ram, ...
From Nand to Tetris week 4
这次回顾第四章的内容,这部分主要介绍了机器语言。
课程官网:
https://www.nand2tetris.org/
视频地址:
https://www.coursera.org/learn/build-a-computer
Chapter 4 机器语言Part 1:课程回顾机器语言冯诺依曼式计算机的架构如下:
内存部分分为指令和数据,这部分都是二进制数,指令部分称为机器语言。显然直接编写机器语言非常麻烦,所以人们想到了使用助记符,例如:
助记符更进一步即发展为汇编语言。
Hack机器语言概述Hack是一个基于冯诺依曼架构的16位计算机,由一个CPU,指令内存和数据内存以及两个内存映射I/O设备(显示器和键盘组成)。这里有一点非常关键,就是Hack将指令内存和数据内存分开(这称为哈佛式计算机结构),而一般计算机中并不是如此,除此之外,两个内存区都是16-位宽,有15位地址空间。
寄存器使用时有两个称为D和A的16位寄存器,这两个寄存器能够被算数和逻辑指令显式控制,例如A=D-1或D!=A。注意D仅用来存储数据值,A既可以作为数据寄存器也可以作为地址寄存器。注意因为Hack的指令 ...