巴拿赫（Banach）空间是完备的赋范空间。

希尔伯特（Hilbert）空间是完备的内积空间。

因为可以通过范数来定义内积，所以内积空间也一定是赋范空间。

同理，希尔伯特空间也一定是巴拿赫空间。

我们可以用下面的韦氏图来表明这几种空间的区别和联系。

反证法。假设$\sqrt{2}$是有理数，那么存在互质的两个正整数$a$,$b$使得$\sqrt{2}=\frac{a}{b}$。

两边同时平方，可以得到$a^2=2b^2$。可见$a$必须是偶数，令$a=2k$，那么$4k^2=2b^2$。可得$b^2=2k^2$，所以$b$也必须是偶数。

$a$和$b$都是偶数，和互质矛盾，所以假设不成立。

sinx 和 x 的图像在无限接近0的地方斜率都是1 ，在0附近放大很多倍之后sinx和x图像几乎重合。

近似看成sinx=x，所以极限就是1了咯。虽然不是很严谨，但是够直观了吧233。

泰勒展开吧

$$\sin x = x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots$$

$$\frac{\sin x}{x }= 1-\frac{x^2}{3!}+\frac{x^4}{5!}-\frac{x^6}{7!}+\cdots=1+O(x^2)$$

所以当$x\rightarrow 0$，$\frac{\sin x}{x}\rightarrow 1$。

泰勒展开

学过高数的都知道，这是在比较两个无穷大。正确的描述应该是这样，对于给定的$k$，以下极限

$\lim_{n\rightarrow \infty}\frac{k^n}{n!}$是$0$还是常数还是无穷大。

这个极限显然是等于$0$的，写成这样，可能就一目了然了

$$\lim_{n\rightarrow \infty}\frac{k\times k\times k\times k\times \cdots \times k\times k\times k\times k\times \cdots \times k}{1\times 2\times 3\times 4\times \cdots \times k\times (k+1)\times (k+2)\times (k+3)\times \cdots \times n}$$

前面$k-1$项的乘积是分母小，因为$n\rightarrow\infty$，后面无穷多项是分母比分子大。希望能够帮到你～

牛顿法需要计算二阶导数，也就是说要计算一个Hessian矩阵。

• 有些时候，损失函数的二阶导数的显式方程未必那么好求。机器学习不同于传统的优化问题，前者的目标函数可能是自己的定义的，未必是光滑的。
• 机器学习问题与传统优化的另外一个区别是，前者的维数通常会很大，经常会上百或者上千乃至上万。如果数据集有n个特征，那么这个Hessian矩阵就是n x n的，我们需要求n平方个点，而sgd只需要求n个点。
• 当n很大的时候，我们需要存一个n x n的矩阵，在空间也会是一个负担。

其次，牛顿法的步长是通过导数计算而来的。所以当临近鞍点的时候，步长会变得越来越小，这样牛顿法就很容易陷入鞍点之中。而sgd的步长是预设的固定值，相对容易跨过一些鞍点。

首先我先说说梯度下降。

其实梯度下降法在机器学习中也极小被直接使用。通常使用的也是梯度下降的改进版本，比如随机梯度下降、小批量梯度下降、随机平均梯度下降等等。

下面说说牛顿法。

• 牛顿法需要二阶导数，也就是Hessian矩阵。
• 牛顿法需要Hessian矩阵正定，如果是非正定的话，牛顿法会陷在鞍点。
• 最重要的是，牛顿法的迭代中需要对Hessian矩阵求逆，$$x_{i+1} = x_i - H^{-1} \nabla_x J(x_{i})$$熟悉矩阵计算的朋友一定知道这件事有多昂贵。

败也萧何，败也萧何。牛顿法的优势也正是二阶收敛速度。所以就不少拟牛顿法，既保留二阶收敛速度，又尽量避免上面的缺陷。其中比较出名的，在机器学习中经常出现的有Broyden–Fletcher–Goldfarb–Shanno(BFGS)算法，它用低秩分解来代替求逆。后来还有的L-BFGS算法，降低了算法对内存的需求。对于很多多维机器学习问题，这个优势是很重要的。

