Machine Learning Readings

Table of Contents

1 常见算法分类汇总

http://www.kuqin.com/shuoit/20140925/342326.html

按照学习方式划分

  • 监督式学习:在监督式学习下,输入数据被称为"训练数据",每组训练数据有一个明确的标识或结果。在建立预测模型的时候,监督式学习建立一个学习过程,将预测结果与"训练数据"的实际结果进行比较,不断的调整预测模型,直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归(Logistic Regression)和反向传递神经网络(Back Propagation Neural Network)。
  • 非监督式学习:在非监督式学习中,数据并不被特别标识,学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。
  • 半监督式学习:在此学习方式下,输入数据部分被标识,部分没有被标识,这种学习模型可以用来进行预测,但是模型首先需要学习数据的内在结构以便合理的组织数据来进行预测。应用场景包括分类和回归,算法包括一些对常用监督式学习算法的延伸,这些算法首先试图对未标识数据进行建模,在此基础上再对标识的数据进行预测。如图论推理算法(Graph Inference)或者拉普拉斯支持向量机(Laplacian SVM.)等。
  • 强化学习:在这种学习模式下,输入数据作为对模型的反馈,不像监督模型那样,输入数据仅仅是作为一个检查模型对错的方式,在强化学习下,输入数据直接反馈到模型,模型必须对此立刻作出调整。常见的应用场景包括动态系统以及机器人控制等。常见算法包括Q-Learning以及时间差学习(Temporal difference learning)。

在企业数据应用的场景下, 人们最常用的可能就是监督式学习和非监督式学习的模型。 在图像识别等领域,由于存在大量的非标识的数据和少量的可标识数据, 目前半监督式学习是一个很热的话题。 而强化学习更多的应用在机器人控制及其他需要进行系统控制的领域。

按照算法类似性划分

  • 回归算法:回归算法是试图采用对误差的衡量来探索变量之间的关系的一类算法。回归算法是统计机器学习的利器。在机器学习领域,人们说起回归,有时候是指一类问题,有时候是指一类算法,这一点常常会使初学者有所困惑。常见的回归算法包括:最小二乘法(Ordinary Least Square),逻辑回归(Logistic Regression),逐步式回归(Stepwise Regression),多元自适应回归样条(Multivariate Adaptive Regression Splines)以及本地散点平滑估计(Locally Estimated Scatterplot Smoothing)。
  • 基于实例的算法:基于实例的算法常常用来对决策问题建立模型,这样的模型常常先选取一批样本数据,然后根据某些近似性把新数据与样本数据进行比较。通过这种方式来寻找最佳的匹配。因此,基于实例的算法常常也被称为"赢家通吃"学习或者"基于记忆的学习"。常见的算法包括 k-Nearest Neighbor(KNN), 学习矢量量化(Learning Vector Quantization, LVQ),以及自组织映射算法(Self-Organizing Map , SOM)。
  • 正则化方法:正则化方法是其他算法(通常是回归算法)的延伸,根据算法的复杂度对算法进行调整。正则化方法通常对简单模型予以奖励而对复杂算法予以惩罚。常见的算法包括:Ridge Regression, Least Absolute Shrinkage and Selection Operator(LASSO),以及弹性网络(Elastic Net)。
  • 决策树学习:决策树算法根据数据的属性采用树状结构建立决策模型, 决策树模型常常用来解决分类和回归问题。常见的算法包括:分类及回归树(Classification And Regression Tree, CART), ID3(Iterative Dichotomiser 3), C4.5, Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 随机森林(Random Forest), 多元自适应回归样条(MARS)以及梯度推进机(Gradient Boosting Machine, GBM)。
  • 贝叶斯方法:贝叶斯方法算法是基于贝叶斯定理的一类算法,主要用来解决分类和回归问题。常见算法包括:朴素贝叶斯算法,平均单依赖估计(Averaged One-Dependence Estimators, AODE),以及Bayesian Belief Network(BBN)。
  • 基于核的算法:基于核的算法中最著名的莫过于支持向量机(SVM)了。 基于核的算法把输入数据映射到一个高阶的向量空间, 在这些高阶向量空间里, 有些分类或者回归问题能够更容易的解决。 常见的基于核的算法包括:支持向量机(Support Vector Machine, SVM), 径向基函数(Radial Basis Function ,RBF), 以及线性判别分析(Linear Discriminate Analysis ,LDA)等。
  • 聚类算法:聚类,就像回归一样,有时候人们描述的是一类问题,有时候描述的是一类算法。聚类算法通常按照中心点或者分层的方式对输入数据进行归并。所以的聚类算法都试图找到数据的内在结构,以便按照最大的共同点将数据进行归类。常见的聚类算法包括 k-Means算法以及期望最大化算法(Expectation Maximization, EM)。
  • 关联规则学习:关联规则学习通过寻找最能够解释数据变量之间关系的规则,来找出大量多元数据集中有用的关联规则。常见算法包括 Apriori算法和Eclat算法等。
  • 人工神经网络:人工神经网络算法模拟生物神经网络,是一类模式匹配算法。通常用于解决分类和回归问题。人工神经网络是机器学习的一个庞大的分支,有几百种不同的算法。(其中深度学习就是其中的一类算法,我们会单独讨论),重要的人工神经网络算法包括:感知器神经网络(Perceptron Neural Network), 反向传递(Back Propagation), Hopfield网络,自组织映射(Self-Organizing Map, SOM),学习矢量量化(Learning Vector Quantization, LVQ)。
  • 深度学习:深度学习算法是对人工神经网络的发展。在计算能力变得日益廉价的今天,深度学习试图建立大得多也复杂得多的神经网络。很多深度学习的算法是半监督式学习算法,用来处理存在少量未标识数据的大数据集。常见的深度学习算法包括:受限波尔兹曼机(Restricted Boltzmann Machine, RBN), Deep Belief Networks(DBN),卷积网络(Convolutional Network), 堆栈式自动编码器(Stacked Auto-encoders)。
  • 降低维度算法:像聚类算法一样,降低维度算法试图分析数据的内在结构,不过降低维度算法是以非监督学习的方式试图利用较少的信息来归纳或者解释数据。这类算法可以用于高维数据的可视化或者用来简化数据以便监督式学习使用。常见的算法包括:主成份分析(Principle Component Analysis, PCA),偏最小二乘回归(Partial Least Square Regression,PLS), Sammon映射,多维尺度(Multi-Dimensional Scaling, MDS), 投影追踪(Projection Pursuit)等。
  • 集成算法:集成算法用一些相对较弱的学习模型独立地就同样的样本进行训练,然后把结果整合起来进行整体预测。集成算法的主要难点在于究竟集成哪些独立的较弱的学习模型以及如何把学习结果整合起来。这是一类非常强大的算法,同时也非常流行。常见的算法包括:Boosting, Bootstrapped Aggregation(Bagging), AdaBoost,堆叠泛化(Stacked Generalization Blending, SGB),梯度推进机(Gradient Boosting Machine, GBM),随机森林(Random Forest)。

2 机器学习和其他领域联系

机器学习和数据挖掘

ntuml-ml-vs-dm.png

机器学习和人工智能

ntuml-ml-vs-ai.png

机器学习和统计学

ntuml-ml-vs-st.png

3 Use Random Forest: Testing 179 Classifiers on 121 Datasets

http://machinelearningmastery.com/use-random-forest-testing-179-classifiers-121-datasets/

对于中小规模数据分类问题(实际上这就是大部分我们遇到的场景),RF和Gaussian-SVM应该是首先应该尝试的模型/算法。

