题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

Solution with iteration:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        bool result = false;
        int m = array.size(), n = array[0].size();
        int row = 0, col = n - 1;
        while(row < m && col >= 0){
            if(array[row][col] == target){
                result = true;
                break;
            }
                 
            else if(array[row][col] < target)
                row ++;
            else
                col --;
        }
        return
         
    }
};

Solution with recursion:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        if(array.size() == 0)
            return false;
        return recursion(array, target, 0, array[0].size() - 1);
    }
    bool recursion(vector<vector<int>> array, int target, int row, int col){
        if(row == array.size() || col == -1)
            return false;
        if(array[row][col] == target)
            return true;
        else if(array[row][col] > target)
            return recursion(array, target, row, col-1);
        else
            return recursion(array, target, row+1, col);
       
        
    }
};

在统计学习理论中有一个很基础的不等式：Hoeffding不等式，这个不等式是大数定律的一种形式。大数定律中最简单的不等式应该就是Chebyshev不等式了。我们今天来证明一下它，以及给出线性bound的几个推论：

Chebyshev不等式：假设t是非负随机变量，对于任意的$\alpha>0$，我们都有：$P[t\geq \alpha]\leq \frac{E \left(t\right)}{\alpha}$

证明如下：
我们定义一个集合$A\subset \Omega:A=\{t\in \Omega | t\geq a\}$,因此：

$$E\left(t\right)=\sum_{t\in \Omega}P\left(t\right)t=\sum_{t\in A}P\left(t\right)t+\sum_{t\notin A}P\left(t\right)t\leq \sum_{t\in A}P\left(t\right)t\\
\leq\sum_{t\in A}P\left(t\right)a = a P\left(A\right)$$
得证！
下面是俩推论：
1.随机变量$u$的均值是$\mu$，方差是$\sigma ^2$，因此可得，对任意$\alpha$，$P[\left(u-\mu\right)^2\geq \alpha]\leq \frac{\sigma^2}{\alpha}$
2.$u_1,u_2,…,u_N$是独立同分布的一组随机变量，每一个变量的均值都是$\mu$，方差是$\sigma^2$，定义新的随机变量$u=\frac{1}{N}\sum_{n=1}^{N}u_n$，对任意的$\alpha>0$，都有：$P[\left(u-\mu\right)^2\geq \alpha]\leq \frac{\sigma^2}{N\alpha}$

续上，这篇博客我们来讨论一下基于迭代策略的词向量的学习。主要想介绍一下四个相关的神经网络来学词向量。

1. 语言模型（Language Modeling）

所有用在NLP中的神经网络模型都是基于语言模型来构建的。我们知道，一篇文章是由一系列的句子组成，每个句子都是由一系列的词组成。我们现在有单独的词（Atom），我们希望构建一系列的句子，从而构建整篇文章。在自然语言处理中有一个很出名的模型叫做N-gram 模型，它是将马尔科夫假设（Makov Assumptions）用在句子的生成过程中。例如这么一个句子：

I am a graduate student in ShanghaiTech University.

1.1.单纯的词袋模型（Bag of Words）

有图有真相！前一阵在微博上面看到下面的这个图很有意思。

BoW是指，所有的词之间相互没有关系，即在构建整个句子中不考虑词与词的顺序。因此，上面的句子跟下面的句子本质上表达的意义相同：

University student am graduate I ShanghaiTech a in.

这看起来很荒唐，但实际上像上一篇博客所说的LDA模型就是这么做的，在做主题建模时work的非常好。当然，这是看应用的。在复杂的问题下如何做出正确的Assumption正是Machine Learning想要研究的问题。对于上面这个句子，我们计算产生它的概率，可以通过这些词的联合概率来计算：
$$P\left(w^{(1)},w^{(2)},…,w^{(n)}\right)=\prod_{i=1}^{n}P\left(w^{(i)}\right)$$

但是，在产生句子这个问题时，Bags of Words模型肯定不够好，因为人在理解一句话中的某个词都会依靠其上下文的关系。因此我们可以把词与其前面n-1个词的关系加进来，这就是n-gram模型。

1.2.Binary Gram & Triple Gram

很简单，在计算一个句子产生的概率时把每个词与其前面n-1个词的关系考虑进来，可以得到：
Binary Gram:$P\left(w^{(1)},w^{(2)},…,w^{(n)}\right)=\prod_{i=2}^{n}P\left(w^{(i)}|w^{(i-1)}\right)P\left(w^{(1)}\right)$
Triple Gram:$P\left(w^{(1)},w^{(2)},…,w^{(n)}\right)=\prod_{i=3}^{n}P\left(w^{(i)}|w^{(i-1)},w^{(i-2)}\right)P\left(w^{(2)}|w^{(1)}\right)P\left(w^{(1)}\right)$
同样可以考虑前n-1个词的关系，但是，随着n的增大，模型复杂度也会随之增大。因为，实际应用中如何选择一个好的n也很有讲究，这在Machine Learning中被称为Bias-Variance Trade-off。实际应用中，我们组的师兄一般用Binary Gram或者Triple Gram就可以表达足够的信息了。

