算法之道

2017-02-01

一、算法基础

前言

时间有限，做个算法的入门。
对于算法而言，语言只是工具，重要的是思想（道）。
器术道用：易者，以用为妙。
建议循序渐进，《算法图解》/《labuladong的算法小抄》==>红宝书《算法》第4版（Robert Sedgewick）==>《数据结构与算法分析》（Mark Allen Weiss）==>《算法导论》（Thomas H.Cormen）。而不是刚学会了1+1=2，就直接上微积分。
算法的基础是数学。要学好数学，学好数学，学好数学。

算法

1、算法是什么？

是任何良定义的计算过程，根据输入产生输出。
万物皆算法，算法在慢慢统治世界。

2、为什么需要算法？

计算机也许是快的，但它们不是无限快。存储器也许是廉价的，但不是免费的。因此算法帮助我们有效的使用时间或空间等资源。

3、大部分算法是现成的，直接拿来用就好，为啥还要学习已有的算法？

数据结构、算法、编译原理、计算机体系结构等基础课程是“内功”，新的语言、技术、标准是“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。

真正学懂计算机的人都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。

时间复杂度

我们以插入排序的算法为例，解释时间复杂度计算。

def insertion_sort(list):          # 代价  次数
    for j in range(1,len(list)):    # c1    n (循环头会比循环体多执行1次)
        key =list[j]                # c2    n-1
        i=j-1                       # c4    n-1
        while i>=0 and list[i]>key: # c5    t(1)+t(2)+t(3)+...+t(j)，t(j)表示当值为j时循环次数，t(j)最坏情况执行j+1次，t(1)=2,t(2)=3,t(n-1)=n，最好情况执行1次。
            list[i+1]=list[i]       # c6    t(1)-1 + t(2)-1 +... t(j)-1，t(j)-1最坏情况执行j次，最好情况执行0次
            i=i-1                   # c7    t(1)-1 + t(2)-1 +... t(j)-1，同上一行
        list[i+1]=key               # c8    n-1
    return list

T(n)=c_1n+c_2(n-1)+c_4(n-1)+c_5\sum_{j=1}^{n-1}t_j

+c_6\sum_{j=1}^{n-1}(t_j-1)+c_7\sum_{j=1}^{n-1}(t_j-1)+c_8(n-1)

最佳情况运行时间，可以看出是n的线性函数。

T(n)=c_1n+c_2(n-1)+c_4(n-1)+c_5(n-1)+c_8(n-1)

=(c_1+c_2+c_4+c_5+c_8)n-(c_2+c_4+c_5+c_8)

最坏情况运行时间：

\sum_{j=1}^{n-1}(t_j)=\dfrac{n(n+1)}{2}-1

还有：

\sum_{j=1}^{n-1}(t_j-1)=\dfrac{n(n-1)}{2}

得出是n的二次函数。

T(n)=(\dfrac{c_5}{2}+\dfrac{c_6}{2}+\dfrac{c_7}{2})n^2+(c_1+c_2+c_4+\dfrac{c_5}{2}-\dfrac{c_6}{2}-\dfrac{c_7}{2}+c_8)n-(c_2+c_4+c_5+c_8)

函数的增长

1、Θ记号

Theta记号渐进给出一个函数的上界和下界。
我们已经使用过渐进记号 $\Theta$ 来表示增长量级，该记号适用于函数，例如插入排序的运行时间： $\Theta(n^2)=an^2+bn+c$

2、O记号

当只有一个渐进上界时，使用O记号。

按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(lgn),线性阶O(n), 线性对数阶O(nlgn),平方阶O(n^2)，立方阶O(n^3)… k次方阶O(n^k)，指数阶O(2^n)，阶乘阶O(n!)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

二、算法和排序

归并排序（Merge Sort）

许多算法结构上是递归的，遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。分治模式在每层递归时有三个步骤：分解、解决、合并。