最后作者给出了选择模型/算法一个比较实际的建议,那就是choose a middle ground. 这里middle ground是相对于其他两种办法而言的:

  • Pick your favorite algorithm. Fast but limited to whatever your favorite algorithm or library happens to be. # 只选择自己喜欢算法
  • Spot check a dozen algorithms. A balanced approach that allows better performing algorithms to rise to the top for you to focus on. # 随机抽查其他算法决定是否要继续深入下去
  • Test all known/implemented algorithms. Time consuming exhaustive approach that can sometimes deliver surprising results. # 尝试所有算法

4 Why you should be Spot-Checking Algorithms on your Machine Learning Problems

http://machinelearningmastery.com/why-you-should-be-spot-checking-algorithms-on-your-machine-learning-problems/

Spot-checking algorithms is about getting a quick assessment of a bunch of different algorithms on your machine learning problem so that you know what algorithms to focus on and what to discard. # 随机抽查算法就是,快速评估一堆算法,以便来决定哪些算法需要继续深入下去而那些算法应该舍弃。

下面给出了5点关于随机抽查算法的注意事项:

  • Algorithm Diversity: You want a good mix of algorithm types. I like to include instance based methods (live LVQ and knn), functions and kernels (like neural nets, regression and SVM), rule systems (like Decision Table and RIPPER) and decision trees (like CART, ID3 and C4.5). # 算法多样性。确保几种算法在实质上差别很很大,比如SVM和LR+正则化本质是一样的,所以如何尝试了SVM那么没有必要尝试LR+正则化. 比如我们可以选择基于实例的kNN, 基于决策树的CART, 基于核函数SVM,以及基于生成方法的NB. 文章后面还给了10个比较常用的算法。当然这些都是没有做加强的。
  • Best Foot Forward: Each algorithm needs to be given a chance to put it's best foot forward. This does not mean performing a sensitivity analysis on the parameters of each algorithm, but using experiments and heuristics to give each algorithm a fair chance. For example if kNN is in the mix, give it 3 chances with k values of 1, 5 and 7. # 为每个算法评价的时候需要尽可能的公平,为这个算法提供最有利的条件。
  • Formal Experiment: Don't play. There is a huge temptation to try lots of different things in an informal manner, to play around with algorithms on your problem. The idea of spot-checking is to get to the methods that do well on the problem, fast. Design the experiment, run it, then analyze the results. Be methodical. I like to rank algorithms by their statistical significant wins (in pairwise comparisons) and take the top 3-5 as a basis for tuning. # 和上面一样,要深入分析这个方法。最终选择前面3-5名来做作为basis进行调优。
  • Jumping-off Point: The best performing algorithms are a starting point not the solution to the problem. The algorithms that are shown to be effective may not be the best algorithms for the job. They are most likely to be useful pointers to types of algorithms that perform well on the problem. For example, if kNN does well, consider follow-up experiments on all the instance based methods and variations of kNN you can think of. # 选出的这几个算法只是一个开始,它能告诉我们这个问题最终结构可能会是什么样的。我们可以以此为起点继续深入。
  • Build Your Short-list: As you learn and try many different algorithms you can add new algorithms to the suite of algorithms that you use in a spot-check experiment. When I discover a particularly powerful configuration of an algorithm, I like to generalize it and include it in my suite, making my suite more robust for the next problem. # 建立自己的候选算法集合

下面是这篇文章给出的10个候选算法:

  • C4.5 This is a decision tree algorithm and includes descendent methods like the famous C5.0 and ID3 algorithms.
  • k-means. The go-to clustering algorithm.
  • Support Vector Machines. This is really a huge field of study.
  • Apriori. This is the go-to algorithm for rule extraction.
  • EM. Along with k-means, go-to clustering algorithm.
  • PageRank. I rarely touch graph-based problems.
  • AdaBoost. This is really the family of boosting ensemble methods.
  • knn (k-nearest neighbor). Simple and effective instance-based method.
  • Naive Bayes. Simple and robust use of Bayes theorem on data.
  • CART (classification and regression trees) another tree-based method.

5 A Tour of Machine Learning Algorithms

http://machinelearningmastery.com/a-tour-of-machine-learning-algorithms/

在Algorithm Similiarity一节基本给出了ML所有可能用到的算法

Regression. Regression is concerned with modelling the relationship between variables that is iteratively refined using a measure of error in the predictions made by the model. Regression methods are a work horse of statistics and have been cooped into statistical machine learning. This may be confusing because we can use regression to refer to the class of problem and the class of algorithm. Really, regression is a process. Some example algorithms are:

  • Ordinary Least Squares
  • Logistic Regression
  • Stepwise Regression
  • Multivariate Adaptive Regression Splines (MARS)
  • Locally Estimated Scatterplot Smoothing (LOESS)

Instance-based Methods. Instance based learning model a decision problem with instances or examples of training data that are deemed important or required to the model. Such methods typically build up a database of example data and compare new data to the database using a similarity measure in order to find the best match and make a prediction. For this reason, instance-based methods are also called winner-take all methods and memory-based learning. Focus is put on representation of the stored instances and similarity measures used between instances.

  • k-Nearest Neighbour (kNN)
  • Learning Vector Quantization (LVQ)
  • Self-Organizing Map (SOM)

Regularization Methods. An extension made to another method (typically regression methods) that penalizes models based on their complexity, favoring simpler models that are also better at generalizing. I have listed Regularization methods here because they are popular, powerful and generally simple modifications made to other methods.

  • Ridge Regression
  • Least Absolute Shrinkage and Selection Operator (LASSO)
  • Elastic Net

Decision Tree Learning. Decision tree methods construct a model of decisions made based on actual values of attributes in the data. Decisions fork in tree structures until a prediction decision is made for a given record. Decision trees are trained on data for classification and regression problems.

  • Classification and Regression Tree (CART)
  • Iterative Dichotomiser 3 (ID3)
  • C4.5
  • Chi-squared Automatic Interaction Detection (CHAID)
  • Decision Stump
  • Random Forest
  • Multivariate Adaptive Regression Splines (MARS)
  • Gradient Boosting Machines (GBM)

Bayesian. Bayesian methods are those that are explicitly apply Bayes' Theorem for problems such as classification and regression.

  • Naive Bayes
  • Averaged One-Dependence Estimators (AODE)
  • Bayesian Belief Network (BBN)

Kernel Methods. Kernel Methods are best known for the popular method Support Vector Machines which is really a constellation of methods in and of itself. Kernel Methods are concerned with mapping input data into a higher dimensional vector space where some classification or regression problems are easier to model.

  • Support Vector Machines (SVM)
  • Radial Basis Function (RBF)
  • Linear Discriminant Analysis (LDA)

Clustering Methods. Clustering, like regression describes the class of problem and the class of methods. Clustering methods are typically organized by the modelling approaches such as centroid-based and hierarchal. All methods are concerned with using the inherent structures in the data to best organize the data into groups of maximum commonality.

  • k-Means
  • Expectation Maximisation (EM)

Association Rule Learning. Association rule learning are methods that extract rules that best explain observed relationships between variables in data. These rules can discover important and commercially useful associations in large multidimensional datasets that can be exploited by an organisation.

  • Apriori algorithm
  • Eclat algorithm

Artificial Neural Networks. Artificial Neural Networks are models that are inspired by the structure and/or function of biological neural networks. They are a class of pattern matching that are commonly used for regression and classification problems but are really an enormous subfield comprised of hundreds of algorithms and variations for all manner of problem types. Some of the classically popular methods include (I have separated Deep Learning from this category):

  • Perceptron
  • Back-Propagation
  • Hopfield Network
  • Self-Organizing Map (SOM)
  • Learning Vector Quantization (LVQ)

Deep Learning. Deep Learning methods are a modern update to Artificial Neural Networks that exploit abundant cheap computation. They are concerned with building much larger and more complex neural networks, and as commented above, many methods are concerned with semi-supervised learning problems where large datasets contain very little labelled data.

  • Restricted Boltzmann Machine (RBM)
  • Deep Belief Networks (DBN)
  • Convolutional Network
  • Stacked Auto-encoders