2.A Simple Neural Network Model for Word Embedding

我们在既然讨论了语言模型，就想把语言模型的idea用来构建神经网络，以此对词进行表示。在n-gram模型中，我们用前n-1个词来对第n个词进行表示。那么在神经网络中我们也可以这么做，我们的输入是n-1个词的One-hot Vectors，预测输出是第n个词。如何在一个句子中有多少个这样的神经网络呢，我们来举个例子，对于下面这个句子：

Word embedding is the collective name for a set of language modeling and feature learning techniques in natural language processing where words from the vocabulary…

我们可以构建多个窗口（window），每个窗口的大小是n。因此随着窗口的移动，一个句子可以得到$len \left(sentence\right)-n$个窗口，如下：

Word embedding is the collective name for a set of language modeling and feature learning techniques in natural language processing where words from the vocabulary…
Word embedding is the collective name for a set of language modeling and feature learning techniques in natural language processing where words from the vocabulary…
Word embedding is the collective name for a set of language modeling and feature learning techniques in natural language processing where words from the vocabulary…
…

对于每一个这样的窗口，我们可以构建一个神经网络来对其中的语言模型进行建模。这就是Bengio等人2003年的工作：

输入层有n-1个词，输出层包括dictionary中所有词的概率。输入层到隐藏层是通过一个Tanh函数来映射。算出Tanh后的假设我们希望在对每个词用一个$d$维度的向量来表示。因此输入的One-hot vector 通过一个look up table转换成d维的词向量表示（神经网络中的第一层到第二层）。从第二层到第三层是指将前n-1个词向量左乘一个H矩阵，映射到隐藏层。隐藏层到输出层是一个线性映射。因此我们可以得到每一个小窗口的目标函数：
$$f\left(w_c,w_{c-1},…,w_{c-n+1}\right)=P\left(w_c|w_{c-1},…,w_{c-n+1}\right)=\frac{e^{y_{w_c}}}{\sum_i e^{y_i}}$$
对于每个句子，我们有$len \left(sentence\right)-n$个窗口，那对于所有的句子来说，假设一共有$C$个窗口，则我们可以得到目标函数：
$$J(\theta)=\frac{1}{C}\sum_{c=n}^{C}\log f(w_c,w_{c-1},…,w_{c-n+1};\theta)+R(\theta)$$
每一个$f$都可以用上面的式子来算，$R(\theta)$是正则项，在神经网络，尤其是深度学习中很常见，一般是参数的$l_2$范数，其目的为了防止overfitting。对于每一个$y_{w_c}$我们应该如何求呢? 就像刚才所说，求这个output的过程就是一个forward process，我们想求所有的$y_{w_c}$，即该神经网络的最后一层：
$$y=b+Wx+Utanh(d+Hx)$$
令隐藏层的数目为$h$，$m$是每个词的词向量表示。解释一下上个式子中符号的意思，$b\in R^{|V|}$是词向量到output的偏置项（Bias term）。$d\in R^{h}$
是词向量这一层到output层的偏置项。$U\in R^{|V|\times h}$是隐藏层到output的weight matrix。词向量层到output层的weight是矩阵$W\in R^{|V|\times \left(n-1\right)m}$。隐藏层算出来的权重$H\in R^{h \times \left(n-1\right)m}$。词向量层的矩阵值是$C\in R^{|V|\times m}$，这个矩阵其实就是词向量的表示。
这里的式子比我们刚才所说的forward process多了一项，即$Wx$。在Bengio的paper中他解释到添加这一层可以使得训练速度更快，但是使得神经网络学习到更好的参数，因此$W$可以设置为0。
得到整个的目标函数，我们希望求解所有的参数:$W,U,x,d,b$。用老方法：Stochastic Gradient Desent。我们在接下来的博客里会举个例子来看一下一般神经网络模型该如何学习参数。

3.Continuous Bag of Words Model

Mikolov等人在谷歌提出了两个计算词向量的模型，分别是CBOW和skip-gram模型，我们在这一部分来介绍一下CBOW模型。继续借用上一部分说到的句子中的窗口的概念，在CBOW模型中我们假设窗口的大小$n$为奇数（3,5,7,9等）。在Bengio的工作中他希望利用前$n-1$个词来建模第n个词。而在CBOW模型中我们希望利用周围的词（称为上下文（Context））来对中间词进行建模。例如I love you在这个窗口中可以通过I和you来对中间词love来建模，我们希望$P\left(love|I,you\right)$这个概率比其他词的概率如$P\left(school|I,you\right)$要大。
$$P\left(love|I,you\right) > P\left(school|I,you\right)$$
这样我们的模型即为：

