CS205A Lecture 8 Eigenproblems III; QR iteration, conditioning; singular value decomposition (SVD)
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾第八讲,这一讲继续介绍了如何计算特征值,然后介绍了SVD。
克里洛夫(Krylov) 子空间法考虑如下矩阵:
K_k=\left(
\begin{matrix}
\vec b & A\vec b & A^2 \vec b& \ldots & A^{k-1}\vec b
\end{matrix}
\right)通过研究上述矩阵来求特征值和特征向量的方法被称为克里洛夫子空间法,事实上,我们有如下算法:
Arnoldi迭代
选择$\vec q_1 \in \mathbb R^n$为任意单位向量。
对$k=2,3,…$
令$\vec a_k =A\vec q_{k-1}$
减去投影:
\vec b_k =\vec a_{k}-\text{proj}_{\text{span}\{\vec q_1,...,\vec q_{k-1}\}} \vec a_{k}
正规化,计算$\vec q_k =\vec b_k /\Arr ...
CS229 2017版作业4
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
作业地址:https://github.com/Doraemonzzz/CS229
参考资料:https://github.com/zyxue/stanford-cs229
这部分回顾2017版作业4。
1. Neural Networks: MNIST image classfication(a)(b)(c)前向传播部分很简单,反向传播部分的推导请参考CS231作业1,其中如下代码
#计算第二层梯度
p3 = np.exp(scores) / p2.reshape(-1, 1)
p3[np.arange(N), y] -= 1
dW2 = X1.T.dot(p3) / N + 2 * reg * W2
db2 = np.sum(p3, axis=0) / N
grads["W2"] = dW2 ...
CS205A HW3
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾作业3。
Problem 1(a)由定义,我们有
\begin{aligned}
C&= LL^T\\
&= \left(
\begin{matrix}
L_{11} & \vec 0 & 0 \\
\vec l_k^T & l_{kk} & \vec 0^T \\
L_{31} & \vec l_k' & L_{33}
\end{matrix}
\right)
\left(
\begin{matrix}
L_{11}^T & \vec l_k & L_{31}^T \\
\vec0^T & l_{kk} & \vec l_k'^T \\
0 & \vec 0 & L_{33}^T
\end{matrix}
\right)\\
&=\left(
\begin{matrix}
L_{11} L_{11}^T & L_{11}\vec l_k & ...
CS205A HW2
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾作业2。
Problem 1(a)$\forall A,B \in \mathbb R^{n\times n}$,以及满足$||\vec x||=1 $的$\vec x $,我们有
\begin{aligned}
||(A+B)\vec x ||
&=||A \vec x + B\vec x||\\
&\le ||A \vec x|| + ||B\vec x|| \\
&\le ||A|| + ||B||
\end{aligned}其中最后一个不等号是由$||A||$的定义。
所以
||A+B||= \max \{||(A+B)\vec x||: ||\vec x||=1 \}
\le ||A||+||B||(b)利用等价定义:
||A|| =\max_{\vec x \in \mathbb R^n \setminus \{0\}}
\frac{||A\vec x||}{||\vec x||}那么显然有
\begin{al ...
CS205A Lecture 7 Eigenproblems; Algorithms
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾第七讲,这一讲主要介绍了计算特征值的方法。
首先回顾我们的问题条件:
\begin{aligned}
A\in \mathbb R^{n\times n}是对称矩阵\\
\vec x_1,...,\vec x_n \in \mathbb R^n 为特征向量\\
|\lambda_1|\ge |\lambda_2| \ge ...\ge |\lambda_n |是特征值
\end{aligned}幂迭代(Power Iteration)注意到所有的特征向量张成$\mathbb R^n $,所以对于任意向量$\vec v$,我们有
\vec v = c_1 \vec x_1 +...+c_n \vec x_n因此
\begin{aligned}
A\vec v
&= c_1 A\vec x_1 +....+c_n A\vec x_n\\
&=c_1 \lambda_1 \vec x _1 +...+ c_n \lambda_n \ ...
一道图论题
最近看到一道很有意思的图论题,来自Mit公开课Session 16。
In a round-robin tournament, every two distinct players play against each other just once. For around-robin tournament with no tied games, a record of who beat whom can be described with a tournament digraph, where the vertices correspond to players and there is an edge $\langle x\to y\rangle$ iff $x$ beat $y$ in their game.
A ranking is a path that includes all the players. So in a ranking, each player won the game against the next ranked player, but may ver ...
CS229 老版作业4
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
作业地址:https://github.com/Doraemonzzz/CS229
参考资料:https://github.com/zyxue/stanford-cs229
这部分回顾老版作业4。
1. EM for supervised learning(a)由定义可得
\begin{aligned}
p(y^{(j)}|x^{(j)})
&= p(y^{(j)}|x^{(j)},z^{(j)}) p(z^{(j)}|x^{(j)})\\
&= \frac 1{\sqrt{2\pi}\sigma} \exp \Big(
-\frac{(y^{(j)}-\theta_{z^{(j)}}^T x^{(j)})^2}{2\sigma^2}
\Big) g(\phi^T x^{(j)})^{z^ ...
CS205A Lecture 6 Eigenproblems, How they arise, properties
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾第六讲,这一讲主要介绍了特征向量的应用及其性质。
Chapter 5 特征向量定义以及性质首先给出如下定义:
定义5.1(特征值和特征向量)$\vec x \neq \vec 0$是矩阵$A \in \mathbb C^{n\times n}$的特征向量,如果存在某个复数$\lambda$,使得$A\vec x = \lambda \vec x $,$\lambda $被称为特征值。
定义5.2(谱和谱半径)矩阵$A$的谱是指$A$的特征值,谱半径$\rho(A)$是使得最大化$|\lambda |$的特征值$\lambda $。
如果$\vec x$是特征向量,其特征值为$\lambda $,那么显然有
A(c\vec x) = cA\vec x =c\lambda \vec x =\lambda(c\vec x)所以不失一般性,我们可以假设特征向量都满足
||\vec x || =1我们之前都默认特征向量存在,但是这个事实不是 ...
CS205A Lecture 5 Column spaces and QR
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾第五讲,这一讲主要介绍了$QR$分解。
Chapter 4 列空间和$QR$分解正规方程的结构上一讲主要介绍了对称矩阵的一些性质,现在考虑$A^TA$的条件数:
\begin{aligned}
\text{cond }A^T A
&=||A^T A||.||(A^T A)^{-1}||\\
&\approx ||A^T||.||A||.||A^{-1}||.||(A^T)^{-1}||\\
&=||A||^2 ||A^{-1}||^2\\
&=(\text{cond }A)^2
\end{aligned}这说明如下方程更加不稳定:
A^TA \vec x =\vec b注意到
\text{cond } I_{n} =1所以如果我们有
A^T A=I_n那么就不会有不稳定的情形发生,这就引入了正交性的概念。
正交性对于矩阵
Q= \left(
\begin{matrix}
\mid & \mid & & \mid \ ...
CS205A HW1
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾作业1。
Problem 1最小化$f(x)$等价于求$f’(x)=0$的根,所以
(a)向前误差:
|x^*- x_{test}|(b)向后误差:
|f'(x^*)- f'(x_{test})|(c)条件数:
\begin{aligned}
\frac{|x^*- x_{test}|}{|f'(x^*)- f'(x_{test})|}
&\approx \frac{|x^*- x_{test}|}{|f''(x_{test})(x^*- x_{test})|} \\
&=\frac 1 {|f''(x_{test})|}
\end{aligned}Problem 2(a)$\epsilon $相当于相对误差,相比于$(x \Diamond y) +\epsilon $的形式,$(1+\epsilon )(x \Diamond y) $可以更方便的比较不同测量值的误差大小。
(b)证明:存在性是显然的,所以我们只需证明
0\l ...
CS231 作业2
课程视频地址:https://study.163.com/courses-search?keyword=CS231
课程主页:http://cs231n.stanford.edu/2017/
参考资料:
https://github.com/Halfish/cs231n/tree/master/assignment2/cs231n
https://github.com/wjbKimberly/cs231n_spring_2017_assignment/blob/master/assignment2/TensorFlow.ipynb
我的代码地址:https://github.com/Doraemonzzz/CS231n
这一部分回顾作业2的重点。
准备工作如果读取数据的时候报错,那么需要修改data_utils.py文件中如下函数:
def get_CIFAR10_data(num_training=49000, num_validation=1000, num_test=1000,
subtract_mean=True):
找到
cifar ...
CS205A HW0
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾作业0,主要是复习线性代数。
Problem 1$\forall f,g \in C^1 (\mathbb R), \forall \alpha, \beta \in \mathbb R$,我们有$\alpha f+ \beta g$连续可导,所以$\alpha f + \beta g \in C^1 (\mathbb R)$,因此$C^1 (\mathbb R)$是线性空间。
考虑$C^1 (\mathbb R)$的子集多项式全体,显然全体多项式的维度为$\infty$,因此$C^1 (\mathbb R)$的维度为$\infty$。
Problem 2
A^T A = \left[
\begin{matrix}
\vec c_1^T \vec c_1& \ldots & \vec c_1^T \vec c_n \\
\ldots & \ldots & \ldots \\
\vec c_n^T \vec c_1& \ldots ...