所以说牛顿法的思想在机器学习的优化问题中依然是很常见的。

我觉得主要是因为牛顿法是二阶的，求二阶导数在大规模计算中应该是个很昂贵（费时间）的事情吧。

虽然牛顿法不常用，但是各种拟牛顿法还是层出不穷的呀

架不住计算量

严格说

np.matmul(a, b)

完全等价于

a @ b

只是表示方式不同。

对于矩阵乘法来说，

np.matmul(a, b)

也完全等价于

np.dot(a, b)

dot和matmul的区别是，当a或b其中一个是标量的时候，只能用np.dot，用matmul会报错。

是的。

假设$g(x)=f_1(x)+f_2(x)$是两个凸函数的和，因为凸函数的二阶导非负，所以

$$g''(x)=f''_1(x)+f''_2(x)\geq 0$$

$g(x)$就必须是凸函数。

对于任何凸函数$f(x)$，

$$f(\lambda x_1 +(1-\lambda)x_2)\leq \lambda f(x_1)+(1-\lambda)f(x_2)$$

令$g(x)=f_1(x)+f_2(x)$，其中$f_1(x),f_2(x)$是两个凸函数，那么

$$g(\lambda x_1 +(1-\lambda)x_2)=f_1(\lambda x_1 +(1-\lambda)x_2)+f_2(\lambda x_1 +(1-\lambda)x_2)$$

$$\leq\lambda f_1(x_1)+(1-\lambda)f_1(x_2)+\lambda f_2(x_1)+(1-\lambda)f_2(x_2)$$

$$=\lambda(f_1(x_1)+f_2(x_1))+(1-\lambda)(f_1(x_2)+f_2(x_2))$$

$$=\lambda g(x_1)+(1-\lambda)g(x_2)$$

所以$g(x)$肯定是凸函数。

介绍点资料，在Convex Optimization中，79页3.2，介绍了一些保持convex性质的操作。比如非负数的加权和（Nonnegative weighted sums）。感兴趣的了解下。

看到上面的答案里有人问“两个凹函数相减还是凹函数？”

这个显然不对，应该是“两个凹函数相加还是凹函数”。因为凹函数的二阶导数小于等于0。

两个凸函数相加：一定凸

两个凸函数相乘：不一定凸

两个凸函数相减：不一定凸

numpy里有linalg.eig直接计算特征值和特征向量。

例子

import numpy as np

>>> m = np.array([[1, 2], [0, 3]])

>>> m

array([[1, 2],

       [0, 3]])

>>> w, v = np.linalg.eig(m)

>>> w

array([ 1.,  3.])

>>> v

array([[ 1.        ,  0.70710678],

       [ 0.        ,  0.70710678]])

w是特征值

v是特征向量，这个例子里第一列对应1的特征向量，第二列对应3的特征向量。

使用 numpy 的 ndarry 对象

用numpy计算比较方便，虽然math里也有，但是math的输入值必须是单个数，不能是list或者array

>>> import numpy as np
# x可以是list或者np.ndarray
# cos(x)
>>> np.cos(x)
# sin(x)
>>> np.sin(x)
# tan(x)
>>> np.tan(x)
# acrcos(x)
>>> np.arccos(x)
# acrsin(x)
>>> np.arcsin(x)
# acrtan(x)
>>> np.arctan(x)
# cosh(x)
>>> np.cosh(x)
# sinh(x)
>>> np.sinh(x)
# tanh(x)
>>> np.tanh(x)

math里基本上都有了

>>> import math

# cos(x)

>>> math.cos(x)



# sin(x)

>>> math.sin(x)



# tan(x)

>>> math.tan(x)



# acrcos(x)

>>> math.acos(x)



# acrsin(x)

>>> math.asin(x)



# acrtan(x)

>>> math.atan(x)



# cosh(x)

