算法channel

公众号：
alg-channel

功能介绍
99%是工程与学术相结合的原创干货和笔记，从基础算法，到机器学习，深度学习，NLP，再到工程级的工具库使用等10余个频道，

经典文章推荐：

1.深度学习和自然语言处理：介绍

这门课程比较新，结合深度学习，神经网络，同时注重工程应用，比如应用Tensorflow解决自然语言处理领域的问题，使用的语言是Python，也是深度学习领域大家都在用的，所以强烈推荐大家与我一起学习Richard Socher大神的这门课及课程给出的参考资料。计算

Richard 的第一讲是对自然语言处理的介绍，主要包括以下几方面：

1) 自然语言处理是什么？
2) 人类语言的本质
3) 理解语言的难点在哪里？
4) Richard大神亲抒自然语言处理目前的工程应用，各个领域的，激动中。

1 NLP是什么
自然语言处理是计算机科学，人工智能和语言学的交叉科学，旨在让计算机去处理或理解自然语言，以便做一些有意义的事情。

理解和表达语言的意思是一件困难而值得探索的事。

精准的语言理解是AI的全部。

2 语言特点
人类语言大多是离散地，带有符号表达，可以分类的，传递含义的系统。语言符号的分类可以为：声音，手势，书写，图像。




3 深度学习
经典标准的机器学习不同，深度学习会自动地学到好的特征或表示，如图所示，它会尝试学到h1, h2, h3, h4(输出层)这四个层的表达关系，输入的x可以是：声音，像素，字符，词语。在这门课程中会介绍已经很好地解决了NLP问题的各种不同神经网络，而不会详细的介绍神经网络的发展历程，关于NN的发展历史，请参考之前的推送： 机器学习、深度学习干货分享 。     深度学习是在2010年开始逐渐超越传统的机器学习，是什么使得DL超越了ML呢？



大数据技术的发展极大地促进了DL的发展；
更快的计算机，多核CPU/GPU的发展；
更好的算法出现：包括，更易于学习的中间件的表达，高效的端到端的联合系统学习，用上下文和任务间切换的学习方法，更好的正则化技术和最优化技术。

这些发展首先应用在了语音识别，图像识别，然后是NLP。DL应用在语音识别是先例，代表性的论文：Context-Dependent        Pre-trained Deep        Neural        Networks        for Large Vocabulary        Speech        Recognition Dahl        et        al.        (2010) 后来应用在图像处理上，代表性的论文：
ImageNet        Classification        with        Deep Convolutional        Neural        Networks        by Krizhevsky, Sutskever,        &        Hinton (2012)，用于图像识别：






4 NLP难点
表达具有复杂性，学习和使用语言知识，情景知识，上下文知识，几乎所有我们能听闻、观察到的知识，解释翻译都得依赖于这些。

同时，人类的语言是模棱两可的。

近期，自然语言处理已经取得的进展，大家可以参考之前的推送：
一文了解自然语言处理的每个范畴用到的核心技术，难点和热点(1)


更多链接

2.这是一道算法面试题，不妨看看

几个月前参加的一次大厂面试，聊到一半，面试官拿起笔，让我算一下从 start 到 finish 的最短路径。这道题的形象话表示如下所示，大家看到这幅图，或许有些小伙伴可能遇到过，有些可能没遇到过，没遇到过的不妨想一想，如何求解。

你有答案了吗？ 下面分析下如何思考这个算法题。

动态规划

要想从start 点到 finish 点，那么，必然经过 h1 或 h2 点，所以，问题转化为：求 start 点到 h1 点，或 start 点到 h2点的路径中的较小者，这相当于将问题域变小了1，递归下去，直到问题域变为 1 个点，如下图所示，

这是动态规划思想的典型运用，以下是一版 C# 代码的实现，熟悉 JAVA 的看这些代码也没有问题。

public int MinPathSum(int[,] grid)

        {

            int m=grid.GetUpperBound(0)+1; //0-dimension element size

            int n=grid.GetUpperBound(1)+1; //1-dimension element size

            int[,] sumdp = new int[m,n];

            sumdp[0,0]=grid[0,0];

            //two boundaries:

            for (int i = 1; i < m; i++)

                sumdp[i,0] = sumdp[i-1,0]+grid[i,0];

            for (int i = 1; i < n; i++)

                sumdp[0,i] = sumdp[0,i-1]+grid[0,i];

            for (int i = 1; i < m; i++)

            {

                for (int j = 1; j < n; j++)

                {

                    sumdp[i, j] = Math.Min(sumdp[i - 1, j], sumdp[i, j - 1]) + grid[i,j];

                }

            }

            return sumdp[m - 1, n - 1];

        }

动态规划思想最重要的两个点：

• 找出迭代方程， sumdp[i, j] = Math.Min(sumdp[i - 1, j], sumdp[i, j - 1]) + grid[i,j];
• 空间复杂度换取时间复杂度，代码中的 int[,] sumdp = new int[m,n];
  
  

