本文从不同角度给出奇异值分解的物理意义

• 参考知乎回答1:奇异值的物理意义是什么？
• 参考知乎回答2:人们是如何想到奇异值分解的？

公式说明

$$A=U\Sigma V^{T}$$

• \(U,V\)都是正交矩阵,\(\Sigma\)是对角矩阵,对角上的元素是矩阵\(A\)的奇异值
• 若保留对角元素最大的K个值
  • \(K=r=Rank(A)\)时为紧奇异值分解,对应的是无损压缩,此时由于奇异值保留数量与原始矩阵相同,能做到对原始矩阵A的完全还原
  • \(K< r=Rank(A)\)时为截断奇异值分解,对应的是有损压缩,此时由于奇异值保留数量比原始矩阵的小,做不到对原始矩阵A的完全还原,但是如果K足够大就能做到对矩阵A的较完美近似

图像处理方面

• 直观上可以理解为奇异值分解是将矩阵分解为若干个秩一矩阵之和,用公式表示就是:
  $$A=\sigma_{1}u_{1}v_{1}^{T}+\sigma_{2}u_{2}v_{2}^{T}+…+\sigma_{r}u_{r}v_{r}^{T}$$
  • 式子中每一项的系数\(\sigma\)就是奇异值
  • \(u,v\)都是列向量,每一个\(uv^{T}\)都是秩为1的矩阵
  • 奇异值按照从小到大排列
• 从公式中按照从大到小排序后,保留前面系数最大的项目后效果
  • 对于一张450x333的图片,只需要保留前面的50项即可得到相当清晰的图像
  • 从保留项1到50,图片越来越清晰
• 结论:
  • 奇异值越大的项,越能体现出来图片的效果,奇异值隐含着某种对于A矩阵来说很重要的信息
  • 加权的秩一矩阵能体现整个大矩阵的值,奇异值就是对应秩一矩阵对于A矩阵的权重

线性变换方面

几何含义

• 对于任何的一个矩阵，我们要找到一组两两正交单位向量序列，使得矩阵作用在此向量序列上后得到新的向量序列保持两两正交.奇异值的几何含义为:这组变换后的新的向量序列的长度

更直观的几何含义

• 公式:
  $$E_{m}={y\in C^{m}: y=Ax, x\in C^{n},\left | x\right |_{2}=1}$$
• 二维矩阵A:
  • 矩阵A将二维平面中的单位圆变换为椭圆,而两个奇异值正好是椭圆的半轴长度.
• m维矩阵
  • 矩阵A将高维平面中的单位球变换为超椭球,矩阵的奇异值恰好就是超椭球的每条半轴长度.

调和级数的和是发散的,并不收敛,但是这又是一个非常常用的级数,本文总结了调和级数的和的求法

一个事实

• 调和级数的和与n的自然对数的差值收敛到欧拉-马歇罗尼常数
  $$
  \begin{align}
  lim_{n \to \infty}(\sum_{i=1}^{n}\frac{1}{i} - ln(n)) = \gamma
  \end{align}
  $$
  • \(\gamma\)为欧拉-马歇罗尼常数
    • (欧拉常数又称欧拉-马斯克若尼常数，近似值为γ≈0.57721 56649 01532 86060 65120 90082 40243 10421 59335)

证明

• 事实上,调和级数的和为
  $$
  \begin{align}
  \sum_{i=1}^{n}\frac{1}{i} = ln(n) + \gamma + \epsilon_{n}
  \end{align}
  $$
  • \(\gamma\)为欧拉-马歇罗尼常数
  • \(\epsilon_{n}\)约等于\(\frac{1}{2n}\),随着n的不断增大,\(\epsilon_{n}\)趋于0

补充

• 两个不同的调和数之间的差值永远不是整数
• 除了n=1时以外,没有任何一个调和数是整数

机器学习中的熵一般包括信息熵,条件熵,交叉熵几种

信息熵