回到之前Bengio的那个神经网络，虽然模型很简单，实际上在计算的时候复杂度很高，一方面在对每一个窗口，最后一层都有$|V|$个节点，如果在一个非常大的corpus中计算复杂度非常高。另一方面在模型中存在tanh这样的函数，指数函数在计算机中求解是通过Taylor公式展开的。这样的话在做back-propagation迭代求参数的花费就非常高。Mikolov很好地解决了第二个问题，在构建神经网络模型中，我们对隐藏层不再采用非线性映射，而是普通的线性映射。在输出层我们仍然需要通过softmax函数将score转换成概率。
定义一下这个网络的一些符号：

• $w^{\left(i\right)}$：词典中第i个词
• $x_i$：第i个词的One-hot vector表示
• $W\in R^{n\times |V|}$：输入层到隐藏层的参数矩阵
• $u^{\left(i\right)}$：$W$矩阵中的第$i$列，也就是第$i$个词的enbedding后的表示。
• $W^{‘}\in R{n\times |V|}$：隐藏层到输出层的权重参数矩阵。
• $v^{\left(i\right)}$：$W^{‘}$矩阵中的第$i$列。也就是第$i$个词的输出表示。
  这样整个的学习过程就是：
• 1.通过词典生成一系列的one-hot vector：$(x^{\left(i-c\right)},…,x^{\left(i-1\right)},x^{\left(i+1\right)},…,x^{\left(i+c\right)})$
• 2.通过$W$得到词向量的表示：$u^{\left(j\right)}=W\cdot x^{\left(j\right)}$，j是在一个集合中：$j\in {i-c,…,i-1,i+1,…,i+c}$
• 3.取所有算出来的词向量的平均数，即隐藏层的值：$h=\frac{u^{\left(i-c\right)}+…+u^{\left(i-1\right)}+u^{\left(i+1\right)}+…+u^{\left(i+c\right)}}{2c}$
• 4.计算output层的score vector：$z=W^{‘}h$
• 5.通过softmax函数将所得到的score转换成概率：$\hat{y}=softmax\left(z\right)$

这样我们对单个窗口的目标函数即为：
\begin{align}
argmax_{\theta}~~J=\log~P(w^{\left(i\right)}|w^{\left(i-c\right)},…w^{\left(i-1\right)},w^{\left(i+1\right)},…,w^{\left(i+c\right)})
=\log \frac{exp\left(v\left(i\right)^{T}h\right)}{\sum_{j=1}^{|V|}exp \left(v\left(j\right)^{T}h\right)}
\end{align}
那么整个dataset的目标函数就是把所有窗口的目标函数加一起。不再详述~

4.Skip-Gram Model

Mikolov的paper中同时介绍了CBOW和这个模型，它俩的idea正好相反，在CBOW中我们希望通过上下文来对中心词进行建模，而Skip-Gram中我们希望通过中心词来对上下文进行建模。下图就是Skip-Gram模型：

在这个模型中，对于每一个窗口，我们想最大化$P\left(context|center word\right)$，我们知道，上下文是这个center word左右两边$c$个词。
$$argmax_{\theta}~~J=\log~P\left(w^{\left(i-c\right)},…w^{\left(i-1\right)},w^{\left(i+1\right)},…,w^{\left(i+c\right)}|w^{\left(i\right)}\right)$$
因此，直接求这个联合概率很难，我们需要做一些假设（Assumption）。在这个模型中我们做了一个非常强的假设：朴素贝叶斯假设，关于什么是Naive Bayes，可以看一下之前的博文。通过Naive Bayes Assumption，我们可以将这个目标函数写成：
$$argmax_{\theta}~J=\log~\prod_{j=0,j\neq c}^{2c} P\left(w^{\left(i-c+j\right)}|w^{\left(i\right)}\right)$$
然后呢，就是用随机梯度下降来求解啦。。。

终于把Part 2给OVER了。。下一篇博客会讲一下SENNA模型，这个模型出自一篇很牛的文章（Natural Language Processing (almost) from Scratch）。它利用一个很聪明的idea，避免了在输出层要计算$|V|$大小的score。。下次再见！

参考文献

[1] Collobert, Ronan, et al. “Natural language processing (almost) from scratch.” The Journal of Machine Learning Research 12 (2011): 2493-2537.
[2] Bengio, Yoshua, et al. “A neural probabilistic language model.” The Journal of Machine Learning Research 3 (2003): 1137-1155.
[3] Mikolov, Tomas, et al. “Efficient estimation of word representations in vector space.” arXiv preprint arXiv:1301.3781 (2013).