Dimensionality Reduction. Like clustering methods, Dimensionality Reduction seek and exploit the inherent structure in the data, but in this case in an unsupervised manner or order to summarise or describe data using less information. This can be useful to visualize dimensional data or to simplify data which can then be used in a supervized learning method.

  • Principal Component Analysis (PCA)
  • Partial Least Squares Regression (PLS)
  • Sammon Mapping
  • Multidimensional Scaling (MDS)
  • Projection Pursuit

Ensemble Methods. Ensemble methods are models composed of multiple weaker models that are independently trained and whose predictions are combined in some way to make the overall prediction. Much effort is put into what types of weak learners to combine and the ways in which to combine them. This is a very powerful class of techniques and as such is very popular.

  • Boosting
  • Bootstrapped Aggregation (Bagging)
  • AdaBoost
  • Stacked Generalization (blending)
  • Gradient Boosting Machines (GBM)
  • Random Forest

6 机器学习(Tom M. Mitchell)


C1 引言

一些学科和它们对机器学习的影响

  • 人工智能:学习概念的符号表示;作为搜索问题的机器学习;作为提高问题求解能力的学习;利用先验的知识和训练数据一起引导学习。
  • 贝叶斯方法:作为计算假设概率基础的贝叶斯法则;朴素贝叶斯;估计未观测到变量值的算法。
  • 计算复杂性理论:不同学习任务中固有的复杂性的理论边界,以计算量,训练样例数量,出错数量衡量。
  • 控制论:为了优化预定目标,学习对各种处理过程进行控制,学习预测被控制的过程的下一个状态。
  • 信息论:熵和信息内容的度量;学习最小描述长度方法;编码假设时,对最佳训练序列的最佳编码及其关系。
  • 哲学:奥卡姆的剃刀:最简单的假设是最好的;从观察到的数据泛化的理由分析。
  • 心理学和神经生物学:实践的幂定律(power law of practice), 该定律指出对于很大范围内的学习问题,人们的反应速度随着时间次数的幂级提高;激发人工神经网络学习模式的神经生物学研究。
  • 统计学:根据有限数据样本,对估计假设精度时出现的误差(例如偏差和方差)的刻画;置信区间,统计检验。

学习任务被简化为发现一个理想目标函数V的可操作描述,通常要完美学习这样一个V的可操作的形式是非常困难的。事实上,我们通常仅希望学习算法得到近似的目标函数,由于这个原因学习目标函数的过程常被称为函数逼近(function approximation).

这书的很多章节给出了一些基本表示(比如线性函数,逻辑描述,决策树,人工神经元网络)定义的假设空间的搜索算法。这些不同的假设表示法适合于学习不同的目标函数。对于其中的每一种假设表示法,对应的学习算法发挥不同内在结构的优势来组织对假设空间的搜索。自始至终,本书够贯穿着这种把学习问题视为搜索问题的看法,从而通过搜索策略和学习器探索的搜索空间的内在结构来刻画学习方法。


C2 概念学习和一般到特殊序

概念学习(concept learning)是指从有关某个布尔函数的输入输出训练样例中推断该布尔函数。概念学习可以看作是搜索预定义潜在假设空间的过程。

实例(instance), 训练样例(training examples), 正例(positive example), 反例(negative example), 所有可能假设(all possible hypotheses)

归纳学习假设:任一假设如果在足够大的训练样例集中很好地逼近目标函数,它也能在未见实例中很好地逼近目标函数。

由于归纳学习需要某种形式的预先假设,或称为归纳偏置(inductive bias), 我们可以用归纳偏置来描述不同学习方法的特征。 # 可以认为归纳偏置描述了这个算法本身在某方面的倾向


C3 决策树学习

通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction). 从树根到树叶的每一条路径对影一族属性测试的合取,树本身对应这些合取的析取。

基本的ID3算法在搜索中不进行回溯,每当在树的某一层次上选择了一个属性进行测试,它不会再回溯重新考虑这个选择。所以它易受无回溯的爬山搜索中的常见风险影响:收敛到局部最优的答案,而不是全局最优。

奥卡姆剃刀(Occam's Razor): 优先选择拟合数据的最简单的假设。一种解释是简单假设的数量少于复杂假设的数量,所以找到一个简单的但是同时与训练数据拟合的假设的可能性较小。

决策树学习的实际问题包括:避免过度拟合数据,处理连续值的属性,属性选择度量标准,处理属性值不完整的训练数据,处理不同代价的属性,提高计算效率。处理连续值的属性可以通过对连续值进行分断或者是映射成为离散值来处理;属性不完整的训练数据可以为缺少值的属性安排最有可能的值,或者是按照概率来赋值;处理不同代价的属性是因为我们取得某些属性的难易程度不同,比如体温相对于血液化验结果更容易获得,在属性筛选方面需要考虑代价函数。

出现过度拟合(overfitting)一种可能原因是训练样例含有随机错误或噪声。当训练数据没有噪声时,过度拟合也可能发生,特别是当很少的样例被关联到叶子节点时。这种情况下,很可能是出现巧合的规律性,使得某些属性恰巧可以很好地被分割样例,但是却与实际的目标函数并无关系。 # 所以在做剪枝时需要减去一些叶子节点上很少的样例的节点。

有几种途径可以被用来避免决策树学习中的过度拟合,它们可以被分为两类:

  • 及早停止树增长,在ID3算法完美分类训练数据之前就停止树增长。 # 一种启发式规则:最小描述长度(MDL, minimum description length)来指导是否停止树增长. 或者是利用卡方(chi-square)测试来估计进一步扩展节点能否改善整个实例分布上的性能,还是仅仅改善了当前的训练数据上的性能。
  • 后修剪法(post-prune), 即允许树过度拟合,然后对整个树进行后修剪。# 通过判断合并某个节点是否能够改善验证数据来决定修剪, 称为错误率降低修剪(reduced-error pruning).

尽管第一种方法看起来更直接,但是对于过度拟合进行后修剪被证明在实践中更成功,因为第一种方法中精确地估计何时停止树增长很困难。


C4 人工神经网络

由于ANN(Artificial Neural Networks, ANN)只是在一定程度上受到生物神经系统的启发,所以ANN并未模拟生物神经系统中很多复杂特征,而且已经知道ANN很多特征也和生物系统也是不一致的。例如我们考虑的ANN每一个单元输出单一的不变值,然而生物神经元输出的是复杂的时序脉冲。

ANN基本组成单元是感知器(perceptron)变种:因为感知器的输出函数是有阈值并且不可导的sign(w' * x),为了方便计算所以ANN基本单元输出变成无阈值并且连续可导(w' * x). 这样可以通过梯度下降方法来求解。多层网络的每层之间输出加上sigmoid单元。sigmoid函数有个特性导数很容易求解,s'(x) = s(x) * (1 - s(x)).

多层网络可以使用反向传播算法来求解。反向传播算法仅能保证收敛到误差E的某个局部极小值,不一定收敛到全局最小值。尽管缺乏对收敛到全局最小误差的保证,反向传播算法在实践中仍是非常有效的函数逼近算法。一个解释是可以考虑含有大量权值的网络,它对应着维度非常高的空间曲面。梯度下降中某个权陷入局部极小值时,其他权未必是局部极小值。网络的权越多,空间曲面越多,就越有可能为梯度下降提供更多的"逃逸曲线",让梯度下降离开相对该单个权值的局部极小值。另外一个解释是,如果初始化权重为0时,sigmoid函数在0附近接近线性函数,不容易出现局部极小值;只有当权值增长一段时间之后,空间曲面才呈现高度非线性特征,这个时候才有比较多的局部极小值,而此时已经足够靠近全局最小值。为了缓解局部最小值情况,常见的启发式规则有:为梯度更新增加一个冲量项希望冲过狭窄的最小值;使用随机梯度下降而不是批量梯度下降;使用不同的随机权值来训练网络。

前馈网络的表征能力:

  • 布尔函数:任何布尔函数都可以被具有两层单元的网络准确表示。
  • 连续函数:任何有界连续函数可以由一个两层网络以任意小的误差逼近。
  • 任意函数:任意函数可以被一个有三层单元的网络以任意精度逼近。

ANN的高级课题

  • 其他可选的误差函数:1)增加权值惩罚项 2)交叉熵最小化
  • 其他可选的误差最小化过程(不一定是反向传播算法)
  • 递归网络以及动态修改网络结构