总结

动态规划思想，是算法面试中经常问到的，大家可以详细参考相关链接中的文章再具体了解下什么样的问题适合用动态规划思想来求解，以及动态规划求解的两个点。

希望大家接下来面试算法岗，被问到动态规划问题时，准确击中要害，成为自己的加分项。

3.机器学习：不得不知的概念（1）


01你会学到什么？

接下来，在这个系列总您将会学到机器学习中非常重要的基本的概念，机器学习模型好坏的重要衡量指标，和机器学习中非常重要的一个概念：归纳偏好，它避免使我们掉入浩瀚的假设空间中。


02不得不知

要想精确地入门机器学习，有一些概念，是我们得准确掌握的，这通常是第一步，走好这一步能为未来构建机器学习大厦打下坚实的地基，同时为你理解基于这些概念的理论和算法提供必不可少的帮助。


那么我们来看一下，这些基本概念吧！

数据集（data set）

记录的集合，假如我们用3个特征，分别为色泽，根蒂，响声来描述西瓜的特点，并且拿到了基于这3个特征的10万条记录，其中一条记录的取值为：

色泽=光亮，根蒂=坚硬，响声=清亮

如果记录到.csv文件中，这个文件的结构可以记为： fruit[100000][3] ，这样一个二维数组，行数为10万，列数为3（因为有3个特征）。

示例（instance）

每条记录是关于一个事件或对象的描述，也称为样本，比如以上其中一条记录

色泽=光亮，根蒂=坚硬，响声=清亮

这个看做是一个实例

属性（attribute）

反映事件或对象在某方面的表现或性质的事项，例如色泽，根蒂，响声等，又称为特征（feature）。

属性上的取值，如青绿，浊响等，称为属性值（attribute value）。

样本空间（sample space）

又称为属性空间（attribute space），或输入空间。它可以理解为训练数据中实际出现的所有属性值构成的集合空间，如上文中提到的10万条西瓜记录，每条记录有3个属性取值，组成了一个fruit[100000][3] 的样本空间。和它有点类似的一个概念叫做假设空间（hypothetical space），它是理论上的所有可能属性值构成的集合空间。

如果我们在购买某个股票时假定根据两个主要特征：股票经纪公司等级和股票最近3个月的涨幅情况，进而判断是否购买某只股。假定股票经纪公司等级取值为4种：A等，B等，C等，还要考虑到一种特殊取值 *，即公司等级取ABC中哪个值这个股票我都要买（也就是说这个特征对于我是否买这只股是无关紧要的）；股票最近3个月的涨幅情况取值为3种：涨，降，取值哪个都合适 *，那么根据这两个特征和特征取值，并且股票的标签y取值为买或不买，因此我们可以得到一个由12种类型的假设组成的假设空间，分别为：
1. A等   涨  

2. A等   降

3. A等    *

4. B等   涨  

5. B等   降  

6. B等   *

7. C等    涨

8. C等    降

9. C等   *

10. *   涨

11. *   降

12. *   *

特征向量（feature vector）

假如将色泽，根蒂，敲声三个属性作为三个坐标轴x1, x2, x3，每个西瓜对应一个空间点（一个坐标向量），每个这种示例称为一个特征向量，记为

(x1, x2, x3 )

维数（dimensionality）

每个示例包含的属性个数，如上文中提到的描述西瓜的3个特征色泽，根蒂，响声，这个10万行的数据集的维数是3，这是机器学习中需要理解的重要概念。

标记（label）

关于示例结果的信息，比如判断一个西瓜是好瓜，那么这个西瓜便拥有了标记示例，这个西瓜便成了样例（example）。一般用 Xi , yi 表示第 i 个样例，其中yi 是示例 Xi 的标记。

学习（learning）

从数据中学得模型的过程，又称为训练（training）。正如上文所示，10万条西瓜数据集，根据它的三个特征，和每条特征的标记，经过计算最后得到了一个 f，通过这个 f 我们能预测第1万零一个西瓜是否是好瓜，这个过程被称为学习。

训练数据 （training data）

训练过程中使用的数据，其中每个样本称为一个训练样本（training sample），训练样本组成的集合称为训练集（training set）。通过这些训练数据通过学习，最终得出一个f，也就是我们学到的模型。与之相对应的是测试数据，为了测试通过训练数据得到的f准确度能高不高，我们特意预留出一些数据用来专门测试用，这部分数据就被称为测试数据。

回归（regression）

如果预测的是连续值，例如预测西瓜的成熟度 ，它必然是个大于0的小数值，比如成熟度为0.9，0.75，抑或是根据房屋面积，使用年限两个特征预测某个房屋的价值，类似这种预测称为回归。回归有些不好理解，可以理解为拟合吧，根据已有数据集，得到一条曲线f，然后再来一个Xm，带到 f 中，得到ym 。