最近在组里做了一个报告，关于词向量以及用词向量来做句子parsing。Slides用LaTex 的Beamer框架做的，花了很长时间来做= =。slides的下载地址在这里。现在就打算把它整理成一个博文，边写边整理思路。

1.传统的词的表示方法

1.1.One-hot Vector

在自然语言的很多任务当中，我们要对corpus中的词进行建模。因此需要对每个词进行表示，传统的表示方法被称为One-hot Vector，它的意思是我对每个词用一个向量来表示，这个向量的长度是语料库（corpus）的词典的大小。比如一句话“I love ShanghaiTech University”。我可以用如下的表示方法：

“I”=[1,0,0,…,0,0]
“love”=[0,0,1,…,0,0]
“ShanghaiTech”=[0,0,,…,1,0]
“University”=[0,0,,…,0,1]

这样的好处是对于一个向量，我看它哪一维度是1就可以代表那个词。坏处也很明显：

• 如果在一个很大的语料库下，词典的维数会很高，这样在以后的计算中cost会很高。
• 它不能抓取词与词之间的语义关系。

  1.2.基于类别词的表示

  有一类对词的表示就是对其Assign一个Lable或者一个Lable的分布。比如在主题模型中，我们对每一个文档的每一个词通过生成模型来生成它。这个生成模型的过程是：
  对于每一个文档，

1. 从一个泊松分布中Sample该文档中词的数量。
2. 从一个Direchlet分布中Sample该文档所属的topic $\theta$
3. 对于这篇文档N个词中的每一个词，
   a). Sample一个主题$z_n \sim Multinomial \left(\theta\right)$
   b). 从$p\left(w_n|z_n,\beta \right)$中Sample一个词。$p\left(w_n|z_n,\beta \right)$这个概率分布函数是一个多项式分布，它是指在主题给定条件下产生词$w_n$的概率。

[Blei, David M., Andrew Y. Ng, and Michael I. Jordan. “Latent dirichlet allocation.” JMLR 2003.]
在上图中，左边的四种颜色的方框是四个主题（topic），在每个topic下的word服从多项式分布（multinomial）。如何产生这篇文章的所有词呢，我们通过右边“折方图”（表示每一个文档的topic分布），对于该分布中的每一个topic我们来通过$P\left(w_n|z_n,\beta \right)$生成word，由于文档的topic不是固定的（是一个随机变量，服从多项式分布），对于每一个topic我们都来产生words，因此我们最后得到多数的words很大程度上能够对那个概率比较大的topic的一种表示。

[Blei, David M., Andrew Y. Ng, and Michael I. Jordan. “Latent dirichlet allocation.” JMLR 2003.]
上图是LDA的图模型的表示，$\alpha$,$\eta$是超参数，在训练整个模型之前要确定好。$\theta$,$Z$,$\beta$是我们希望来做推断（inference）的随机变量。在整个模型中我们只可观察到D个文档，每个文档有$W_d$个词。

2.基于矩阵SVD分解的词向量

第二部分我想讨论一下基于矩阵分解的词向量的方法，我们的目的是获得词典中每个词的一个向量表示。那很直接的想法就是我通过语料库来构建一个Co-occurrence矩阵，矩阵的行和列均代表词典的每个词。矩阵中的每一个值是在语料库中相邻词一起出现的次数。下面我们举个例子：
我们现在有如下的语料库：

I love you.
I love you.
I love you.
I like you.
I like you.
I hate her.

通过这个语料库我们可以构建这个Co-occurrence矩阵。

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

import numpy as np
import matplotlib.pyplot as plt  
la = np.linalg
words = ["I","love","you","her","hate","like"]
X = np.array([[0,3,0,0,1,2],
			  [3,0,3,1,0,0],
			  [0,3,0,0,0,2],
			  [0,1,0,0,1,0],
			  [1,0,0,1,0,0],
			  [2,0,2,0,0,0]])
U,s,Vh = la.svd(X,full_matrices = False)
for i in xrange(len(words)):
	plt.text(U[i,0],U[i,1],words[i])
	plt.plot(U[i,0],U[i,1])
plt.show()

这个矩阵就是代码中的变量$X$。我们去分解后的$U$矩阵的前两列的值作为每一个词向量。可视化看一下结果：

我们可以看到，很多信息可以被抓取到，比如，word I和word you在几何关系上面很近。当然，由于语料库很少，深层次的语义还没有被挖掘。这样的方法有什么缺陷呢?可想而知，当语料库很大的时候，词典非常长，矩阵就特别大，我们很难对这个这个矩阵进行SVD分解。于是Bengio等人就在2003年提出了基于神经网络的方法来解决这类问题，后续有很多的变种，都是基于目标函数迭代的思路来得到词向量。我们在下一篇博客在讨论。