C6 贝叶斯学习

D表示数据集合,h表示假设

  • P(h)称为h的先验概率(prior probability), 它反映了我们所拥有的关于h是正确假设的机会的背景知识
  • P(D)代表训练数据D的先验概率,P(D|h)代表假设h成立时观察到数据D的概率。
  • P(h|D)表示给定数据D时h成立的概率,称为h的后验概率(posterios probability), 也是我们要求解的对象
  • 贝叶斯公式是P(h|D) = P(D|h) * P(h) / P(D).
  • 对于P(h|D)最大的假设被称为极大后验假设(maximum a posterior, MAP)
  • 如果P(h)和P(D)相同的话,那么MAP就是最大的P(D|h). P(D|h)被称为给定h时数据D的似然度(likelihood), 最大的P(D|h)称为极大似然(maximum likelihood, ML).
  • 如果我们对于假设先验概率相同的话,那么ML == MAP

在特定的前提下,不管是使误差平方最小化,使交叉熵最小化,以及使用最小描述长度,都是在寻找极大似然假设。

MAP假设并不一定是最优分类器。考虑一个情况包含三个假设h1, h2, h3, 后验概率分别是0.4, 0.3, 0.3. 那么h1是MAP. 但是如果针对一个实例,h1预测+1, 而h2, h3预测-1. 那么实际上-1概率是0.6, 比+1(0.4)更有可能。我们可以通过对合并所有假设输出并且使用后验概率加权来预测结果,这样得到的假设是才是最优的(贝叶斯最优分类器, Bayes optimal classifier).


C8 基于实例的学习

应用k-近邻算法的一个实践问题是,实例之间的距离是根据实例的所有属性计算的。如果20个属性里面只有2个属性和分类相关,那么其余18个属性会误导分类。换句话说,近邻之间的距离会被大量的不相关属性所支配,这种由于存在很多不相关属性所导致的难题,有时被称为维度灾难(curse of dimensionality)。最近邻方法对这个问题特别敏感。

  • 回归(regression): 逼近一个实数值的目标函数
  • 残差(residual): 逼近目标函数时误差f(x) - y
  • 核函数(kernel function): 一个距离函数,用来决定每个训练样例的权值

局部加权回归:局部只是目标函数逼近仅仅根据查询点附近的数据,加权指每个训练样例的贡献是由它与查询点间的距离加权的。局部线性加权回归则是:cost(x) = \SUM{x'表示x附近的k个近邻} (f(x') - y) ^ 2 * K(d(x', x)))

径向基函数(radial basis function, RBF): f(x) = w' * K(d(x', x)). 其中K为高斯核函数。径向基函数可以看做是一个两层的网络,第一层对输入做核函数映射,第二层对这些核函数做线性组合。理论上,只要以上高斯核函数数量足够多,那么RBF是可以逼近任何函数的。

消极学习延迟了如何从训练数据中泛化的决策,直到遇到一个新的查询案例才进行。积极学习则是在见到新的查询之前就做好泛化工作。消极学习方法可以对于每一个查询实例选择不同的假设(或目标函数的局部逼近),所以相当于可以通过很多局部逼近的组合(隐含地)表示目标函数;积极方法必须在训练时提交单个的全局逼近,一个覆盖整个实例空间的单一假设。当然积极方法可以使用合并了多个局部逼近的假设空间,就像RBF一样。然而,即使是这些合并的局部逼近,也不能使积极方法完全具有消极方法哪种针对未知查询作出假设的能力。

7 机器学习系统设计(Building Machine Learning Systems with Python)


然而根据亲身经验,我们知道做这些很"酷"的事–使用和调整机器学习算法比如SVM,NNS,或者同时支持两者–其实只需要耗费一位优秀机器学习专家的一点时间。看看下面这个典型的工作流程,你就会发现绝大部分时间花费在一些相当平凡的任务上:1)读取和清洗数据;2)探索和理解输入数据;3)分析如何最好地讲数据呈现给学习算法;4)选择正确的模型和学习算法;5)正确地评估性能。

你通常不会直接将数据输入机器学习算法,而是在训练前对部分数据进行提炼。很多时候,使用机器学习算法会让你得到性能提升的回报。一个简单算法在提炼后数据上的表现,甚至能够超过一个非常复杂的算法在原始数据上的效果。这部分机器学习流程叫做特征工程(feature engineering),通常是一个非常令人兴奋的挑战。你有创意和智慧,便会立即看到效果。

好特征的目标是在重要的地方取不同值,而在不重要的地方不变。一个很自然就会想到的问题式,我们能否自动滴把好特征选取出来。这个问题叫做特征选择(feature selection). 人们已经提出了很多方法来解决这个问题,但是在实践中,极简单的想法可能已经可以做得很好。

要提升效果,我们基本上有如下选择:1)增加更多的数据[learning_curve];2)考虑模型复杂度[cross_validation and validation_curve];3)修改特征空间;4)改变模型。


逻辑回归中的逻辑函数引入是这样的:

  • 线性回归的回归函数式 y = w * x
  • 逻辑回归中我们使用 log(p / (1-p) 来代替 y.
  • 逻辑函数h(x) = p = 1 / (1 + e^{-w * x})

朴素贝叶斯分类器要求所有特征之间相互独立。虽然在实际应用中很少有这种情况,但是在实践中它仍然能够达到非常好的正确率。

  • 我们要求解在已知特征F1,F2情况下样本属于某类别C的概率P(C|F1,F2). # 后验概率
  • 根据贝叶斯公式P(C|F1,F2) * P(F1,F2) = P(F1,F2|C) * P(C). # P(C)先验概率(prior) P(F1,F2|C)似然性(likehood)
  • 预测时因为P(F1,F2)都一样所以我们有时可以不用计算。
  • P(F1,F2|C) = P(F1|C) * P(F2|C) 这是因为F1,F2两个特征相互独立。
  • 实际过程中可能P(F1,F2) = 0. 那么可以通过加法平滑或是拉普拉斯平滑(laplacian smoothing), 又或是Lidstone平滑来处理。
  • 又因为在实际计算时多个p1 * p2…会出现精度问题,所以可以转为log(p1) + log(p2)…来处理。

回归惩罚函数

  • Ordinary Least Squares(OLS) 普通最小二乘法,普通线性回归
  • L1惩罚(L1范数, L1 norm)则是在OLS上增加a * |w|. Lasso法
  • L2惩罚(L2范数, L2 norm)则是在OLS上则加a * |w|^2. Ridge regressin(岭回归)
  • L1 + L2则是在OLS上增加a * |w| + b * |w|^2. Elastic Net(弹性网)

整个购物篮分析领域有时又叫做关联规则挖掘(association rule mining). 这些规则式:如果一个顾客购买了X的话,相对于基线,那么他更有可能购买Y。有一个指标来衡量每个规则的价值,称为提升度。提升度就是规则和基线所得到的概率之间的比值:life(X->Y) = P(Y|X) / P(Y). 其中P(Y|X)就是规则对应的概率,而P(Y)则是基线。Apriori是这方面问题的经典算法。


下面这些理由会告诉你为什么在实践中应该尽可能消减维度:

  • 多余的特诊会影响或误导学习器。并不是所有机器学习方法都会有这种情况(SVM), 但是大多数模型在维度较小的情况下会比较安全。
  • 另一个反对高维特征空间的理由是,更多特征意味着更多参数需要调整,过你喝的风险也越大。
  • 我们用来解决问题的数据的维度可能只是虚高,真实维度可能比较小。
  • 维度越少意味着训练越快,更多东西可以尝试,能够得到更好的结果。
  • 如果我们想要可视化数据,就必须限制在两个或者三个维度上。

8 统计学习方法(李航)


C1 统计学习方法概论

统计学习三要素:模型 + 策略(cost-function) + 算法.

交叉验证的基本想法是重复地使用数据:把给定的数据进行切分,将切分的数据集组合为训练集与测试集,在此基础上反复地进行训练测试以及模型选择。 1)简单交叉验证. 2)S折交叉验证(随机地将已给数据切分为S个互不相交的大小相同的子集,然后利用S-1个子集的数据训练模型,利用剩余1个子集测试模型。重复S次). 3)留一交叉验证(S=N的特殊情况,通常在数据缺乏的情况下使用)