为什么信息熵中有log?

参考博客:https://www.cnblogs.com/kyrieng/p/8694705.html

自信息\(I(x)\)

• 一条信息的信息量大小和它的不确定性有直接的关系, 信息量的度量就等于不确定性的多少
• 考虑一个离散随机变量\(x\),随机变量的信息量由概率分布\(p(x)\)确定
• 我们的目标是找到一个函数\(I(x) = f(p(x))\)(自变量是\(p(x)\),因为随机变量的信息量由概率分布确定),能够衡量\(x\)信息内容的多少
  • 且必须是概率分布\(p(x)\)的单调函数?
• 现在考虑同时出现两个相互独立的随机变量\(x\)和\(y\),那么他们的信息量和应该是
  $$I(x,y) = I(x)+I(y) = f(p(x)) + f(p(y))$$
  • 同时他们的联合概率分布为
    $$p(x,y) = p(x)p(y)$$
• 由上面的两个表达式可以知道\(f(\cdot)\)应该是一个对数相关的函数,因为
  $$log_{a}(MN) = log_{a}M + log_{a}N$$
• 所以我们可以考虑把原始信息量定义为
  $$I(x) = f(p(x)) = -log p(x)$$
  • 其中负号是用来保证信息量是正数或者零
  • log 函数基的选择是任意的（信息论中基常常选择为2，因此信息的单位为比特bits；而机器学习中基常常选择为自然常数，因此单位常常被称为奈特nats）
• \(I(x)\)也被称为随机变量\(x\)的自信息(self-information)，描述的是随机变量的某个事件发生所带来的信息量

信息熵\(H(x)\)

• 现在假设一个发送者想传送一个随机变量的值给接收者
• 那么在这个过程中，他们传输的平均信息量可以通过求 \(I(x)=−logp(x)\)关于概率分布\(p(x)\)的期望得到:
  $$
  \begin{align}
  H(x) &= \sum_{x}p(x)(-logp(x))
  &= -\sum_{x}p(x)logp(x)
  &= -\sum_{i=1}^{n}p(x_{i})logp(x_{i})
  \end{align}
  $$
• \(H(X)\)就被称为随机变量\(x\)的熵,它是表示随机变量不确定的度量，是对所有可能发生的事件产生的信息量的期望
• 从公式可得，随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大,当随机分布为均匀分布时，熵最大，且
  $$0 ≤ H(X) ≤ logn$$
  • 证明
    $$p(1)+p(2)+\dots+p(n)=1$$
  • 目标函数
    $$f(p(1),p(2),\dots,p(n))=-(p(1)logp(1)+p(2)logp(2)+\dots+p(n)logp(n))$$
  • 约束条件
    $$g(p(1),p(2),\dots,p(n),\lambda)=p(1)+p(2)+\dots+p(n)-1=0$$
  • 定义拉格朗日函数
    $$
    L(p(1),p(2),\dots,p(n),\lambda)=-(p(1)logp(1)+p(2)logp(2)+\dots+p(n)logp(n))+\lambda(p(1)+p(2)+\dots+p(n)-1)
    $$
  • 对\(p(i)\)和\(\lambda\)求偏导,并令其等于0得
    $$p(1)=p(2)=\dots=p(n)=\displaystyle\frac{1}{n}$$
  • 带入目标函数得
    $$
    \begin{align}
    f(\displaystyle\frac{1}{n},\frac{1}{n},\dots,\frac{1}{n}) &= -(\frac{1}{n}log\frac{1}{n} + \frac{1}{n}log\frac{1}{n} + \dots + \frac{1}{n}log\frac{1}{n})
    & = -log(\frac{1}{n})
    & = logn
    \end{align}
    $$

题目描述

• 餐馆有12生肖优惠券,每天给小明等概率随机发放一张,问: 小明集齐12中生肖优惠券的天数
• 相关延伸: 掷骰子, 要求每个面都出现一次, 求投掷次数的期望