在有监督学习算法用做分类问题时，有两种算法在实际中应用广泛，它们分别是Logistic regression和Naive bayes。今天我们讨论一下这两类算法在分类问题上面的异同点，以及它们的优缺点。

1.两类算法介绍

Logistic Regression

对于分类问题，我们有一个训练集合N，我们的训练数据是${x^{\left(1\right)},x^{\left(2\right)},…,x^{\left(m\right)}}$，每一个训练数据$x^{\left(i\right)},i \in {1,2,…,n}$有n个特征，$x^{\left(i\right)}$对应的$y^{\left(i\right)}$是一个离散变量，我们考虑简单情况，假设$y^{\left(i\right)}$取binary的离散值，$\theta \in R^{n}$是我们的参数。Logistic regression模型是指我们认为$\theta_i$与$x_i$之间是线性关系，因此我们构建条件概率$P\left(y|x;\theta\right)$，通过将$\sum_{i=1}^{n}\theta_ix_i$映射到0和1之间的概率：
$$P\left(y|x;\theta \right)=\frac{1}{1+e^{-\theta^{T}x}}$$

Naive Bayes

Naive Bayes模型是说我有一个很强的假设，这个假设是在$y$给定的条件下，$x_i$相互独立，这个假设看上去非常stupid，但是在实际应用（比如垃圾邮件检测）中能够work非常好。这一方面也验证了Occam’s Theory: Simple model is better。继续主题，既然$x_i$相互独立，我们想对测试数据$\hat{x}$进行预测，可以通过如下方法：
$$P\left(\hat{y}=k|\hat{x}\right)=\frac{P\left(\hat{x}|\hat{y}=k\right)P\left(\hat{y}=k\right)}{P\left(\hat{x}\right)}$$
在这里，$P\left(\hat{x}|\hat{y}=k\right)$可以通过条件独立性写成：
$$P\left(\hat{x}|\hat{y}=k\right)=\prod_{i=1}^{n}p\left(\hat{x}_i|\hat{y}=k\right)$$
而分母可以通过联合概率写成：
$$P\left(\hat{x}\right)=P\left(\hat{x}|\hat{y}=0\right)P\left(\hat{y}=0\right)+P\left(\hat{x}|\hat{y}=1\right)P\left(\hat{y}=1\right)$$
然后再将$P\left(\hat{x}|\hat{y}=k\right)$式子代入，即可算出$P\left(\hat{y}=k|\hat{x}\right)$。可是$p\left(\hat{x}_i|\hat{y}=k\right)$怎么获得呢？直接通过训练数据进行counting就好了，counting的理论解释是最大化似然函数，这里不再详述。

好的，下面我们开始分析Logistic Regression和Naive Bayes的异同点。

2.两者的异同点

相同点

• Logistic regression和Naive bayes都是对特征的线性表达$\sum_j\theta_jx_j$，只是区别在于两者所fit的参数不同。
• Logistic regression和Naive bayes建模的都是条件概率$P\left(y=k|x\right)$，对所最终求得的不同类的结果有很好的解释性。而不像SVM，神经网络这样解释性不高。

不同点

• Logistic regression在有相关性feature上面学习得到的模型在测试数据的performance更好。也就是说，logistic regression在训练时，不管特征之间有没有相关性，它都能找到最优的参数。而在Naive bayes中，由于我们给定特征直接相互独立的严格设定，在有相关性的feature上面学习到的权重同时变大或变小，它们之间的权重不会相互影响。从这方面来说，如果能够在对参数较好地控制，在损失项方面处理的很好的话，Logistic regression相对Naive bayes在应用时更不会限制在特征工程（feature engineering）上面。

• Naive bayes的好处是我没有优化参数这一步，通过训练数据我直接得到一个counting table，这些有助于并行化。

• Andrew Ng和Michael Jordan在2001年发了一篇NIPS短文《On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes》，他们把这两个模型用在各种数据集上面进行测试，最后得到在小数据上面Naive bayes可以取得更好的效果，随着数据的增多、特征维度的增大，Logistic regression的效果更好。这也是因为Naive bayes是生成模型，在有prior的情况下模型能够把数据fit的更好，而Logistic regression属于生成模型，目标驱动化，不去建模联合概率，通过训练数据直接预测输出，因此在数据足够多的情况下能够得到更好一些的效果。

感谢秦风师弟的帮助，以后这里就是新家啦！

pdf版本下载地址
前一阵在一个机器学习的qq群里听了一位妹子做关于线性模型的tutorial，我就按着自己的理解把线性模型的资料窜一下。

1 引入

我们知道，在机器学习模型中最基础的就是线性模型，无论是有计算机科学味道的机器学习书籍（如PRML）还是统计系味道较重的统计学习书籍（如ESL）,或者是各位大神（Andrew Ng, Eric Xing…）的机器学习课程都是先从线性模型还是讲起，可见其基础性。本文先从基本的线性模型，到指数家族，最后谈广义线性模型，以及众多广义线性模型的例子。