监督学习可分为生成方法(generative approach)和判别方法(discriminative approach). 所学到的模型分别称为生成模型(generative model)和判别模型(discriminative approach).

  • 生成方法学习联合概率分布P(X,Y),然后求解条件概率分布P(Y|X)=P(X,Y) / P(X)作为预测模型。之所以称为生成方法,是因为模型表示了给定输入X产生输出Y的生成关系。比如朴素贝叶斯和隐式马尔可夫模型。
  • 判别方法直接学习决策函数f(X)或者P(Y|X), 关心给定输入X应该预测什么样的输出Y。比如kNN, 感知机,决策树,逻辑回归,最大熵,SVM,提升模型和条件随机场等。

标注问题(tagging)输入是一个观测序列,输出式一个标记序列或状态序列。标注问题的目的在于学习一个模型,使它能够对观测序列给出标记序列作为预测。评价标注模型的指标与评价分类模型的指标一样,常用的有标注准确率,精确率和召回率。常用的统计学习方法有:隐式马尔可夫模型,条件随机场。


C2 感知机

  • 感知机(perceptron)是二类分类的线性分类模型, 对应于在输入空间(特征空间)中将实例划分为正负两类的分离超平面, 属于判别模型.
  • 感知机学习旨在求出将训练数据进行线性划分的分离超平面, 学习算法分为原始形式和对偶形式. 感知机是神经网络与支持向量机的基础.
  • 如果训练数据是线性可分时, 感知机算法迭代是收敛的. 当训练数据线性不可分时, 感知机学习算法不收敛, 迭代结果会发生震荡.
  • 感知机学习算法存在许多解, 这些解既依赖于初值的选择, 也依赖于迭代过程中误分类点的选择顺序. 为了得到唯一的超平面, 需要对分类超平面增加约束条件, 这就是SVM的想法.

C3 kNN

KNN三要素: 距离度量, k值选择和分类决策规则.

  • 常用的距离度量是欧式距离以及更一般的Lp距离. (Minkowski距离 Lp(x,y) = (\SUM (x(i) - y(i)) ^ p) ^ (1/p))
  • k值小时, 就相当于用较小领域中的训练实例进行预测. "学习"的近似误差(approximation error)会减小, 只有与输入实例较近的(相似的)训练实例才会对预测结果起作用. 但缺点是"学习"的估计误差(estimation error)会增大, 预测结果会对近邻的实例点非常敏感. 如果近邻的实例点恰好是噪声, 预测就会出错. 换句话说, k值的减小就意味着整体模型变得更加复杂, 容易发生过拟合.
  • k值大时, 就相当于用较大领域中的训练实例进行预测. 优点是可以减少学习的估计误差. 但缺点是学习的近似误差会增大. 这时与输入实例较远(不相似的)的训练实例也会对预测其作用, 使预测发生错误. k值的增大就意味着整体模型的变得简单.
  • 常用的分类决策规则是多数表决, 对应于经验风险最小化.

kNN的实现需要考虑如何快速搜索k个最邻近点. kd树是一种便于对k维空间中的数据进行快速检索的数据结构. kd树是二叉树, 表示对k维空间的一个划分, 其每个节点对应于k维空间划分中的一个超矩形区域. 利用kd树可以省去对大部分数据点的搜索, 从而减少搜索的计算量.


C4 朴素贝叶斯

朴素贝叶斯方法他训练数据集学习联合概率分布P(X,Y). 具体地学习先验概率分布P(Y)以及条件概率分布P(X|Y). 然后根据联合概率分布选择后验概率最大的y. P(Y|X) = P(X,Y) / P(X).

条件概率分布P(X|Y)有指数量级的参数(因为X的组合), 所以难以估计实际概率. 朴素贝叶斯对条件概率分布做了条件独立性的假设: X的各个特征之间相互独立. 这样P(X|Y) = \PROD (P(X(i) | Y)).

我们通过极大似然来估计来先验概率以及条件概率. 比如先验概率P(Y=ck)的极大似然估计是# of ck in traning set / # of traning set. 条件概率P(X(i) | Y=ck) = # of (X(i), Y=ck) / # of (Y=ck).

但是上面的条件概率可能# of (Y=ck)会为0. 解决这一问题的方法是采用贝叶斯估计: 在分子上增加一个参数a, 分母上增加Z*a(Z为归一化参数). 如果a=0那么就是极大似然估计, 如果a=1那么就是拉普拉斯平滑(Laplace smoothing).

P(H(hypotheses) | E(evidence)) = P(H) * P(E/H) / P(E). 其中P(H)称为先验概率(prior probability), P(H/E)称为后验概率(post probability), P(E/H)称为证据似然值(likehood of evidence).


C5 决策树

决策树(decision tree)是一种基本的分类和回归方法. 它可以认为是if-then规则的集合, 也可以认为是定义在特征空间与类空间上的条件概率分布. 决策树学习通常包括3个步骤: 特征选择, 决策树的生成和决策树的修剪.

决策树学习的损失函数通常是正则化的极大似然函数. 决策树学习的策略是以损失函数为目标函数的最小化. 当损失函数确定之后, 学习问题就变为在损失函数意义下选择最优决策树的问题. 因为从所有可能的决策树中选取最优决策树是NP完全问题, 所以现实中决策树学习算法通常采用启发式方法, 近似求解这一最优化问题, 得到的决策树也是次最优(sub-optimal)的.

决策树学习算法通常是递归地选择最优特征, 根据该特征对训练数据进行分割, 使得对各个子数据集有一个最好的分类的过程. 这一过程对应着对特征空间的划分, 也对应着决策树的构建, 直到所有训练数据子集被正确分类. 这样构建好之后泛化能力会比较差, 可以通过剪枝去掉过分细分的叶子节点使其回退到父节点甚至更高的节点. 决策树的生成对应于模型的局部选择, 决策树的剪枝对英语模型的全局选择. 决策树的生成只考虑局部最优, 相对地, 决策树的剪枝则考虑全局最优.

特征选择可以通过信息增益或者是信息增益比来指导:

  • 信息增益 g(D, A) = H(D) - H(D|A). 表示特征A对训练数据集合D的信息增益(互信息). 其中H(D)称为信息熵, 而H(D|A)称为条件熵. 因为我们是通过数据估计(贝叶斯估计, 或者是极大似然估计)来计算P的, 所以对应称为经验信息熵(empirical entropy)以及经验条件熵(empirical conditional entropy). ID3算法使用这个指标.
  • 信息增益比 gR(D, A) = g(D, A) / H(D, A) 其中H(D, A)表示训练数据关于特征A的熵. 以信息增益作为划分训练数据集的特征, 存在偏向于选择取值比较多的特征的问题. 所以我们通过信息增益比来进行校正. C4.5算法使用这个指标.