问题求解

• 思路:

  • 把天数\(X\)这个随机变量变成12个随机变量的和$$X = \sum_{i=1}^{12}x_{i}$$
  • 于是可以把期望分解为12个随机变量的期望和$$E(X) = \sum_{i=1}^{12}E(x_{i})$$

• 第一种优惠券(12种中的任意一种均可):

  • 第一天随机拿到一个优惠券一定能够对应其中某一个生肖,概率为\(p_{1} = 1\)
  • 期望天数\(E(x_{1})\)与概率的关系为\(E(x_{1})\cdot p_{1} = 1\)
    • 一个直观的说明,为什么\(E(x_{1})\cdot p_{1} = 1\):由于每一天成功的概率为\(p_{1}\),不成功概率为\(1-p_{1}\),显然为二项分布,由二项分布的期望应该为1次,即\(np_{1}=1\),其中n就是我们天数的期望(注意:二项分布的期望与这里的天数期望不同,后者为使得二项分布期望为1所需要的天数)
    • 上面的证明不够严谨,严谨的数学证明如下:
      • 假设期望天数是 \(E\), 每天成功的概率为 \(p\), 下面我们求成功和不成功的概率分布
      • 第一天成功的概率为 \(p\), 成功时只需要 \(1\) 天即可, 即有 \(p\) 的概率需要 \(1\)天
      • 第一天没成功的概率为 \(1-p\), 不成功时需要将当前日子(\(1\)天)算上,然后回到原点,重新开始,即有 \(1-p\) 的概率需要 \(1+E\) 天
      • 期望公式
        $$E = p*1 + (1-p)(1+E)$$
      • 化简为:
        $$pE = 1$$
  • 需要天数的期望为$$E(x_{1}) = \frac{1}{p_{1}} = 1$$

• 第二种优惠券(11种中的任意一种均可):

  • 每天随机收到的优惠券有\(p_{2} = \frac{11}{12}\)的概率满足剩余的11个生肖中的一个
  • 期望天数\(E(x_{2})\)与概率的关系为\(x_{2}\cdot p_{2} = 1\)
  • 需要的天数期望为$$E(x_{2}) = \frac{1}{p_{2}} = \frac{12}{11}$$

• …

• 以此类推可得:
  $$
  \begin{align}
  E(X) &= \sum_{i=1}^{n}E(x_{i}) \\
  &= \sum_{i=0}^{11}\frac{12}{12-i} \\
  &= \sum_{i=1}^{12}\frac{12}{i} \\
  &= 12\sum_{i=1}^{12}\frac{1}{i} \\
  \end{align}
  $$

• 由于调和级数的和与n的自然对数有关系,详情参考调和级数的和
  $$
  \begin{align}
  \sum_{i=1}^{n}\frac{1}{i} = ln(n) + \gamma + \epsilon_{n}
  \end{align}
  $$

  • \(\gamma\)为欧拉-马歇罗尼常数,近似值为γ≈0.57721
  • \(\epsilon_{n}\)约等于\(\frac{1}{2n}\),随着n的不断增大,\(\epsilon_{n}\)趋于0

• 所以有
  $$
  \begin{align}
  E(X) &= 12\sum_{i=1}^{12}\frac{1}{i} \\
  &\approx 12(ln(12)+\gamma+\frac{1}{24})
  \end{align}
  $$

• 将12生肖推广到n,有
  $$
  \begin{align}
  E(X) &= n\sum_{i=1}^{n}\frac{1}{i} \\
  &\approx n(ln(n)+\gamma+\frac{1}{2n}) \\
  &\approx nln(n)
  \end{align}
  $$

寻找最优者：不可逆的做出选择，如何使得选到最优者的概率最大

题目描述

• 由于无人知道缘分何时到来,假设人的一生会遇到100个异性,这100个人参差不齐,其中有个人是最好的,100人随机的排着队出现,而我们对每个人必须决定是否接受,而且一旦决定后不能修改,那么用什么策略选择更有机会选到最好的那一个呢?