2 用于回归问题的线性模型

2.1 模型定义

有监督学习是指通过训练数据学到一个model使得其在测试数据上面能够表现的很好。而回归问题中我们想学到的模型就是一个超平面，我们希望这个超平面能够很好地来fit我们的训练数据。假设我们的输入的一个数据是$x$，这里的$x$是一个向量，每一维度代表这个数据的一个属性即$x_i \in R$，而且$x\in R$，输出是$y$，首先分析一下向量$x$的所有可能取值：

• 原本的数据
• 原始数据的一些变化，比如：log，exp等
• 平方，三次方等
• 不同元素之间的关系，如：$x_3 = x_1 \cdot x_2$

既然建立起$x$，一个很直观的想法就是我希望$y$与$x$是一个近似的线性关系。因此，我们定义一个近似$y$的线性函数：
$$h_\theta \left(x\right) = \sum_{i=0}^{n} \theta_i x_i = \theta^Tx$$
其中，$\theta_i$是参数，可以理解成对每一个 $x_i \in R$ 的一个权重，定义了这个模型，我们接下来希望通过$x$和$y$来获得这些参数。因此，我们定义了一个损失函数 $J\left(\theta \right)$，我们希望平均下来对于每一个$x$输出的$y$及其预测的$h\left(x\right)$之间的平均误差最小。
$$J\left(\theta \right) = \frac{1}{2} \sum_{i=1}^{m}\left(h_\theta\left(x^{(i)}\right)-y^{(i)}\right)^2$$
在这个式子中$x^{(i)}$和$y^{(i)}$分别代表第$i$个数据的输入和输出。我们可以看出，其实这个函数就是中学学到的最小二乘模型。既然目标函数出来了，我们就需要用一些优化方面的技术来求解我们的参数。

2.2 求解模型

2.2.1 直接求解

我们可以看出，我们的目标函数是个凸函数，我们把目标函数写成向量的形式，如下：
$$J\left(\theta \right) = \frac{1}{2}\left(X\theta - y\right)^T\left(X\theta - y\right)$$
这里我们定义$X = $
\begin{bmatrix}
—(x^{(1)})^T— \\
—(x^{(2)})^T— \\
: \\
: \\
—(x^{(m)})^T—
\end{bmatrix}
m是指训练数据的数量。每一个$x^{(i)}分别指一个数据$
\begin{aligned}\end{aligned}
$$\bigtriangledown_{\theta} J\left(\theta\right) = X^T\left(X\theta - y\right)$$
设偏导数为0，则
$$\theta = \left(X^TX\right)^{-1}X^Ty$$
这么轻松就得到了$\theta$的值了，得到$\theta$后，我们看一下对于我们的训练数据$X$，我们可以通过下面这个式子得到对应的$\hat{y}$。
$$\hat{y} = X \theta = X\left(X^TX\right)^{-1}X^Ty$$
我们可以看到，$y$与$\hat{y}$直接是通过一个矩阵来进行映射，我们把矩阵$H=X\left(X^TX\right)^{-1}X^T$这个矩阵称为帽子矩阵（hat matrix）。这里我们停下来分析一下这个式子的几何意义，
在一个m维的空间里，$y$就是一个点，所有的$x^{(i)}$ span 出一个平面。我们的目标就是在这个平面上面搜寻出一个点，使得$y$到这个点的距离最小，因此，最好的点就是$y$到平面的最短距离。

由Gauss-Markov定理可得，这里我们得到的$y_{target}$是对$y$的无偏估计。

Gauss-Markov定理：$\theta$的最小二乘估计在所有线性无偏估计中方差最小。

life is really easy？我们仔细观察，这里存在两个问题：

（1）在我们得到最后关于$\theta$的表达式中有一项矩阵求逆，所以，当$X^TX$不能求逆(奇异矩阵)时，即使咱们能得到$\theta$的表达式，也是白搭嘛。有哪些情况呢？如：$x_i$和$x_j$之间有线性关系。这时候怎么办呢，我们需要对$\theta$加一些约束条件。后面有说$LASSO$或者$Ridge$ $Regression$（这里就不再是无偏估计了，我们希望用“有偏”来换取较小的均方误差（MSE））
（2）即使用了预处理（特征选择等）什么天马行空的方法，这个矩阵能求逆，当每一个$x^{(i)}$的维数很高时，我们发现，即使简单地求一下$X^TX$都很耗时。看来，我们需要找到更快的解决方法，这就是接下来要说基于梯度的方法。

2.2.2 基于梯度的方法