分治算法运行时间的递归式为：T(n)是规模为n的一个问题的运行时间，如问题规模足够小，当n<=c（某个常量）时，直接求解需要常量时间，协作 $\Theta(1)$ 。把原问题分解成a个子问题，每个子问题的规模是原问题的1/b（对归并排序，a和b都为2）。为了求解子问题，需要T(n/b)的时间，分解问题需要的时间D(n)，合并子问题需要的时间C(n)，则可得到递归式：

T(n)= \begin{cases} \Theta(1) &\text{if } n \le c \\ aT(n/b)+D(n)+C(n) &\text{if } n>c \end{cases}

具体到递归排序，分解运行时间如下：

分解：D(n)= $\Theta(1)$ 。
解决：2T(n/2)
合并：C(n)= $\Theta(n)$ 。

递归排序的最坏运行时间T(n)的递归式：

T(n)= \begin{cases} c &\text{if } n=1 \\ 2T(n/2)+cn &\text{if } n>1 \end{cases}

递归式求解如下：

第一层为1个cn，第二层为2个2/cn，第lgn层为n个c，因此递归式总体运行时间为cn lgn+cn。

快速排序（Quick Sort）

名字简单粗暴，就是快，尤其是数据量巨大的情况下。通常是实际排序应用中最好的选择，因为它平均性能非常好，期望时间复杂度为O（nlgn），且隐含的常数因子非常小。

快速排序的基本思想：和归并一样使用了分治思想。快速排序的性能取决于划分是否平衡。

从排序算法开始

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	In-place	不稳定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	稳定
归并排序	O(n lgn)	O(n lgn)	O(n lgn)	O(n)	Out-place	稳定
堆排序	O(n lgn)	O(n lgn)	O(n lgn)	O(1)	In-place	不稳定
快速排序	O(n lgn)	O(n lgn)	O(n^2)	O(lgn)	In-place	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	Out-place	稳定
基数排序	O(d(n+k))	O(d(n+k))	O(d(n+k))	O(n+k)	Out-place	稳定
桶排序	O(n+k)	O(n+k)	O(n^2)	O(n+k)	Out-place	稳定
希尔排序	O(n lgn)	O(n lg^2 n)	O(n lg^2 n)	O(1)	In-place	不稳定

指标解释如下:

n代表数据规模，^代表几次方，lg为以2为底的log对数，O代表时间复杂度函数的渐进上界。k代表桶的个数（计数排序的排序值或者基数排序的每一位的取值个数），d代表排序值的位数。
稳定性：（1）稳定：如果a原本在b前面且a=b，排序之后a仍然在b的前面。（2）不稳定：排序之后a可能会出现在b的后面。
排序方式：（1）In-place：原址的，占用常数内存，不占用额外内存。（2）Out-place：占用额外内存。
时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。

我们往往只求最坏情况运行时间，原因在于，

一个算法的最坏情况运行时间给出了任意输入的运行时间的上界，不会变的更坏。
对某些算法，最坏情况经常出现。
平均情况往往与最坏情况大致一样差。

综合使用

JDK8的Arrays.sort方法，采用插入排序，快速排序，归并排序三种排序的组合。

小于47个元素，直接使用插入排序。
大于47个元素且小于286个元素，直接用快速排序。
大于286个元素且降序分组大于67（不具备结构），则使用快速排序。
大于286个元素且降序分组小于67（具备结构），则使用归并排序。

三、算法和数据结构

按照Pascal之父沃斯的话，程序 = 算法 + 数据结构。

两者密不可分，算法是基于某种数据结构，快速高效的实现数据操作的方法。

数据结构是底层，算法高层
数据结构为算法提供服务
算法围绕数据结构操作

常用的数据结构有：

数组（Array）
链表（Linked List）
栈（Stack）
队列（Queue）
树（Tree）
堆（Heap）
图（Graph）
散列表（哈希表）（Hash）

迪杰斯特拉（Dijkstra）算法

案例：北京地铁两站间最短路线

四、算法和加密