决策树剪枝的损失函数定义为: 每个叶子节点上经验熵之和 + a * |T|(叶子数量). a可以控制模型复杂度: 较大a可以促使选择简单的模型树, 较小a可以促使选择比较复杂的模型树. 树的剪枝算法则是对比从某个节点剪枝前后损失函数大小, 如果损失函数变小的话那么就可以进行剪枝. 决策树的剪枝算法可以由在一种动态规划的算法实现.

CART(classification and regression tree)模型假设决策树是二叉树. CART既能够用于分类也能够用于回归, 对回归树选用平方误差最小准则, 对分类树使用基尼指数(Gini index)准则, 进行特征选择. 对于回归树每次选择特征, CART寻找最优切分变量(splitting variable)和切分点(splitting point), 以对应分类里面average-y为中心计算最小二乘, 使得这个最小二乘极小化. 而对于分类树准则, 类似选择最大信息增益(比), 只不过这里选择Gini index. Gini(p) = \SUM (p(k) - (1 - p(k))) = 1 - \SUM p(k) ^ 2. 其中k对于表示对应类. 我们选择的是Gini(D) - Gini(D, A)最大的特征. #note: CART剪枝有点复杂没有看懂.


C6 逻辑回归与最大熵模型

最大熵是概率模型学习的一个准则, 将其推广到分类问题得到最大熵模型(maximum entropy model). 逻辑回归与最大熵模型都是对数模型, 都是以似然函数为目标函数的最优化问题. 通常通过迭代算法求解. 从最优化的观点看, 这时的目标函数具有很好的性质: 它是光滑的凸函数, 因此多种最优化的方法都能使用, 且保证能够找到全局最优解. 常用的方法有改进的迭代尺度算法(improved iterative scaling, IIS), 梯度下降法, 牛顿法(newton method)和拟牛顿法(quasi newton method). 牛顿法和拟牛顿法一般收敛速度更快.

二项逻辑回归 vs. 多项逻辑回归。二项逻辑回归的似然函数是\PROD ((f(x) ^ y) * ((1 - f(x)) ^ (1-y))),为了方便计算取对数似然函数则是\SUM (y * log(f(x)) + (1-y) * log(1-f(x))) #note: 多项逻辑回归似然函数是什么?

最大熵原理认为, 学习概率模型时, 在所有可能的概率模型(分布)中, 熵最大的模型也是最好的模型. 通常用约束条件来确定概率模型的集合, 所以最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型.


C7 支持向量机

支持向量机(SVM)是一种二类分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机。支持向量机还包括核技巧,这使它称为实质上的非线性分类器。支持向量机学习策略就是间隔最大化,可以形式化为求解一个凸二次规划(convex quadratic programming)的问题,也等价于正则化的合页损失函数的最小化问题。序列最小最优化算法(sequential minimal optimization, SMO)是SVM学习的一种快速算法。

支持向量机学习方法包含构建由简至繁的模型,简单模型是复杂模型的基础,也是复杂模型的特殊情况:

  • 线性可分支持向量机(linear support vector machine in linearly separable case). 线性完全可分,硬间隔最大化(hard margin maximization)
  • 线性支持向量机(linear support vector machine). 线性近似可分,软间隔最大化(soft margin maximization)
  • 非线性支持向量机(non-linear support vector machine). 线性不可分但是通过核技巧(kernel trick)可以软间隔最大化

当输入空间为欧式空间或离散集合,特征空间为希尔伯特空间时,核函数(kernel function)表示将输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。核方法(kernel method)是比支持向量机更为一般的机器学习方式。

首先看线性可分支持向量机。我们得到(w,b)(法向量和截距)之后,可以定义分离超平面为wx+b=0. 因为我们是要确保间隔最大,训练数据集合的样本点中与分离超平面距离最近的样本点的实例称为支撑向量(support vector). 对于y=1的点,wx+b=1, 对于y=-1的点,wx+b=-1. 支撑向量距离超平面的距离为1/|w|. 图中H1, H2是间隔边界,上面所有点都是支撑向量,H1和H2之间的距离称为间隔(margin) = 2/|w|.

sml-svm-hard-margin.png

然后在看线性支持向量机。因为不是线性完全可分,所以引入松弛变量,然后在损失函数里面增加对松弛变量的惩罚。最终得到的是软间隔最大的分离超平面,不过这个超平面并不唯一,并且软间隔的支持向量可以在间隔边界上,也可以在超平面和间隔边界之间,也可以在误分的一侧。

sml-svm-soft-margin.png

学习的对偶算法里面可以发现,目标函数里面所有和输入相关的项,都转变称为了特征向量之间的内积。这就是为什么可以使用核函数的原因。核函数的定义是:假设X是输入空间,H为特征空间,如果存在一个X到H的映射f, 使得函数K(x1,x2)满足条件K(x1,x2) = f(x1) * f(x2)(内积). 则称K(x,y)为核函数,也称为正定核(positive definite kernel function)。核技巧的想法是:在学习与预测中只定义核函数K(x,y)而不显示定义映射函数f.


C8 提升方法

提升(boosting)方法是一种常用的统计学习方法,在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类的性能。通常需要解决两个问题:1)每一轮如何改变训练数据的权值或者是概率分布 2)如何将弱分类器组合称一个强分类器。AdaBoost算法是比较有代表性的一个提升方法:在改变样本权重时,提高被错误分类样本的权值,降低被争取分类样本权值;在组合分类器时,加大分类误差率小的分类器的权值,而减小分类误差率大的分类器权值。提升树是以分类树或回归树为基本分类器的提升方法。


C9 EM算法及其推广


C10 隐马尔可夫模型


C11 条件随机场


C12 统计学习方法总结

sml-conclusion.png

9 关于CNN(卷积神经网络)

http://blog.csdn.net/stdcoutzyx/article/details/41596663 是一篇非常好的关于CNN的入门文章

CNN常用于处理图像和视频数据,在DNN的基础(前向反馈网络结构,使用BP来做参数训练)增加了一些扩展技术: 1. 局部感知(卷积核). 2. 参数共享 3. 多卷积核 4. pooling/subsampling(下采样).


局部感知

卷积神经网络有两种神器可以降低参数数目,第一种神器叫做局部感知野(local receptive fields)。一般认为人对外界的认知是从局部到全局的,而图像的空间联系也是局部的像素联系较为紧密,而距离较远的像素相关性则较弱。因而,每个神经元其实没有必要对全局图像进行感知,只需要对局部进行感知,然后在更高层将局部的信息综合起来就得到了全局的信息。网络部分连通的思想,也是受启发于生物学里面的视觉系统结构。视觉皮层的神经元就是局部接受信息的(即这些神经元只响应某些特定区域的刺激)。如下图所示:左图为全连接,右图为局部连接。

cnn-lsf.jpg

在上右图中,假如每个神经元只和10×10个像素值相连,那么权值数据为1000000×100个参数,减少为原来的万分之一。而那10×10个像素值对应的10×10个参数,其实就相当于卷积操作。


参数共享

但其实这样的话参数仍然过多,那么就启动第二级神器,即权值共享。在上面的局部连接中,每个神经元都对应100个参数,一共1000000个神经元,如果这1000000个神经元的100个参数都是相等的,那么参数数目就变为100了。

怎么理解权值共享呢?我们可以这100个参数(也就是卷积操作)看成是提取特征的方式,该方式与位置无关。这其中隐含的原理则是:图像的一部分的统计特性与其他部分是一样的。这也意味着我们在这一部分学习的特征也能用在另一部分上,所以对于这个图像上的所有位置,我们都能使用同样的学习特征。

更直观一些,当从一个大尺寸图像中随机选取一小块,比如说 8x8 作为样本,并且从这个小块样本中学习到了一些特征,这时我们可以把从这个 8x8 样本中学习到的特征作为探测器,应用到这个图像的任意地方中去。特别是,我们可以用从 8x8 样本中所学习到的特征跟原本的大尺寸图像作卷积,从而对这个大尺寸图像上的任一位置获得一个不同特征的激活值。