解决方案

策略设想

• 拒绝前k个人,然后从第k+1个开始,只要优于前面的所有人,则接受
• k值的设定比较难,太小了容易找到不好的,太多了容易错过最好的

证明

• 假设最优者出现在第\(i(k< i \leq n)\)个(事件A),那么最优者被选中(事件B)的概率为前i-1个中的最优者在前k个人中的概率
  $$ P(B|A) = \frac{k}{i-1} $$

  • \(P(B|A) = P(最优者被选中|第i个为最优者)\)

• 最优者出现在第\(i\)个的概率为
  $$P(B) = \frac{1}{n}$$

• 最优者被选中的概率为

• 接下来的证明用到了调和级数的和,详情参考调和级数的和
  $$
  \begin{align}
  \sum_{i=1}^{n}\frac{1}{i} = ln(n) + \gamma + \epsilon_{n}
  \end{align}
  $$

  • \(\gamma\)为欧拉-马歇罗尼常数,近似值为γ≈0.57721,下面的推导都不需要精确解的,所以可以使用该公式
  • \(\epsilon_{n}\)约等于\(\frac{1}{2n}\),随着n的不断增大,\(\epsilon_{n}\)趋于0
    $$
    \begin{align}
    P(B) &= \sum_{A}P(B,A) \\
    &= \sum_{A}P(B|A)P(A) \\
    &= \sum_{i=k+1}^{n}\frac{k}{i-1}\frac{1}{n} \\
    &= \sum_{i=k+1}^{n}\frac{k}{n}\frac{1}{i-1} \\
    &= \frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1} \\
    &= \frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i} \\
    &= \frac{k}{n}(\sum_{i=1}^{n-1}\frac{1}{i} - \sum_{i=1}^{k-1}\frac{1}{i}) \\
    &\approx \frac{k}{n}((ln(n-1)+C)-(ln(k-1)+C)) \\
    &= \frac{k}{n}ln(\frac{n-1}{k-1}) \\
    \end{align}
    $$

• 当n和k足够大时有

  • (不能证明k也会足够大,但是直觉上n足够大k也会足够大,因为n足够大时往往需要拒绝更多的人)
    $$\frac{n-1}{k-1} = \frac{n}{k}$$

• 令\(x=\frac{k}{n}\),则有
  $$
  \begin{align}
  f(x) &= xln\frac{1}{x} \\
  {f}’(x) &= ln(\frac{1}{x})+(-\frac{1}{x^2}\cdot x \cdot x) \\
  &= ln(\frac{1}{x})-1
  \end{align}
  $$

• 求\(f(x)\)的最大值,令\({f}’(x)=0\)有
  $$ ln(\frac{1}{x})-1 = 0 $$

• 解方程得
  $$ x = \frac{1}{e} $$

• 也就是说当\(\frac{k}{n} = \frac{1}{e} \)时,找到最优者的概率最大

策略描述

• 拒绝前\(\frac{n}{e}\)个人(也就是拒绝前37%的人),然后从第\(\frac{n}{e}+1\)个开始,只要优于前面的所有人,则接受
• 这种方式可以保证我们有最大的概率找到最优者

初始题目为1米长的绳子剪成三段后能够构成三角形的概率，实际上绳子的长度可以是任意的，解法都一样

题目描述

• 一根绳子长度为n，剪三段后能构成三角形的概率是多少？
• 由于长度与概率无关，所以接下来我们把绳子当做长度为1米来处理

解决方案

• 三段绳子的长度分别为x,y,1-x-y

• 首先需要满足
  $$
  \begin{align}
  x &> 0 \\
  y &> 0\\
  1-x-y &> 0 \\
  \end{align}
  $$

  • 以x为横坐标，y为纵坐标画图得到阴影区域面积为\(\frac{1}{2}\)