加密算法

加密算法首先分为两种：单向加密、双向加密

双向加密技术通常分为两大类:”对称式”和”非对称式”，用来对敏感数据等信息进行加密。

对称式加密算法有：DES、3DES、AES
非对称性加密算法有：RSA、DSA、ECC

单项加密算法主要是散列算法，有：MD5、SHA1、HMAC

用途：主要用于验证，防止信息被修。具体用途如：文件校验、数字签名、鉴权协议。

HTTPS

HTTPS解决的问题是：A客户端与B服务器端通信的内容，有且只有A和B有能力看到通信的真正内容。

问几个为什么：

1、怎么保证安全？加密，比如使用对称加密和非对称加密。对称加密速度快、效率高。非对称加密计算量大、效率低。由于效率问题，我们先从对称加密入手。

2、那先只使用对称加密是否能保证安全？当HTTPS使用对称加密时，秘钥的管理和传输是个问题，会被泄漏。

3、怎么保证对称加密的秘钥安全？使用非对称机加密。私钥只有服务端有，而公钥可以发给所有的客户端。非对称加密需要解决的是密钥传输问题。

4、那么混合使用对称加密和非对称加密是否安全？不安全，因为非对称加密的公钥发送给客户端时，可能被中间人掉包。中间人用自己的假公钥替换掉服务端的真公钥，然后用假私钥解密后篡改，用真公钥加密，使得客户端最后用假公钥解密的内容会出现篡改。

5、怎么解决公钥被掉包的问题？涉及到密码学的身份验证问题，即客户端验证返回公钥的是真服务器还是中间人。所以，我们不能直接将服务器的公钥传递给客户端，而是第三方机构使用它的私钥对我们的公钥进行加密后，再传给客户端。客户端再使用第三方机构的公钥进行解密。以上的过程其实是数字证书的本质。数字证书中包含了服务器的公钥，这个公钥被第三方机构的私钥加密了。

RSA

由麻省理工学院的Ron Rivest、Adi Shamir、Leonard Adleman提出，是一个支持变长密钥的公共密钥算法，需要加密的文件块的长度也是可变的。

对于RSA的原理理解，需要的数学知识包含互质、欧拉函数、欧拉定理、模反元素。

RSA密钥生成步骤：

1、求N

使用伪随机数生成器生成p和q，p和q都是质数，N=p * q

2、求φ(N)（欧拉函数）

φ(N) = φ(p * q) = φ(p)φ(q)=(p-1)(q-1)

3、求E

要求1<E<φ(N)，且E和φ(N)互质。实际应用中，常常选择65537。

4、求E对于φ(N)的模反元素D

要求1<D<φ(N)，且E * D mod φ(N)=1

5、公钥和私钥

将N和E放入公钥，将N和D放入私钥。

6、可靠性验证

回顾我们一共生成了六个数字：p、q、N、φ(N)、E、D，这六个数字之中，公钥用到了两个（N和E），其余四个数字都是不公开的。其中最关键的是D，因为N和D组成了私钥，一旦D泄漏，就等于私钥泄漏。那么，有无可能在已知N和E的情况下，推导出D？

E * D mod φ(N)=1。只有知道E和φ(N)，才能算出D
φ(N)=(p-1)(q-1)。只有知道p和q，才能算出φ(N)
N=pq。只有将N因数分解，才能算出p和q

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。但是如果N很大，即以现有计算能力，还无法被因数分解。正是基于这个数学上的难题，因此可以公开密钥算法。

目前针对RSA流行的攻击一般都是基于大数因式分解。目前编号为RSA-768的数被成功分解，威胁到现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。

此外量子计算的秀尔算法能使穷举的效率大大的提高。一个拥有N量子比特的量子计算机，每次可进行2^N次运算，理论上讲，密钥为1024位长的RSA算法，用一台512量子比特位的量子计算机在1秒内即可破解。

五、KNN算法

简介