如下图所示,展示了一个3×3的卷积核在5×5的图像上做卷积的过程。每个卷积都是一种特征提取方式,就像一个筛子,将图像中符合条件(激活值越大越符合条件)的部分筛选出来。

cnn-wt-sharing.gif

#note: 完成前面两个操作之后,假设原始图像大小20 * 20, filter/卷积核大小5 * 5, 那么我们得到卷积之后的图像大小是(20 - 5 + 1) = 16 * 16,每个像素点是有5*5个connections. 所以共有16 * 16 * 5 * 5个connections, 但是只有5 * 5个不同的weights.(因为参数共享原因)


多卷积核

#note: 一个filter/卷积核对应这个图像的一种可能特征,实际上我们会想多尝试几种可能的特征,所以我们可以使用多卷积核(或称为feature maps).

上面所述只有100个参数时,表明只有1个10*10的卷积核,显然,特征提取是不充分的,我们可以添加多个卷积核,比如32个卷积核,可以学习32种特征。在有多个卷积核时,如下图所示:

cnn-feature-maps.jpg

上图右,不同颜色表明不同的卷积核。每个卷积核都会将图像生成为另一幅图像。比如两个卷积核就可以将生成两幅图像,这两幅图像可以看做是一张图像的不同的通道。

#note: 还是以上面为例的话,如果我们使用500 feature maps的话,那么我们的connections数目变为16 * 16 * 5 * 5 * 500, 权重数量也变为5 * 5 * 500.


下采样

在通过卷积获得了特征 (features) 之后,下一步我们希望利用这些特征去做分类。理论上讲,人们可以用所有提取得到的特征去训练分类器,例如 softmax 分类器,但这样做面临计算量的挑战。例如:对于一个 96X96 像素的图像,假设我们已经学习得到了400个定义在8X8输入上的特征,每一个特征和图像卷积都会得到一个 (96 − 8 + 1) × (96 − 8 + 1) = 7921 维的卷积特征,由于有 400 个特征,所以每个样例 (example) 都会得到一个 7921 × 400 = 3,168,400 维的卷积特征向量。学习一个拥有超过 3 百万特征输入的分类器十分不便,并且容易出现过拟合 (over-fitting)。

为了解决这个问题,首先回忆一下,我们之所以决定使用卷积后的特征是因为图像具有一种"静态性"的属性,这也就意味着在一个图像区域有用的特征极有可能在另一个区域同样适用。因此,为了描述大的图像,一个很自然的想法就是对不同位置的特征进行聚合统计,例如,人们可以计算图像一个区域上的某个特定特征的平均值 (或最大值)。这些概要统计特征不仅具有低得多的维度 (相比使用所有提取得到的特征),同时还会改善结果(不容易过拟合)。这种聚合的操作就叫做池化 (pooling),有时也称为平均池化或者最大池化 (取决于计算池化的方法)。

cnn-down-pooling.gif

#note: 对pooling-layer在做BP时候需要单独处理,因为这个激活函数是不可导的。

#todo: 据说pooling不仅仅能够减少计算量,还可以引入旋转(rotate)不变性? 我可以理解pooling可以引入平移(shift)以及扭曲(distortion)不变性。


在实际应用中,往往使用多层卷积,然后再使用全连接层进行训练,多层卷积的目的是一层卷积学到的特征往往是局部的,层数越高,学到的特征就越全局化。下面这幅图就是 LeNet-5 的结构

cnn-lenet-5.png

S2有6个fmaps, C3有16个fmaps, 两者之间并不是完全连接的。这样可以打破网络对称性,强迫C3上的不同fmaps根据不同输入学习到互补信息。

As Dr. LeCun explained it, his non-complete connection scheme would force the feature maps to extract different and (hopefully) complementary information, by virtue of the fact that they are provided with different inputs. One way of thinking about this is to imagine that you are forcing information through fewer connections, which should result in the connections becoming more meaningful.

具体连接配置是这样的

cnn-lenet-5-cf.png

另外在关于激活函数方面,这里 的建议是内部使用ReLu, 倒数第二层换成sigmoid, 最后使用softmax. 这里 (还给出了具体实现!)的建议则是使用tanh(作者不太建议使用sigmoid), 最后使用softmax. 不知道能不能综合考虑,内部使用ReLu, 倒数两层换为tanh和softmax.


粗略地看了一下"Gradient-Based Learning Applied to Document Recognition"的Section II.

  • 通常图像是具有局部相关性的,所以可以使用local receptive field以及weight sharing.
  • 个人理解:使用multiple feature maps可以用来引入旋转(rotate)不变形,可以使用多个卷积核来学习旋转
  • pooling可以引入平移(shift)以及扭曲(distortion)不变性
  • C5这层实际上是一个卷积层,只不过恰好conv kernel size = 5.

没有太理解F6/Output. 不过在这两层里面值得一体的是,论文里面说如果classes太多的话(比如84种),那么最好不要采用native-bitv方式来定义输出(native-bitv是我随便取的名字,如果classes=84, 那么输出就是84长度的bit-vector,其中有一个bit为1其他全部为0),否则使用sigmoid簇函数作为loss function效果非常差(当然可以使用softmax). LeCun给的方式则是RBF/Euclidean作为loss function, 输出表示方式允许在多个bit上为1. 如果将定义输出表示称为灰度图像的话,就是下面这个样子

cnn-output-code.png

10 目前机器学习的瓶颈有哪些

作者:李瞬生 链接:https://www.zhihu.com/question/22370288/answer/23223650 来源:知乎 著作权归作者所有,转载请联系作者获得授权。

我不是专家,只能说我自己学习过程中感觉到的瓶颈。

  • 计算时间

在工业界的训练数据动辄上TB,每天都得train一大批的model。光从计算时间上,就限制了SVM等相对复杂算法的流行程度。个人在微软、亚马逊经常见到的是逻辑回归train天下。偶尔有特殊的问题会用上SVM,但规模很小,且training data不会每天更新。因为只有logistic regression这种程度的方法在计算上是可行的。

  • 模型诠释

如果是logistic regression来train的model,那么最起码人还能看到每个feature的权重。 但若使用SVM、神经网络或更复杂的方法,train出来的结果首先不说,其模型对人而言是很难进行诠释的。这也会限制商业上的应用。因为我作为卖家都不知道自己train出来的model究竟该怎样诠释,外行的买家大概也只能够不明觉厉了吧。

  • 过于灵活相当于没有方法

面对一个问题,可选择的机器学习模型首先就有很多。即使选定了几种方法,每一种方法还会有n多变种。比如SVM如此多的kernel、神经网络的activation function等。就算把这个选好了,还要去tune model的parameter。

最可恨的是,这个流程很难总结出一套系统的经验指导。更多时候都只能trial and error。这相当于面对一个问题,临时去找方法、试各种方法一样。 灵活过头了就变成玄学了。正是因为玄之又玄,机器学习养活了一大批论文灌水的人。

11 机器学习里,数学究竟多重要?

链接

过去几个月里,有不少人联系我,向我表达他们对数据科学、对利用机器学习技术探索统计规律性,开发数据驱动的产品的热情。但是,我发现他们中有些人实际上缺少为了获取有用结果的必要的数学直觉和框架。这是我写这篇文章的主要原因。

最近,许多好用的机器和深度学习软件变得十分易得,例如 scikit-learn,Weka,Tensorflow,等等。机器学习理论是与统计学、概率论、计算机科学、算法等方面交叉的领域,它产生于从数据出发的学习迭代,试图找出用于开发智能应用的隐藏的洞见。尽管机器学习和深度学习有无限的可能性,对这些技术有一个全面的数学理解对理解算法的内部工作机制、获取好的结果是有必要的。