• 图片来源于：https://blog.csdn.net/fanoluo/article/details/40374571*

  

• 进一步分析三段绳子能生成组成三角形的概率
  $$
  \begin{align}
  x+y &> 1-x-y \\
  y + 1-x-y &> x\\
  x + 1-x-y &> y \\
  \end{align}
  $$

  • 进一步分析得到阴影部分面积为\(\frac{1}{8}\)

• 图片来源于：https://blog.csdn.net/fanoluo/article/details/40374571*

  

• 所以有
  $$P = \frac{1/8}{1/2} = \frac{1}{4}$$

和Java类似,Python实现了丰富的基本数据结构,但是使用方式和Java有所不同

字符类型

• Python中没有Java以及C++一样的字符类型,只有字符串类型

字符和数字的比较

• 'a'表示的不是字符’a’, 而是字符串”a”,也就是说0 < 'a'这样的写法是不可以的,因为'a'不是一个数字
• 若非要和数字比较,方式如下:

  1 2 3 4 5 6 7 8 9 10 11

  string = "12_abc*ABZ-=" alphanumeric_str = "" for char in string: if (ord(char) >= ord('0') and ord(char) <= ord('9'))\ or (ord(char) >= ord('a') and ord(char) <= ord('z'))\ or (ord(char) >= ord('A') and ord(char) <= ord('Z')): alphanumeric_str += char print(alphanumeric_str) # output: 12abcABZ

集合类型的复制

浅拷贝

以list为例

1
2
3
4
5
6
7
8

l = [1, 2, 3]
# method 1
lcopy = l[:] # notice: ls.append(l[:]), 添加的是副本!!!
# method 2
lcopy = l.copy()
# method 3
import copy
lcopy = copy.copy(l)

深拷贝

1
2
3
4

import copy

l = [1, 2, 3, [4, 5, 6]]
l = copy.deepcopy(l)

format函数的使用

• format是用于格化式字符串的函数

• format是字符串自带的函数

  1 2 3 4 5 6 7 8 9 10 11

  # format string print "{} {}".format("hello", "world") print "{0} {1}".format("hello", "world") print "{1} {0} {1}".format("hello", "world") # output 'hello world' 'hello world' 'world hello world' # format number print "{:.2f}".format(3.1415926)

• 其他使用方式之后再补充

字符串到数字的转换

1
2
3
4
5
6
7
8
9

# string to integer, int(str, base=10)
a = "101"
integer = int(a, 10)
integer = int(a, 2)
integer = int(a, 7)

# string to float, float(str)
b = "123.4"
f = float(b)

进制转换

转换示例

1
2
3
4
5
6
7
8
9

# binary, octonary, hexadecimal to decimal(from string)
dec_num = int("1001", 2) # or int("0b1001", 2)
dec_num = int("657", 8) # or int("0657", 8)
dec_num = int("ff", 16) # or int("0xff", 16)

# decimal to binary, octonary, hexadecimal(or string)
bin_num = bin(123) # or str(bin(123))
oct_num = oct(123) # or str(oct(123))
hex_num = hex(123) # or str(hex(123))

总结:

• 词的表示为十进制(123), 二进制(0b110), 八进制(0567), 十六进制(0xff1)
• 词的转换函数如下:

map函数的使用

定义

• Python3

  1	map(function, iterable, ...) -> map

• Python2

  1	map(function, iterable, ...) -> list

示例

1
2
3
4
5
6
7
8
9
10
11
12

# Python2
print map(lambda x: x**2, [1, 2, 3])
# output:
[1, 4, 9]

print map(lambda x, y: x+y, [1, 2, 3], [5, 6, 7])
# output:
[6, 8, 10]

# Python3
result = map(lambda x: x**2, [1, 2, 3])
print(list(result))

本文将介绍一般RNN,RNN的变种GRU(门控循环单元)和LSTM(长短期记忆网络)等神经网络结构