>>> math.cosh(x)



# sinh(x)

>>> math.sinh(x)



# tanh(x)

>>> math.tanh(x)

scipy numpy

python中科学计算相关的基本上都在 scipy中，可以用来做最优化等。

scipy提供了Nelder-Mead，Newton, CG，Trust Region等相关的算法。

pyopt

利用公式$lcm(a,b)=ab/gcd(a,b)$

from math import gcd

def lcm(a,b): 

    prod = abs(a * b)

    gcd_ab = gcd(a,b)

    if gcd_ab == 0:

        return 0

    return int(prod / gcd_ab)

布朗桥是一种特殊的布朗运动。

如果一个布朗运动，从某点开始，并且在结束时回到起点，那么这个过程就称为布朗桥。

比如说一个股票的发行价是20块，经过了几年之后，股价在某一天又回到了20块，那么这个过程就是布朗桥。

下图就是一个例子

可以直接使用scipy

>>>from scipy.special import comb

>>>comb(10, 3, exact=True) #精确解

120

>>>comb(10, 3, exact=False) #近似解

120.0

自己写一个也不费事

def binom_coef(n, k):

    result = 1

    for i in range(n-k+1, n+1):

        result *= i

    for i in range(1, k+1):

        result /= i

    return result

例子

>>>binom_coef(5, 2)

10.0

>>>binom_coef(6, 1)

6.0

scipy.linalg.solve(A, b)

from scipy import linalg

x = linalg.solve(A, b)

提供两种解法：

1. 根据 http://sofasofa.io/forum_main_post.php?postid=1001963 的思路，得到公式

$(1-p)(x+1)+p(1-p)(x+2)+p^2(1-p)(x+3)+3p^3=x$

由 $p=1/2$ 得，$x=14$。

2. 根据 http://www.aquatutoring.org/ExpectedValueMarkovChains.pdf 的 Example 7 可直接得期望为 14。

令正面为H，背面为T

有4个状态，S1是开始或抛出反面（begin/T），S2是一个正面（H），S3:是连续抛出两个正面（HH），S4是连续抛出3个正面并结束（HHH）。

图来至

初始状态$x_0=[1,0,0,0]$，状态转移矩阵是

$$P=\begin{bmatrix}0.5 & 0.5 & 0 & 0\\0.5 & 0 & 0.5 & 0 \\ 0.5 & 0 & 0 & 0.5\\ 0 & 0 & 0 & 1\end{bmatrix}$$

$x_{t+1}=x_{t} P$

根据Markov Chain hitting time公式 定理1.3.5

$K_i^A $是状态i到状态A的步数的期望

$K_1^4 = 1 + \sum\limits_{j = 1,2,3} {{P_{1j}}K_j^4} =1+0.5K_1^4+0.5K_2^4$

$K_2^4 = 1 + \sum\limits_{j = 1,2,3} {{P_{2j}}K_j^4} =1+0.5K_1^4+0.5K_3^4$

$K_3^4 = 1 + \sum\limits_{j = 1,2,3} {{P_{3j}}K_j^4} =1+0.5K_1^4$