k近邻法(k-nearest neighbor,k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的算法的描述为：

计算测试数据与各个训练数据之间的距离（欧式距离或曼哈顿距离）；
按照距离的递增关系进行排序；
选取距离最小的K个点；
确定前K个点所在类别的出现频率；
返回前K个点中出现频率最高的类别作为测试数据的预测分类。

优点：

精度高
对异常值不敏感
无数据输入假定

缺点：

计算复杂度高
空间复杂度高

案例1：电影分类

根据电影的打斗镜头和接吻镜头，来判定电影类型

电影	打斗镜头	接吻镜头	电影类型
电影1	3	104	爱情片
电影2	2	100	爱情片
电影3	1	81	爱情片
电影4	101	10	动作片
电影5	99	5	动作片
电影6	98	2	动作片
？	18	90	？

采用欧式距离（可理解为直线距离）计算未知电影和已知的距离，当前示例有2个特征，为2维空间，通过计算可得：

电影	与未知电影的距离
电影1	20.5
电影2	18.7
电影3	19.2
电影4	115.3
电影5	117.4
电影6	118.9

假定k=3，则3个靠近的电影依次是电影2、电影3和电影1，这三部电影都是爱情片，则我们判定未知电影是爱情片。

案例2：识别手写数字

如何使用KNN算法识别手写数字？

六、朴素贝叶斯算法

假设和公式

朴素贝叶斯是贝叶斯决策理论的一部分，我们称之为“朴素”(native)，是因为整个形式化过程只做最原始、最简单的假设。朴素贝叶斯分类器中的假设是：

每个特征都是独立的
每个特征同等重要

贝叶斯决策理论的核心思想是，分类时，我们会选择高概率对应的类别，即选择具有最高概率的决策。

P(B_i|A)= \dfrac{P(B_i)P(A|B_i)}{\sum_{i=1}^n{P(B_i)P(A | B_i)}}

可得到如下形式：

P(A|B)= \dfrac{P(A)P(B|A)}{P(B)}

怎么理解？

P(A)称为”先验概率”（Prior probability），即在B事件发生之前，我们对A事件概率的一个判断。
P(A|B)称为”后验概率”（Posterior probability），即在B事件发生之后，我们对A事件概率的重新评估。
P(B|A)/P(B)称为”可能性函数”（Likelyhood），这是一个调整因子，使得预估概率更接近真实概率。

所以，条件概率可以理解成下面的式子：

后验概率　＝　先验概率ｘ调整因子

这就是贝叶斯推断的含义。我们先预估一个”先验概率”，然后加入实验结果，看这个实验到底是增强还是削弱了”先验概率”，由此得到更接近事实的”后验概率”。

在这里，如果”可能性函数”P(B|A)/P(B)>1，意味着”先验概率”被增强，事件A的发生的可能性变大；如果”可能性函数”=1，意味着B事件无助于判断事件A的可能性；如果”可能性函数”<1，意味着”先验概率”被削弱，事件A的可能性变小。

为方便理解上述公式，对于规律总结来讲，可写成：

P(规律|现象)=P(现象|规律)P(规律)/P(现象)

对于分类任务来讲，可写成：

P(类别|特征)=P(特征|类别)P(类别)/P(特征)

案例1

男士的条件会影响到女士是否愿意嫁，数据如下：

样貌	性格	身高	上进心	嫁不嫁
帅	不好	矮	不上进	不嫁
不帅	好	矮	上进	不嫁
帅	好	矮	上进	嫁
不帅	好	高	上进	嫁
帅	不好	矮	上进	不嫁
不帅	不好	矮	不上进	不嫁
帅	好	高	不上进	嫁
不帅	好	高	上进	嫁
帅	好	高	上进	嫁
不帅	不好	高	上进	嫁
帅	好	矮	不上进	不嫁
帅	好	矮	不上进	不嫁

那么有一个男生，四个特点分别是不帅，性格不好，身高矮，不上进，请你判断（分类）一下女生是嫁还是不嫁？

问题可以变为P(嫁|不帅,性格不好,矮,不上进) 和P(不嫁|不帅,性格不好,矮,不上进) 这两个概率哪个高？

根据贝叶斯公式，有以下2个：

1、P(嫁|不帅,性格不好,矮,不上进) = P(嫁) × P(不帅,性格不好,矮,不上进|嫁)/P(不帅,性格不好,矮,不上进)

2、P(不嫁|不帅,性格不好,矮,不上进) = P(不嫁) × P(不帅,性格不好,矮,不上进|不嫁)/P(不帅,性格不好,矮,不上进)

P(嫁)=P(不嫁)=6/12
P(不帅,性格不好,矮,不上进|嫁)这个是联合概率，=P(不帅|嫁) × P(性格不好|嫁) × P(矮|嫁) × P(不上进|嫁)=1/2 × 1/6 × 1/6 × 1/6 =1/432
P(不帅,性格不好,矮,不上进|不嫁)=P(不帅|不嫁) × P(性格不好|不嫁) × P(矮|不嫁) × P(不上进|不嫁)=1/3 × 1/2 × 1 × 2/3 =1/9
P(不帅,性格不好,矮,不上进)套用全概率公式，=P(嫁) × P(不帅,性格不好,矮,不上进|嫁)+ P(嫁) × P(不帅,性格不好,矮,不上进|不嫁)=1/2 × 1/392 + 1/2 × 1/9=49/392

可得出P(嫁|不帅,性格不好,矮,不上进) =(1/432)/(49/432)=1/49，P(不嫁|不帅,性格不好,矮,不上进)==(1/9)/(49/432)=48/49。可以看出不嫁的概率远远大于嫁的概率。

案例2：垃圾邮件过滤

怎么判断一封邮件是否是垃圾邮件？

七、线性回归算法

基本概念

1、回归

回归用于预测输入变量和输出变量之间的关系，目的是预测数值型的目标值。
回归模型（回归方程）是表示输入变量到输出变量之间映射的函数。
回归问题分为模型的学习和预测两个过程。基于给定的训练数据集构建一个模型，根据新的输入数据预测相应的输出。
回归问题按照输入变量的个数可以分为一元回归和多元回归；按照输入变量和输出变量之间关系的类型，可以分为线性回归和非线性回归。如果你和的线是一条直线，则被称为线性回归。非线性回归有常用的逻辑回归模型。

2、线性回归（linear regression）

一元线性回归最简单：y=ax+b(x为价格，y为销量，则该线性回归用来描述价格与销量的关系，一元代表输入只有一个维度-价格，求a和b的值)

多元回归，代表输入有多个维度。

可以用最小二乘法，梯度下降法求解线性预测函数的系数

3、逻辑回归（logistic regression）

逻辑回归的模型是一个非线性模型，它本质上又是一个线性回归模型，因为通过sigmoid映射函数（又称逻辑回归函数）关系，转换成线性回归问题来解决。

案例1

有数据如下，需要计算最优回归系数。

x0-偏移量	x1-x轴	x2-y轴
1.000000	0.067732	3.176513
1.000000	0.427810	3.816464
…	…	…
1.000000	0.995731	4.550095
1.000000	0.738336	4.256571
1.000000	0.981083	4.560815

案例2

北京房价预测分析

八、算法小结

五大通用算法：

分而治之（递归）
贪心
动态规划
穷举（大力出奇迹）
回朔法/分支界定法

机器学习算法：

推荐算法：协同过滤
支持向量机
决策树

九、附录：数学相关

无穷大之比较

无穷大从小到大，其中a1,a2,a3大于1

序号	数列
1	$\ln{n}$
2	$n^{1/a_1}$
3	n
4	$n^{a_2}$
5	$a_3^n$
6	n!
7	$n^n$

素数和素性测试

素数，是除了1和自己以外没有除数的自然数。

大素数检测，如果需要枚举mod不现实。可使用费马素性检测来解决，它用来判断数字是素数的可能性的大小。

当p为prime number素数时，对于n<p，有n^p mod p =n，被称为费马小定理。

匹配得到确认的次数越多，素数的可能性就越高。

实例：5是素数

4^5=1024 mode 5=4
3^5=243 mode 5=3
2^5=32 mode 5=2
1^5=1 mode 5=1

欧拉函数

N以内有多少个小于等于N的正整数与N互质呢？

\varphi(x)=x\prod_{i=1}^n(1-\dfrac{1}{p_i})

其中p1, p2…pn为x的所有质因数，x是不为0的整数。

欧拉函数是积性函数，若m,n互质，则φ(mn)=φ(m)φ(n)。

实例：

φ(1)=1。和1互质的数(小于等于1)就是1本身。
φ(12)=φ(2^2 * 3^1)=12 * (1-1/2)* (1-1/3) = 4。

欧拉定理

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

a^{\varphi(n)} \equiv 1 (mod n)

a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。

比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）

模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除。这时，b就叫做a的“模反元素”。

边缘概率（又称先验概率）：某个事件发生的概率。边缘概率是这样得到的：在联合概率中，把最终结果中那些不需要的事件通过合并成它们的全概率，而消去它们（对离散随机变量用求和得全概率，对连续随机变量用积分得全概率），这称为边缘化（marginalization），比如A的边缘概率表示为P(A)，B的边缘概率表示为P(B)。

联合概率，表示两个事件A和B共同发生的概率，记为P(AB),P(A,B)或P(A ∩ B)。

条件概率（又称后验概率）

条件概率，就是事件A在另外一个事件B已经发生条件下的发生概率，记为P(A | B)，读作“在B条件下A的概率”。根据定义，可得出P(A | B)=P(A ∩ B)/P(B)。

证明：样本空间有N个等可能的基本事件，随机事件A包含M1个事件，B包含M2个事件。设A和B的联合概率包含M个事件（M是M1和M2的共有事件），则P(A ∩ B)=M/N。有P(A|B)=M/M2=M/N / M2/N=P(AB)/P(B)。

实例：100件产品中有5件不合格品，不合格品中又有3件是次品，2件是废品。设A表示“抽到的产品是次品”，B表示“抽到的产品是不合格品”。5件不合格品种有3件次品，则P(A|B)=3/5。P(B)=5/100。
同时是不合格品和次品的联合概率：P(A ∩ B)=3/100。

概率的加法定理：

P(A ∪ B)=P(A)+P(B)-P(A,B)

概率的乘法公式：

P(AB)=P(A)P(B|A)=P(B)P(A|B)

全概率公式

设Ω为实验E的样本空间，B1,B2,…,Bn为一组事件，两两互不相容且并集为全集，则称B1,B2,…,Bn是样本空间Ω的一个划分。且P(Bi)>0，则有公式：

P(A)=\sum_{i=1}^n{P(B_i)P(A | B_i)}

贝叶斯定理（Bayes’ theorem）

根据概率乘法定理，有

P(A)P(B_i|A)=P(B_i)P(A|B_i)

得到

P(B_i|A)= \dfrac{P(B_i)P(A|B_i)}{P(A)}

再根据全概率公式，得到

P(B_i|A)= \dfrac{P(B_i)P(A|B_i)}{\sum_{i=1}^n{P(B_i)P(A | B_i)}}

最小二乘法

最小二乘法适用于任意多维度的线性回归参数求解，它可求解出一组最优解，使得对于样本集中的每一个样本，用y=f(x1,x2,…xi,…xn)来预测样本，使得预测值与实际值的方差最小。

1、模型公式

h_{\theta}(x) = \sum_{i=0}^m{\theta_i x_i}=\theta^T X

θ和X都是列向量。

2、目标函数（损失函数）

根据最小二乘法定义，目标函数表示是预测值和真实值的差距。

J(\theta) = \dfrac{1}{2} \sum_{i=0}^m (h_{\theta}(x_i)-y_i)^2

直观的理解，为了避免正负抵消，是每个样本值与全体样本值的平均数之差的平方，和方差类似。如通过模型函数推导，较为复杂：

多维参数的数学推导

首先模型函数包含噪音项，根据中心极限定理，满足均值为0的高斯分布

\varepsilon_i \sim N(0,\sigma^2)

有：

\varepsilon_i =y_i-\theta^T x_i

高斯分布表示如下：

p(y_i|x_i;\theta)=\dfrac{1}{\sqrt{2\pi}\sigma}e^{(- \dfrac{(y_i-\theta^T x_i)^2}{2\sigma^2})}

通过极大似然MLE求得似然函数为所有样本的乘积

L(\theta) = \prod_{i=1}^m p(y_i|x_i;\theta) = \prod_{i=1}^m \dfrac{1}{\sqrt{2\pi}\sigma}e^{(- \dfrac{(y_i-\theta^T x_i)^2}{2\sigma^2})}

求log，将极大似然最大值转为log函数的最大值，

l(\theta) = \log{L(\theta)} =\log{\prod_{i=1}^m \dfrac{1}{\sqrt{2\pi}\sigma}e^{(- \dfrac{(y_i-\theta^T x_i)^2}{2\sigma^2})}} = \sum_{i=0}^m \log{\dfrac{1}{\sqrt{2\pi}\sigma}e^{(- \dfrac{(y_i-\theta^T x_i)^2}{2\sigma^2})}}

= m \log{ \dfrac{1}{\sqrt{2\pi}\sigma}} - \dfrac{1}{\sigma^2} \dfrac{1}{2} \sum_{i=0}^m (y_i-\theta^T x_i)^2

要使得最大似然最大，则需要最小二乘最小。有：

J(\theta) = \dfrac{1}{2} \sum_{i=0}^m (h_{\theta}(x_i)-y_i)^2 = \dfrac{1}{2} (X\theta-y)^T(X\theta-y)

得出

\dfrac{dJ(\theta)}{d\theta} = X^T X\theta-X^T y

当矩阵满秩时，求导后取极值点，令函数值为0，得出

\theta = (X^T X)^{-1} X^T y

矩阵的转置

将m×n的矩阵 $A=(a_{ij})_{m \times n}$ 的行换成同序数的列得到的一个n×m矩阵，称为A的转置矩阵，记作 $A^T$

有以下规律:
1、 $(A^T)^T=A$

2、 $(A+B)^T=A^T+B^T$

3、 $(\lambda A)^T=\lambda A^T$

4、 $(AB)^T=B^T A^T$

逆矩阵和伴随矩阵

设A为n阶矩阵，若存在另一个n阶矩阵B，使得： AB=BA=E（单位矩阵），则我们称B是A的逆矩阵，而A则被称为可逆矩阵。

设A为n阶矩阵，记

A^*=\begin{bmatrix} A_{11} & A_{21} & \cdots & A_{n1} \\ A_{12} & A_{22} & \cdots & A_{n2} \\ \vdots & \vdots & & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{nn} \\ \end{bmatrix}

其中，

A_{ij}

是|A|的元素

a_{ij}

的代数余子式，

A^*

称为A的伴随矩阵。

有 $AA^*=A^T A=|A|E$ ，则n阶方阵A可逆的充分必要条件是|A|不等于0，且有 $A^{-1}=\dfrac{1}{|A|}A^*$

奇异矩阵不可逆。

矩阵的秩

矩阵中的最大的不相关的向量的个数，就叫秩。

设在m×n的矩阵A中，任取k行k列（k<=min{m,n}），位于这些行列交叉处的k^2个元素按照原来次序构成的k阶行列式，称为A的k阶子式。A中有不等于0的r阶子式D，且所有的r+1阶子式（存在的话）全为0，则D称为矩阵A的最高阶非0子式，数r称为矩阵A的秩，记作R(A)。