分类（classification）

如果我们要预测的是离散值，等于0,1,2,3等这类离散值，例如 好瓜，坏瓜，称此类学习任务为分类。如果分类的结果为两类，又称此分类为二分类，通常称其中一个为正类（positive class），另一个为反类（negative class）。它还有一个很奇怪的名字，叫逻辑回归，虽然是带着回归二字，实际是分类，注意此处。

聚类（clustering）

没有标记的记录集，并且我们还想学习这类数据集，比如想从里头挖出点有用的东西来。然后我们根据某些特征和算法将训练中的西瓜分成若干组，自动形成了几簇，这些簇可能对应一些潜在的概念，比如浅色瓜，深色瓜，本地瓜，这些概念我们都是事先不知道的。聚类的常用的算法自己查阅吧，资料有很多。

更多点击链接
4.「机器学习」：不得不知的概念（2）

泛化能力
泛化能力（generalization），学得的模型适用于新样本的能力，是非常重要的能力。

举个例子来说明什么是泛化能力。

就在我们上学那回，小明爱动脑筋，老师讲的题目不光会做，还能举一反三；小红学习很努力，上课认真听讲，老师布置的作业完成的非常好，但是这仅限于老师讲过的知识范畴内，因为小红不喜欢动脑筋，就是填鸭时地学习知识，老师讲什么，她就学什么，并且这些学得非常好。

在一次数学竞赛中，考的题目都不是以前做过的题目，更别说有原题了，考试的结果，小明100，小红30。

我们说小明的泛化能力很强，因为它能根据老师讲的东西，准确回答出以前老是讲过地类似题目，毕竟万变不离其宗，形式再不一样的题目还是围绕那30个知识点。

但是，小红泛化能力很弱，它虽然平时老师讲的那些题目都会做，但过度地依赖老师讲的每一个细节，仅限于老师讲的那些东西，当来了一个形式上变化但是原理不变的题目时，她变得束手无策，答错了很多题。

引起泛化能力不足的一个原因是过拟合，过拟合导致在测试集上变现非常好，但是在新来的数据集上表现非常差。

泛化能力图解




总结
以上通过1个例子阐述了机器学习中非常重要的1个概念：泛化能力。

在明天的推送中，我们再通过1个例子详细阐述归纳偏好；

后天进入机器学习的回归讲述，欢迎您的订阅学习。


5.直接选择排序到堆排序做的那些改进

01你会学到什么？

彻底弄明白常用的排序算法的基本思想，算法的时间和空间复杂度，以及如何选择这些排序算法，确定要解决的问题的最佳排序算法，上个推送总结了冒泡排序和其改进后的快速排序这两个算法，下面总结直接选择排序到堆排序的改进，后面再继续总结插入排序、希尔排序、归并排序和基数排序。

02讨论的问题是什么？

各种排序算法的基本思想；讨论各种排序算法的时间、空间复杂度；以及算法的稳定性；算法是如何改进的，比如冒泡排序如何改进成了目前最常用的快速排序的，直接选择排序到堆排序的改进，正是接下来要讨论的对象。

03相关的概念和理论

内部排序

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

外部排序

若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

就地排序

若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1），称为就地排序。

稳定排序

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序后，这些记录的相对次序保持不变，即在原序列中 ri=rj， ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序序列分布

排序需要考虑待排序关键字的分布情况，这会影响对排序算法的选择，通常我们在分析下列算法时都考虑关键字分布是随机分布的，不是按照某种规律分布的，比如正态分布等。

待排序序列

排序序列中，剩余即将要排序的序列部分。

已排序序列

排序序列中，已经排序好的序列部分。

更多链接


归并排序算法的过程图解

01你会学到什么？

彻底弄明白常用的排序算法的基本思想，算法的时间和空间复杂度，以及如何选择这些排序算法，确定要解决的问题的最佳排序算法，已经总结了冒泡排序和其改进后的快速排序算法，直接选择排序和堆排序算法，总结了直接插入排序到希尔排序做的改进，下面总结归并排序。


02讨论的问题是什么？

各种排序算法的基本思想；讨论各种排序算法的时间、空间复杂度；以及算法的稳定性；算法是如何改进的，比如冒泡排序如何改进成了目前最常用的快速排序的，直接选择排序到堆排序的改进，直接插入排序到希尔排序做的优化，下面讨论归并排序。

03相关的概念和理论

内部排序
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

外部排序
若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

就地排序
若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1），称为就地排序。

稳定排序
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序后，这些记录的相对次序保持不变，即在原序列中 ri=rj， ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序序列分布
排序需要考虑待排序关键字的分布情况，这会影响对排序算法的选择，通常我们在分析下列算法时都考虑关键字分布是随机分布的，不是按照某种规律分布的，比如正态分布等。

待排序序列
排序序列中，剩余即将要排序的序列部分。

已排序序列
排序序列中，已经排序好的序列部分。

更多链接