• LSTM原始论文: NIPS 2014, Sequence to Sequence Learning with Neural Networks
• GRU原始论文: EMNLP 2014, Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation

一般的RNN

循环神经网络(Recurrent Neural Network, RNN)

• 将神经单元展开后的示意图如下:

RNN与CNN优缺点比较

此处我们之比较CNN和RNN在序列预测问题中的优劣

• 关于前馈神经网络:
  • 是一种最简单的神经网络
  • 各神经元分层排列, 每个神经元只接受前一层的输入,输出到下一层,已知到输出层,
  • 整个网络中没有反馈(后面的backward求梯度不能算反馈,这里指一次输入到输出计算各层间没有反馈,数据流只能从上一层到下一层单向流动)
  • 可以用一个有向无环图表示
• CNN:
  • 是一种前馈神经网络(多层感知机),是多层感知机的变体
  • 采用固定大小的输入并生成固定大小的输出
  • CNN是图像和视频处理的理想选择
• RNN:
  • 不是前馈神经网络, 有环
  • 可以处理任意长度的输入输出
  • 使用时间序列信息,能用之前的状态影响下一个状态
  • RNN是文本和语音分析的理想选择
• RNN在处理序列信息的缺点:
  • 对短期输入非常敏感,但是对长期输入不敏感
  • 难以处理长文本中长距离的单词间的关系

LSTM

长短期记忆网络(Long Short-Term Memory, LSTM)

• 整体示意图如下:
• 核心是”(Gate)门”结构
  • 其中Sigmoid是输出0到1的数值,描述每个部分有多少量可以通过当前门
  • 0表示拒绝所有, 1表示接受所有

推导流程图

GRU

门控循环单元(Gated Recurrent Unit, GRU)

• 整体示意图及推导如下:

GRU与LSTM对比

• 二者提出的时间基本相同
• 都是用来解决RNN不能处理长期依赖的问题
• LSTM有三个”门”结构, GRU只有两个”门结构”
• GRU较简单,参数比较少,不容易过拟合, LSTM比较复杂一点,但是常用

• 参考博客: 一篇写得非常好的文章:深度学习激活函数的理解与总结

ReLU

修正线性单元(Rectified Linear Unit)

x为0时的导数问题

• 在实际场景中，x为0的概率非常低
• 实际场景中，当x为0时，原函数不可导，可以给此时的导数制定一个值，如0，或1
• 神经元永久死亡问题：https://www.zhihu.com/question/67151971
  • 当对于任意的训练样本，某一个神经元输出都小于0时，该神经元的反向梯度为0，所以神经元上层与神经元相连接的所有节点梯度都为0(链式法则，梯度相乘)，也就是对所有的训练样本，这些节点相关的参数都不会被更新(因为梯度为0)，下一次正向计算到这些节点时值都不会变
  • 一个常见的疑问：如果当前神经元上层的神经元其他参数发生改变而导致当前神经元的输入数据发生改变呢？
  • 回答：可能有这种情况，一个神经元的反向梯度为0以后，所有只与该层该神经元相关的参数都不会变了，但与该层其他神经元相关的节点参数还是会变的！【需要进一步探讨这个问题】
  • 补充回答：可以确定的是，如果当前层的其他神经元不影响该神经元上层的相关参数，那么，这个神经元将永久性死亡
  • 所以正确的描述是：对于任意的输入(不管当前层输入为何值时，当前神经元的输出都等于0，也就是说，虽然上层的输入可能会变，但是当前节点的输出已经不会变化了！)，都有当前神经元的输出等于0，此时反向梯度永远为0
  • 注意：这不是说神经元从开始就怎么样，而是神经元相关的参数偏向太多，导致当前神经元的值永远为0

某个用户的所有进程突然消失,top,ps aux,或者时pstree都看不到相关的进程
但cat /proc/进程pid/status能看到进程信息,且相关端口确实被进程占用