基于梯度的方法基本思想是，既然我不能一次性找到最优的solution，那我慢慢找，通过一个学习法则来找，每一步都满足使得目标函数有一定的提高。这样我们的第一个方法就是梯度下降法，初始化一组参数$\theta$，对于一个训练数据，我们通过如下迭代$\theta$:
$$\theta_j:=\theta_j - \alpha \frac{\partial}{\partial \theta_j}J\left(\theta\right)$$
通过求导可以得到
$$\theta_j:=\theta_j + \alpha \left(y^{(i)}-h_\theta\left(x^{(i)}\right)\right)x_j^{(i)}$$
由于我们训练样本有$m$个数据，我们迭代的公式即为：
$$\theta_j:=\theta_j + \alpha \sum_{i=1}^{m} \left(y^{(i)}-h_\theta\left(x^{(i)}\right)\right)x_j^{(i)}$$

在这个方法中，每次我们更新一次$\theta$，都要穷举所有的训练样本，因此，这类算法被称为批梯度下降（batch gradient descent）。可想而知，这种算法耗时很长，何不如每次仅考虑一个数据来对$\theta_j$进行更新呢？这就是下面的随机梯度下降（stochastic gradient descent）。

循环直至收敛{
对训练集每一个数据进行操作{
$$\theta_j:=\theta_j + \alpha \left(y^{(i)}-h_\theta\left(x^{(i)}\right)\right)x_j^{(i)}$$
}
}

2.3 结果的思考

通过上面的求解，我们可以直接或者间接得到$\theta$的值，在原来当我们设计模型的时候，我们希望$y\approx h_{\theta} \left(x\right)$，实际上，他们直接有一个误差$\epsilon$，我想现在换一个角度考虑，我直接对$y$跟$x$的关系进行建模，因此，
$$y^{(i)} = h_{\theta} \left(x^{(i)}\right) + \epsilon^{(i)}$$
$\epsilon$服从一个分布函数。

在这里有一个结论，
如果$\epsilon^{(i)}$之间独立同分布（IID）,并且服从一个均值为0,方差为$\sigma ^{2}$的高斯分布。
$$p\left(\epsilon^{(i)} \right) = \frac{1}{\sqrt{2\pi}\sigma}exp\left(-\frac{\left(\epsilon^{(i)}\right)^{2}}{2 \sigma ^{2}}\right)$$
将$\epsilon^{(i)}$代入，我们可以得到，
$$p\left(y^{(i)}|x^{(i)};\theta \right) = \frac{1}{\sqrt{2\pi}\sigma}exp\left(-\frac{\left(y^{(i)} - h_{\theta} \left(x^{(i)}\right)\right)^{2}}{2 \sigma ^{2}}\right)$$
因为训练数据中样本之间关系是IID的，我们可以最大化似然估计（MLE），似然函数为：
\begin{aligned}
L\left(\theta \right) = L\left(\theta;X,\vec{y} \right) = p\left(\vec{y} | X;\theta \right)
= \prod_{i=1}^{m} \frac{1}{\sqrt{2\pi}\sigma}exp\left(-\frac{\left(y^{(i)} - h_{\theta} \left(x^{(i)}\right)\right)^{2}}{2 \sigma ^{2}}\right)\\
\end{aligned}
我们想最大化似然函数，这样就意味着最大化$exp$括号里的式子。可以观测到，里面的式子其实就正比于我们之前的损失函数。而这里，我们最后选取的参数$\theta$跟$\sigma$之间没有关系。这个现象比较有趣，我们将在以后讨论广义线性模型时讨论到它。

2.4 更一般化的损失函数

在最小二乘里面，我们定义损失函数是通过$l_2$范数，我们可以得到最小化它与$y|x \sim Gauss$所得到的最大化似然函数等价。这里我们若把$l_2$范数改为$l_1$范数或者$l_0$范数呢？它们对应的损失函数分别称为：平方损失，绝对损失和0-1损失。这里我们简单地看一下三个损失函数在描述样本集中趋势的意义：
平方损失：
$$min_{\theta} ||X-\theta||^2$$
绝对损失：
$$min_{\theta} |X-\theta|$$
0-1损失：
$$min_{\theta} 1\left(X \neq\theta \right)$$
我们可以看到，在描述样本时，其实它们分别表示：平均数，中位数和众数。
另外，在$l_1$范数的损失函数的情况下，最小化损失函数其实就是最大化Laplace分布下的似然函数：
$$max_{\beta} \prod_{i} \frac{m}{2} exp \left(-m \sum_i|y_i-x_i^T\beta|\right)$$

2.5 带有惩罚项的目标函数