为什么要关心数学?

为什么机器学习中的数学很重要?这个问题的理由我想强调以下几点:

  1. 选择合适的算法,要考虑的包括算法准确性、训练时间、模型复杂度、参数的数量和特征数量。
  2. 选择参数设置和验证策略。
  3. 理解偏差与方差的权衡以确定欠拟合和过拟合。
  4. 预估正确的置信区间和不确定性。

你需要多高的数学水平?

试图了解一个例如机器学习这样的跨学科领域,主要的问题是必要的数学知识的量,以及理解这些技术需要的数学水平。这个问题的答案是多方面的,取决于个人水平和兴趣。对数学公式和机器学习的理论发展的研究一直在进行着,一些研究人员研究的是更先进的技术。以下我将说明我认为成为一名机器学习科学家/工程师需要的最低程度的数学,以及每个数学概念的重要性。

ml-math-basics.png

1.线性代数

Skyler Speakman曾说:"线性代数式21世纪的数学",我完全赞同该论述。在ML领域,线性代数无处不在。主成分分析(PCA)、奇异值分解(SVD)、特征分解、LU分解、QR分解、对称矩阵、正交化&标准正交化、矩阵运算、投射、特征值&特征向量、向量空间和规范等这些概念对理解机器学习的优化方法都是必须的。我认为线性代数很棒的一点是,互联网上的资源非常多。我总是说传统课堂要消亡,因为互联网上有如此大量的资源。我最喜欢的线性代数课程是MIT的Gilbert Strang教授的。

2.概率论与数理统计

机器学习和数理统计并不是完全不同的领域。事实上,最近有人把机器学习定义为"在Mac上做数理统计"。ML需要的数理统计基础和概率论知识包括组合数学、概率规则&公理、贝叶斯定理、随机变量、方差和均值、条件和联合分别、标准分布(伯努利、二项、多项、统一和高斯)、矩母函数、最大似然估计(MLE)、先验和后验、最大后验估计(MAP)和采样方法。

3.多元微积分

必要的概念包括微积分、偏导数、向量函数、方向梯度、Hessian、Jacobian、Laplacian和Lagragian分布。

4.算法和复杂性优化

这对理解机器学习算法的计算效率和可扩展性以及数据集的开发稀疏性很重要。需要数据结构(二叉树、Hashing、Heap、Stack等等)的知识,以及动态编程、随机&次线性算法、图形、梯度/随机趋势、以及原对偶方法的知识。

5.其他

这包括上述4个主要领域没有涉及的其他数学概念。包括实分析与复分析(集合和序列、拓扑结构、度量空间、单值和连续函数、极限)、信息理论(熵、信息增益)、函数空间和流形。

下面是部分机器学习所需数学概念的一些MOOC和学习资料:

  1. Khan Academy's Linear Algebra, Probability & Statistics, Multivariable CalculusandOptimization.
  2. Coding the Matrix: Linear Algebra through Computer Science Applications by Philip Klein, Brown University.
  3. Linear Algebra – Foundations to Frontiers by Robert van de Geijn, University of Texas.
  4. Applications of Linear Algebra, Part 1 and Part 2. A newer course by Tim Chartier, Davidson College.
  5. Joseph Blitzstein – Harvard Stat 110 lectures
  6. Larry Wasserman's book – All of statistics: A Concise Course in Statistical Inference .
  7. Boyd and Vandenberghe's course on Convex optimisation from Stanford.
  8. Linear Algebra – Foundations to Frontiers on edX.
  9. Udacity's Introduction to Statistics.

最后,本文的主要目的是提供有关机器学习所需的重要数学概念的建议和有用的资源。但是,有些机器学习爱好者可能是数学初学者,会觉得这篇文章令人沮丧(这并不是我的目的)。对初学者来说,你并不需要先学好大量数学知识再开始做机器学习。正如这篇文章提到的,最基本的需要是数据分析,然后你可以在掌握更多技术和算法的过程中继续学习数学。

12 一些介绍RNN/LSTM的好文章

13 深度學習(Deep Learning)自學素材推薦

https://dt42.github.io/2016/04/27/deep-learning-material-recommendations/

網路上關於深度學習的資料實在太多了,這裡列出的只是我個人讀過覺得相當不錯的資源,看不夠的話請右轉 Google 搜尋「Deep Learning」,絕對能滿足絕大部分的需求。如果有好的文章卻被漏掉了,也非常歡迎留言推薦,一定儘快補上。

機器學習

如果完全還不知道 Deep Learning 是什麼,甚至對機器學習 (Machine Learning) 都沒有概念,Andrew Ng 在 Coursera 開的課程(1)絕對能給你一個好的開始,雖然是英文授課,但有中文字幕可以參考。除了 Andrew Ng 開的課,華語世界也有個相當熱門的 MOOC 課程─台大林軒田老師在 Coursear 上教授的 Machine Learing;雖然課程已經結束,但所有的影片都公開在 Youtube 上(2)。不過要提醒一下,雖然林老師是中文授課,但可別因此覺得親切,與 Andrew 的課程相比,林軒田老師的課程更重視理論根基,數學很重。

深度學習

對機器學習有概念,但不知道什麼是深度學習的讀者,可以從 PyData 2015 London 的一個 talk 開始(3),它提供了簡短的摘要,從 Learning 的概念開始講起,到介紹如何使用 Python libraries 來達成基本的深度學習任務。有一點概念以後,相當推薦 Michael Nielsen 所寫的 Neural Networks and Deep Learning(4),這篇深入淺出地帶領讀者從最基本的 Perception,一路走到近年來深度學習熱門的技巧像是 Dropout, Batch Normalization 等等,配合大量的 Javascript 導讀與實作範例,是本非常實用的小書。想要收藏更完整的 Deep Learning 知識,可以參考這本由 Ian Goodfellow, Yoshua Bengio 與 Aaron Courville 合著的 Deep Learning(5)。一邊唸書的同時,推薦可以配合著看 Christopher Olah 的部落格(6),她把很多不易理解的概念(例如 Backpropagation)做了視覺化,或者是用不同的角度切入,常常能帶給讀者「原來還可以這樣看啊!」的收穫。對於對深度學習有相當好的理解、甚至自己開發新 model 的讀者,如果遇到困難,推薦可以看看 Russell Stewart 的這篇 Introduction to debugging neural networks (8),或許解 bug 的靈感就藏在其中。

電腦視覺 (Computer Vision)

Deep Learning 其實不只能拿來做視覺辨識,它在自然語言、推薦系統甚至金融商品預測等等也都有很好的表現。不過本篇文章是以視覺辨識為主要範例,如果對電腦視覺有興趣,Stanford 開設的 CS231n Computer Vision (7)是很好的入門課程。

  1. https://www.coursera.org/learn/machine-learning/
  2. https://www.youtube.com/playlist?list=PLXVfgk9fNX2I7tB6oIINGBmW50rrmFTqf
  3. Python For Image Understanding: Deep Learning with Convolutional Neural Nets
  4. http://neuralnetworksanddeeplearning.com/index.html
  5. http://www.deeplearningbook.org/
  6. http://colah.github.io/
  7. http://cs231n.stanford.edu/
  8. http://russellsstewart.com/blog/0

14 Generative Adversarial Networks: The Basic Idea

GAN-basic-idea.jpg

15 Best Practices for Applying Deep Learning to Novel Applications

PDF

Understanding what is happening in your model will affect the success of your project. Carpenters have an expression “measure twice, cut once”. You should think “code once, measure twice”. In addition to evaluating the output, you should visualize your architecture and measure internal entities to understand why you are getting the results you are obtaining. Without diagnostics, you will be shooting in the dark to fix problems or improve performance.

16 数据应该使用哪种图形表达

chart-suggestions.jpg

comments powered by Disqus