等价问题
150
等价问题和人工智能
我在今年的专栏和《硅谷来信》，以及很多公开的场合中讲过，人工智能发展的关键是找到相应的“空气动力学”。也就是说，正如我们无法依靠模拟鸟的飞行让飞机上天，而要通过掌握空气动力学的原理设计出能够有效飞行的飞机一样，人工智能也不是简单模仿人的思维和动作，而要找到适合计算机获取智能的“空气动力学”。
人工智能的支柱其实有三个，就是摩尔定律、大数据和数学模型。
于是从1956年到上个世纪70年代初，全世界科学家一边自己琢磨智能的本质，一边看看那些认知科学的方法是否可以量化地表述，从而使用计算机解决。
最先在人工智能的一个小领域取得突破性成就的是我多次提到的贾里尼克。他天才地找到了语音识别和机器翻译的等价问题——通信问题，从而通过解决通信问题解决了上述两个智能问题。
编码－信道传输－解码，这不就是一个标准的通信过程么？既然语音识别的等价问题是通信问题，那么就可以采用解决通信问题的方法解决语音识别问题。看出了这一点，就是贾里尼克的过人之处了。
当然，由于采用通信的模型需要大量的数据来训练模型，这种方法也被称为数据驱动的方法。
再接下来，贾里尼克的一个叫做彼得∙布朗的部下发现机器翻译的问题也是一个通信问题。
我们可以把贾里尼克和布朗的思想，用这样一个公式概括：
语音识别≡通信问题≡机器翻译。
其中三个横杠，代表数学上的等价。
最后总结一下今天的内容：
1. 我们通过解释一些人工智能系统内部的核心方法，说明寻找等价问题的重要性。2. 很多时候，成功需要各种条件成熟。在没有数据的时候，布朗虽然找到了正确的方法，但是巧妇难为无米之炊。这时，缺乏智慧的人会怨天尤人，具有智慧的人会去开辟一个新的战场。
3. 上帝常常是公平的，人不要总想着名利双收。
思考题：
布朗虽然最早提出机器翻译的正确框架，但是因为客观条件的原因，他没有成为最后一个发明人。在历史上这一类人很多，大部分时候，我们看到的是这些人后来在别人成功之后跑出来强调当年自己的原创贡献。
但是布朗根本不屑于这么做，而是在新的领域找到了属于自己的位置，成为真正的赢家。布朗的做法对你有什么启发？
151
通信中使用最多的算法——维特比算法
语音识别基本上分为三步，第一步是对声波进行信号处理，得到一些语音特征；第二步是通过语音特征，识别出相应的音节；第三步是根据音节，合成出完整的语句。
解码的过程就是找到一条最合理的路径的过程，我们把它称为寻找最佳路径。
对于这样路径密密麻麻的网格，维特比注意到这样一个现象：不论有多少条路径，最佳的那一条路径在某个特定时刻，只有六种可能。
维特比算法从本质上讲，是把一种指数复杂度的问题，变成了线性的复杂度。这可能是所有的计算机算法中复杂度下降最大的改进。
维特比是在上个世纪60年代发明了这个快速算法，并且凭借它，奠定了自己在数字通信中不可替代的地位。但是，维特比并不满足于停留在算法本身，而是努力将它推广出去。
为此，维特比做了两件事：首先，他放弃了这个算法的专利，这使得该算法得以在整个通信领域普及；第二，他和雅各布博士一起在1968年创办了林卡比特（Linkabit） 公司，将这个算法做成芯片，卖给其他通信公司，这样他也就保证了自己的经济收益。到这一步维特比已经比一般的科学家走得远很多了，但是，这仅仅是维特比辉煌人生的第一步。
思考题：维特比算法是一个很了不起的算法。通常人们为了推广自己的成果选择将技术公开，但是维特比又通过直接做芯片的方式挣钱维持了自己的利益，这对你有什么启发？
152
维特比和高通公司
先说说CDMA为什么能提高传输率。根据香农第二定律，一个移动网络只要传输的带宽固定了，整个网络的传输率就被限制死了。
在CDMA以前，移动通信使用过两种技术：频分多址（FDMA）和时分多址（TDMA）。
所谓频分多址，顾名思义，是对频率进行切分，每一路通信使用一个不同的频率，对讲机采用的就是这个原理。由于相邻频率会互相干扰，因此每个信道要有足够的带宽。这些信道之间的带宽无法利用，就被浪费掉了，你可以把它们想象成经济学上所说的边际成本。
时分多址是将一个很宽的频带按时间分成很多份。
形象地讲，FDMA是按照频率垂直划分，TDMA是按照时间水平划分。不论哪种划分的方法，中间白色的都是无法利用的空隙，它们影响了移动互联网的效率。
CDMA的做法和上述两种方法都不同，它既不是使用固定的频率传输，也不是分时共享，而是让每一个网络用户都可以占用很多频带，而且也不对时间进行划分。
移动互联网上多个用户同时发射信息，岂不打架了？没关系，在CDMA协议中，每个发送者被赋予了不同的密码，接收者在接到不同信号时，通过密码过滤掉自己无法解码的信号，留下那些和自己密码对应的信号即可。由于这种方法是根据不同的密码区分信息的，因此称为码分多址。
从1985年到1995 年，高通公司制定和完善了CDMA的通信标准CDMA1，并于2000 年发布了世界上第一个3G移动通信标准CDMA2000，后来又和欧洲、日本的通信公司一同制定了世界上第二个3G标准WCDMA。2007年，维特比作为数学家和计算机科学家，被授予美国科技界最高成就奖——国家科学奖。
如果把维特比算作数学家中的一员，那么他也许是全世界有史以来第二富有的数学家（最富有的无疑是文艺复兴技术公司的创始人吉姆·赛蒙斯）。维特比是南加州大学最大的资助者之一，该校的工学院也是以他的名字命名的。
153
Google面试题——如何实现拼写纠错功能和拼写提示功能
在介绍如何纠错之前，先讲一个简单的问题，如何查错。注意这是两个相关的，但并不相同的问题。
第一种设计方法是采用排好序的线性数组，这样采用二分查找，就可以判断一个字符串的拼写是否是正确的（在构词学上称为"合法"）。
当然，如果你还记得我们前面讲到的哈希表和哈希查找，我们利用哈希表来存储词典，大约只要进行两次单词查找，就可以判断一个单词的拼写是否合法。
第二种设计方法是使用一种类似于我们前面讲过的二叉树的树状结构。
采用树状的数据结构有两个好处。首先就是速度快，一个要检查的单词有多少字母，只要查找那么多次即可，比如平均只需要六次。
接下来再谈谈如何纠错，这并非是个很容易的问题，我们需要从理论和工程两个角度来回答。先从理论上回答。
最后，总结一下今天的内容：
1. 很多人问我什么是一通百通，对于一种知识和技能的熟练运用，就是一通百通。
2. 科学和工程还是有区别的，从今天的例子中你应该有更深的体会。在科学上，采用一个好的和不好的方法，差距会非常大。在工程上，很多实际问题不考虑清楚，做出来的东西就不好用。
3. 很多时候，改进是无止尽的，有的人做事情只做了50%-60%，就觉得全做好了，就满足了，其实如果要往深里做，就会发现还有很多问题有待解决。
来信补充 | 给李开复新书《AI 未来》序言
AI也变得更亲民：行业专业知识不再被少数精英团体垄断。只要具有相应背景，谁都可以掌握深度学习的基础知识。比起强大的队伍，数据才是王道。谁拥有最多的数据，谁就能发起最具颠覆性的技术革新。
答读者问38 | 如何平衡产品的体验与快速迭代的需求
在历史上，法国的专利以“水”著称，今天中国的专利大致如此，中国真正有价值的，是在美国被批准的专利。
评论