在我们做回归问题的时候，为了使得我们的模型有着较强的表达能力，我们建立的$x$包含了原本数据的1-9次方，这样通过构建损失函数学出来的模型在未来测试数据上很大可能会过拟合（overfit）。这时候我们希望对参数$\theta$加一些约束，如$l_1$，$l_2$ 范数。这种方法在统计系被称为Shrinkage方法，当然，引入它的理由不仅仅是为了防止过拟合，很多时候保留或者舍弃一些feature可以使得模型更直观（intuitive），这里我们讨论两种模型，岭回归（Ridge Regression）和LASSO。

2.5.1 Ridge Regression

Ridge Regression是指我在目标函数里面加上参数的$l_2$范数，这里我们的目标函数就变成：
$$J\left(\theta \right) = \frac{1}{2} \sum_{i=1}^{m}\left(h_\theta\left(x^{(i)}\right)-y^{(i)}\right)^2 + \lambda||\theta||_2$$
因此，我们得到
$$\theta = \left(X^TX+\lambda I\right)^{-1}X^Ty$$

2.5.2 LASSO

LASSO是指我在目标函数里面加上参数的$l_1$范数
$$J\left(\theta \right) = \frac{1}{2} \sum_{i=1}^{m}\left(h_\theta\left(x^{(i)}\right)-y^{(i)}\right)^2 + \lambda|\theta|_1$$
如何求解呢？
求次梯度啊，MP，OMP。。等等。上学期压缩感知学了一学期的这方面的算法和应用。To be writed!

Blog by Tomasz Malisiewicz(Phd@CMU Now PostDoc@MIT)
Blog by Saravanan Thirumuruganathan
Blog by Shubhendu Trivedi

此博文整理一些备用数学公式，会一直更新：

1.Linear Algebra

Linear Algebra Review and Reference

1.1 有关trace的公式

对于一个矩阵$A\in R^{n\times n}$，定义矩阵A的trace为：
$$trace\left(A\right)=\sum_{i=1}{n}A_{ii}$$

• $trace\left(A\right)=trace\left(A^{T}\right)$
• For $x\in R^{n}$, $x^{T}Ax=trace\left(Axx^{T}\right)$
• For $B\in R^{n\times n}$$trace\left(AB\right) = trace\left(BA\right)$,proof is in the pdf file.

下面是搜集的一些机器学习的课程资源：

1. General Machine learning courses

1.1 Introduction to Machine Learning courses

Coursera上 Andrew Ng的machine learning课，现在是self learning，可以随时学习。

1.2 Machine Learning courses @ Universities with videos

Andrew Ng在Stanford开设的CS 229: Machine Learning课程，notes很好，多看几遍收获很大。
来自Washington的Pedro Domingos在Coursera上面开设的Machine Learning，Domingos大牛可谓机器学习界风云人物，发明了Sum-Product Network, Markov Logic等等模型，我等渣渣只能在大牛的脚下做一些小的improvement。
CMU院士Tom Mitchell开设的10-701/15-781

1.3 Machine Learning courses @ Universities without videos

MIT 6.867 研究生课程Machine Learning，notes很详细！

2. Advanced machine learning courses

高级机器学习课程，包括图模型，无参贝叶斯，统计机器学习理论

2.1 Probabilistic Graphical Models

来自CMU的Eric Xing在2014年春季开设的概率图模型：Probabilistic Graphical Models
(Spring 2014)

Stanford的Daphne Koller在coursera开设的Probabilistic Graphical Models

2.2 Statistical Learning Theory

CMU大牛Larry Wasserman的统计机器学习Statistical Machine Learning

2.3 一些比较老的资源

2.3.1 Copied from Dr. Tomasz.

以下资源都是从Dr. Tomasz主页分享而获得的，
With videos
Graduate Summer School: Intelligent Extraction of Information from Graphs and High Dimensional Data.
UCLA Institute for Pure & Applied Mathematics.
July 2005
(He highly recomment the Michael Jordan Graphical Model videos!!!)

Emphasis Week on Learning and Inference in Vision
February 2005
Simoncelli, Mumford, Fitzgibbon, Efros, Frey, Zhu,
Freeman, Black, Blake, Isard, Weiss, Huttenlocher,
Yuille, Zabih, Besag, Gottardo, Donoho
MSRI

With notes
CS 281B / Stat 241B: Statistical Learning Theory
Spring 2004
Michael Jordan
Berkeley

CS 281A / Stat 241A: Statistical Learning Theory
Fall 2004
Michael Jordan
Berkeley

9.520: Statistical Learning Theory and Applications
Spring 2014
Tomas Poggio et al
MIT
Spring 2003

Statistics 315B: Modern Applied Statistics:
Elements of Statistical Learning II
Jerome H. Friedman
Stanford

Probabilistic Graphical Models
Fall 2004
Kevin Murphy
UBC

2.3.2 Some Graduate school videos and old workshops.

With videos
Deep Learning Workshop: Foundations and Future Directions
Special Topics in Computer Vision04 Spring