有$K_1^4=1+0.5K_1^4+0.5(1+0.5K_1^4+0.5(1+0.5K_1^4)$

最后$K_1^4=14$

用e表示，e后面跟着的表示是10的幂次

350000

3.5e5

0.002

2e-3

如果 $P$在$X$的column_space中就可以。先做SVD，$X=USV^T$，$rank(X)=r$。$U$是$n\times r$的标准正交基。

$$P^TX(X^TX)^{-1}X^TP$$

$$=P^TUSV^T(VSU^TUSV^T)^{-1}VSU^TP$$

$$=P^TUSV^TV(SS)^{-1}V^TVSU^TP$$

$$=P^TUU^TP$$

如果$P$能够被$U$的列向量表示，$P=UC$纯在$r\times 1$的解$C$，等式就成立。

np.identity(n)可以生成$n\times n$的单位矩阵

>>> np.identity(4)

array([[ 1.,  0.,  0.,  0.],

       [ 0.,  1.,  0.,  0.],

       [ 0.,  0.,  1.,  0.],

       [ 0.,  0.,  0.,  1.]])

或者也可以用np.diag生成对角阵

>>> np.diag([1] * 4)

array([[1, 0, 0, 0],

       [0, 1, 0, 0],

       [0, 0, 1, 0],

       [0, 0, 0, 1]])

最省事的是numpy.eye了，比numpy.identity还少打了几个字母，哈哈

np.eye(3)

array([[1., 0., 0.],
       [0., 1., 0.],
       [0., 0., 1.]])

直接

a.T

啊

import numpy as np

a = np.array([[1, 2, 3], [4, 5, 6]])
a = a.transpose()

转置后的a

array([[1, 2, 3],
       [4, 5, 6]])

要先把list类型转换成set类型，然后调用set.intersection

set.intersection(set(list1), set(list2))

最后返回的结果是个set

万能的numpy

import numpy
numpy.linalg.cond(A)

itertools是方便做循环的package

import itertools

result = list(itertools.product(*[A, B]))

得到的结果为

[('a', 1), ('a', 2), ('a', 3), ('b', 1), ('b', 2), ('b', 3)]

如果只是计算两个集合，可以直接用循环

[(x,y) for x in A for y in B]

如果多个集合计算笛卡尔积，itertools比较简明

numpy.transpose([numpy.tile(x, len(y)), numpy.repeat(y, len(x))])

用int函数转换，设置base为16，不过要注意输入值类型需要是str

num16 = '4e'

num10 = int(num16, 16)

num10的结果为

78

因为在求$f_t(x_i)$时，$y$和$\hat{y}$都是已知的，省去的项是常数，融合到最后的const中了。这两行的const不想等。

>>>my_list = [2, 3, 1, 5]
>>>import numpy as np
>>>np.prod(my_list)
30

也可以借助python的高级函数reduce

>>> from functools import reduce
>>> reduce(lambda x, y: x * y , [2, 3, 1, 5])
>>> 30

牛顿法求凸函数的最小值完全等价于牛顿法求这个凸函数的导函数唯一的根。

因为是凸函数，所以不存在马鞍点的情况。

和梯度下降类似，牛顿法也可能出现超调，也就是overshoot，这个是由函数本身的性质导致的。发生超调的话就很难收敛了。

牛顿法求最根需要有初始点，如果初始点不好，可能也会导致不收敛（其实也是超调）。

import numpy as np

a = np.matrix([[1, 1], [1, 1]])

try:

    a_inverse = a.I

    print('可逆')

except:

    print('不可逆')

提供两个思路

思路1：可逆矩阵的行列式不等于0，不可逆矩阵的行列式为0。可以利用numpy.linalg.det来算行列式

import numpy as np

M = np.array([[1, 1], [2, 2]])

if np.linalg.det(M) > 0:

    print('可逆')

else:

    print('不可逆')

思路2：可逆矩阵的秩是n，不可逆矩阵的秩小于n。可以利用numpy.linalg.matrix_rank来算秩

import numpy as np

M = np.array([[1, 1], [2, 2]])

if np.linalg.matrix_rank(M) == M.shape[0]:

    print('可逆')

else:

    print('不可逆')

矩阵的秩大于0就可逆，等于0就不可逆

求秩可参考：numpy求矩阵的秩

np.tile就是专门干这个事情的

import numpy as np

A = np.array([[1, 2], [3, 4]])

np.tile(A, (1, 2))

得到的就是

array([[1, 2, 1, 2],

       [3, 4, 3, 4]])

2行3列的话，就是

np.tile(A, (2, 3))

结果为

array([[1, 2, 1, 2, 1, 2],

       [3, 4, 3, 4, 3, 4],

       [1, 2, 1, 2, 1, 2],

       [3, 4, 3, 4, 3, 4]])

在$n$维空间中，一个$n-1$维的子空间就是称作一个超平面。超平面是平面的推广。

2维空间中，超平面是1维的，也就是线；3维空间中，超平面是2维的，也就是平面。

$n$维空间的超平面一定是可以用下面的式子表达的

$$a_1x_1+a_2x_2+\cdots+a_n x_n=b$$

$a_1,\cdots,a_n$是超平面公式的系数，不能全都为0。

>>> import numpy as np

>>> from scipy import sparse

>>> arr = np.array([[0,2,0],[0,0,3],[1,0,0],[0,0,4]])

# numpy array转成稀疏

>>> arr_sparse = sparse.csr_matrix(arr) 

# 稀疏矩阵转成numpy array

>>> arr_numpy = arr_sparse.A

可以对A遍历，如果A中的元素不在B中，那就不是子集

def IsSubset(A, B):

    for item in A:

        if item not in B:

            return False

    return True

调用上面的函数

IsSubset(['a'], ['b', 'a'])

返回True

如果A和B的交集还是A，那么A肯定是B的子集。

(set(A) & set(B)) == set(A)

数学上有对“光滑”的严格定义。

一个函数如果任意阶导数都是连续的，那么这个函数就是光滑的。一个显然的例子是$f(x)=e^x$以及多项式函数。

https://docs.scipy.org/doc/numpy/reference/generated/numpy.kron.html#numpy.kron

np.kron(a, b)

import numpy as np
outer_product = np.outer(x, y)

x和y是两个向量

有直接的转换关系 $i \tan (x)=\text{tanh}(ix)$

$i$是虚数$\sqrt{-1}$

不需要可导。是否是凸函数与是否可导没有直接关联。

$f(x)=|x|$就是凸函数，但是这个函数在0点并不可导。

拐点(inflection point)就是凹凸性的分界点。另外一个定义就是在拐点的左右两侧，它们的二阶导的符号相反。如果是光滑函数，拐点的二阶导为0。

拐点和极值点（驻点）不一样。极值点是一阶导为0。“疫情的拐点”应该就是指每日病例增长进入一个放缓的阶段。

“疫情的拐点”：指是新增病例虽然还是增加的，但是增加的速度放缓了

数据上拐点是一个二阶的属性。如果把一阶看作是速度的话，二阶就是加速度，加速度为0的地方就是拐点。拐点上是加速度从正到负，或者从负到正的点。

话说两年过去了，现在又在期待拐点了。

向量$u$在向量$v$上的投影长度应该等于

$$u \cos \theta = uv\frac{1}{|v|}=(10,11,-2) (0,3,4)\frac{1}{5}=5$$

根据泰勒展开公式，

$$f(x)=f(x_0)+\frac{(x-x_0)}{1!}f'(x_0)+\frac{(x-x_0)^2}{2!}f''(x_0)+\frac{(x-x_0)^3}{3!}f'''(x_0)+\cdots$$

针对$e^x$在$x_0=0$处展开

$$e^x = 1 + x + \frac{x^2}{2!}+\frac{x^3}{3!}+\cdots$$

如果$x=1$，那么

$$e=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\cdots$$

所以自然常数就是自然数阶乘的倒数的和。

---------------

也可以用Python验证一下

import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn')

approx = [1]
for i in range(1, 10):
    approx += [approx[-1] + 1/np.math.factorial(i)]

plt.plot(range(10), [np.math.e] * 10, label='e')
plt.plot(range(10), approx, marker='s', label='approximation')
plt.legend(fontsize=15)
plt.show()

图像如下

可以看出当加到$1/6!$的时候，两者就已经很接近了

无环图是就是没有环的图。

如果无环图是联通的，那么就是树(tree)；如果无环图是不连通的，那么就是多棵树，等价于森林(forest)

下图的例子是有环图(cyclic graph)和一个联通的无环图(acyclic graph)

DAG和AG不是同一个概念。DAG是指图里的边都是有方向的无环图。有向树(polytree)是DAG的一种。

举个例子，你应该就明白了：