数学之美系列 二十四 从全球导航到输入法——谈谈动态规划

发表者:Google(谷歌)研究员 吴军

今年九月二十三日,Google、T-Mobile 和 HTC 宣布了第一款基于开源操作系统 Android 的 3G 手机,其中一个重要的功能是利用全球卫星定位系统实现全球导航。这个功能在其它手机中早已使用,并且早在五六年前就已经有实现这一功能的车载设备出售。其中的关键技术只有两个:第一是利用卫星定位;第二根据用户输入的起终点,在地图上规划最短路线或者最快路线。后者的关键算法是计算机科学图论中的动态规划(Dynamic Programming)的算法。    

在图论(请见拙著《图论和网络爬虫》)中,一个抽象的图包括一些节点和连接他们的弧。比如说中国公路网就是一个很好的“图”的例子:每个城市一是个节点,每一条公路是一个弧。图的弧可以有权重,权重对应于地图上的距离或者是行车时间、过路费金额等等。图论中很常见的一个问题是要找一个图中给定两个点之间的最短路径(shortest path)。比如,我们想找到从北京到广州的最短行车路线或者最快行车路线。当然,最直接的笨办法是把所有可能的路线看一遍,然后找到最优的。这种办法只有在节点数是个位数的图中还行得通,当图的节点数(城市数目)有几十个的时候,计算的复杂度就已经让人甚至计算机难以接受了,因为所有可能路径的个数随着节点数的增长而成呈指数增长(或者说几何级数),也就是说每增加一个城市,复杂度要大一倍。显然我们的导航系统中不会用这种笨办法。

所有的导航系统采用的都是动态规划的办法(Dynamic Programming),这里面的规划(programming)一词在数学上的含义是“优化”的意思,不是计算机里面编程的意思。它的原理其实很简单。以上面的问题为例,当我们要找从北京到广州的最短路线时,我们先不妨倒过来想这个问题:假如我们找到了所要的最短路线(称为路线一),如果它经过郑州,那么从北京到郑州的这条子路线(比如是北京-> 保定->石家庄->郑州,称为子路线一),必然也是所有从北京到郑州的路线中最短的。否则的话,我们可以假定还存在从北京到郑州更短的路线(比如北京->济南->徐州->郑州,称为子路线二),那么只要用这第二条子路线代替第一条,我们就可以找到一条从北京到广州的全程更短的路线(称为路线二),这就和我们讲的路线一是北京到广州最短的路线相矛盾。其矛盾的根源在于,我们假设的子路线二或者不存在,或者比子路线一还来得长。

在实际实现算法时,我们又正过来解决这个问题,也就是说,要想找到从北京到广州的最短路线,先要找到从北京到郑州的最短路线。当然,聪明的读者可能已经发现其中的一个“漏洞”,就是我们在还没有找到全程最短路线前,不能肯定它一定经过郑州。不过没有关系,只要我们在图上横切一刀,这一刀要保证将任何从北京到广州的路一截二,如下图。    

那么从广州到北京的最短路径必须经过这一条线上的某个城市(图中蓝色的菱形)。我们可以先找到从北京出发到这条线上所有城市的最短路径,最后得到的全程最短路线一定包括这些局部最短路线中的一条,这样,我们就可以将一个“寻找全程最短路线”的问题,分解成一个个小的寻找局部最短路线的问题。只要我们将这条横切线从北京向广州推移,直到广州为止,我们的全程最短路线就找到了。这便是动态规划的原理。采用动态规划可以大大降低最短路径的计算复杂度。在我们上面的例子中,每加入一条横截线,线上平均有十个城市,从广州到北京最多经过十五个城市,那么采用动态规划的计算量是 10×10×15,而采用穷举路径的笨办法是 10 的 15 次方,前后差了万亿倍。

那么动态规划和我们的拼音输入法又有什么关系呢?其实我们可以将汉语输入看成一个通信问题,而输入法则是一个将拼音串到汉字串的转换器。每一个拼音可以对应多个汉字,一个拼音串就可以对应图论中的一张图,如下:    

其中,Y1,Y2,Y3,……,YN 是使用者输入的拼音串,W11,W12,W13 是第一个音 Y1 的候选汉字,W21,W22,W23,W24 是对应于 Y2 的候选汉字,以此类推。从第一个字到最后一个字可以组成很多很多句子,我们的拼音输入法就是要根据上下文找到一个最优的句子。如果我们再将上下文的相关性量化,作为从前一个汉字到后一个汉字的距离,那么,寻找给定拼音条件下最合理句子的问题就变成了一个典型的“最短路径”问题,我们的算法就是动态规划。

上面这两个例子导航系统和拼音输入法看似没什么关系,但是其背后的数学模型却是完全一样的。数学的妙处在于它的每一个工具都具有相当的普遍性,在不同的应用中都可以发挥很大的作用。

我们在下一个系列将详细介绍专门针对拼音输入法的“维特比算法”。

[…]

浪潮之巅 第十一章 幕后的英雄—风险投资(Venture Capital)

发表者:Google(谷歌)研究员 吴军

第一节 风投的起源

第二节 风投的结构

第三节 风投的过程

第四节 投资的决策和公司的估价

第五节 风投的角色

第六节 著名的风投公司

就像华尔街已经等同于美国金融业一样,在创业者眼里“沙丘路”(Sand Hill Road)便是风险投资公司的代名词。沙丘路位于硅谷北部的门罗公园市(Menlo Park),斯坦福大学向北一个高速路的出口处。它只有两三公里长,却有十几家大型风险投资公司。在纳斯达克上市的科技公司至少有一半是由这条街上的风险投资公司投资的。其中最著名的包括红杉资本(Sequoia Capital,在中国称作红杉风投)、KPCB(Kleiner,Perkins,Caufield & Byers)、NEA(New Enterprise Associates)、Mayfield 等等。NEA 虽然诞生于美国“古城”巴尔的摩,但经营活动主要在硅谷,它投资了五百家左右的公司,其中三分之一上市,三分之一被收购,投资准确性远远高于同行。它同时是中国的北极光创投的后备公司(backing company)。Mayfield 是最早的风险投资公司之一,它的传奇之处在于成功投资了世界上最大的两家生物公司基因科技(Genentech)公司和 Amgen 公司(这两家公司占全世界生物公司总市值的一半左右)。除此之外,它还成功投资了康柏、3COM、SGI 和 SanDisk 等科技公司。而所有风投公司中,最值得大书特书的便是红杉风投和 KPCB 了。

6.1 红杉风投

    

Sequoia 是加州的一种红杉树,它是地球上最大的(可能也是最长寿的)生物。这种红杉树可以高达一百米,直径八米,寿命长达两千两百年。1972 年,投资家唐纳德.凡伦汀(Don Valentine)在硅谷创立了一家风险投资公司,以加州特有的红杉树命名,即 Sequoia Capital。该公司进入中国后,取名红杉风投。

红杉风投是迄今为止最大、最成功的风险投资公司。它投资成功的公司占整个纳斯达克上市公司市值的十分之一以上,包括苹果公司、Google 公司、思科公司、甲骨文公司、Yahoo 公司、网景公司和 YouTube 等 IT 巨头和知名公司。它在美国、中国、印度和以色列有大约五十名合伙人,包括公司的创始人凡伦汀和因为成功投资 Google 而被称为风投之王的麦克.莫利兹(Michael Moritz)。

红杉风投的投资对象覆盖各个发展阶段的未上市公司,从最早期到马上就要上市的公司。红杉风投内部将这些公司分成三类:

[…]

浪潮之巅 第十一章 幕后的英雄—风险投资(Venture Capital)

发表者:Google(谷歌)研究员 吴军

第一节 风投的起源

第二节 风投的结构

第三节 风投的过程

第四节 投资的决策和公司的估价

第五节 风投的角色

对风险投资家来讲,最理想的情况是能当一个甩手掌柜:把钱投到一家公司,不闻不问,几年后几十倍的利润拿回来。这种情况对于天使投资确实发生过,比如有一个从洛杉矶募集资金的天使投资团将钱投入了早期的 Google,等 Google 上市时,该投资团的合伙人,包括 NBA 明星奥尼尔、加州州长施瓦辛格和一些好莱坞明星,稀里糊涂地就挣到了一大笔钱。对于比较大的风险投资,反而很少发生。大多数办公司的人的经验总有局限性,尤其是 IT 行业的创始人大多是技术出身,没有商业经验和“门路”(在美国,门路和在中国一样重要)。风投公司就必须帮助那些创始人把自己投资的公司办好。毕竟,他们已经在一条船上了。

风投公司介入一个新兴公司后的第一个角色就是做顾问。这个顾问不仅需要在大方向比如商业上给予建议,而且还要在很多小的方面帮助创始人少走弯路。我在前一章“硅谷的另一面”中提到,创办一个小公司会遇到形形色色的问题,而创始人常常缺乏处理这些问题的经验,这时风投公司(坐在被投公司董事会席上的那个人)就必须帮忙了。我的一位朋友原来是苹果公司副总裁、乔布斯的朋友,现在是活跃的投资人,他给我讲了下面一个例子。

留心各大公司图标(Logo)的读者也许会注意到,几乎所有大公司的图标和名称字体都是一种简单的颜色设计,尤其是在二十年前。至今很少有公司像 Google 那样使用明暗分明的彩色图标。我的这位朋友告诉我,这主要有两个原因:首先,彩色印刷比单色(和套色,比如普通黑字套蓝色)印刷要贵得多,公司初办,必须本着能省一点是一点的原则,如果一个公司所有的文件和名片都采用彩色印刷,办公成本将增加;第二,也是更重要的,所有的传真机和绝大部分复印件都是黑白的,印有彩色图标的公司传真不仅不可能像原来彩色的那样好看,而且有些颜色可能还印不清楚。这样不仅让商业伙伴感到糊涂,还不容易给客户留下深刻印象。他告诉我,很多年轻的创始人喜欢为自己公司设计漂亮的彩色图标,实际宣传效果并不好。比如下面一个漂亮的彩色图标:    

当我在不同复印件上拷贝时,得到两个颇为不同的黑白复印件。不仅原来精心设计的丰富色彩在传真文件中看不到,而且每次黑白复印件深浅不同,反而会让商业伙伴和客户糊涂。    

    

下面是 IBM 和 AT&T 公司早期的图标,它们避免了复印和传真可能带来的迷惑。    

    当然,上面只是一个小的例子。风投介入一个新兴公司后,可以帮助创业者少走很多弯路,总的来讲好的风投是创业者的伙伴。

当然,风投不可能替公司管理日常事务。这就有必要替公司找一个职业经理人来做 CEO(当然,如果风投公司觉得某个创始人有希望成为 CEO,一般会同意创始人兼 CEO 的职位)。每个风投基金投资的公司都有十几到几十家,要找到几十个 CEO 也并非容易的事。因此,有影响的老牌风投公司实际上手里总攥着一把 CEO 候选人。这些人要么是有经验的职业经理人,要么是该风投公司以前投资过的公司的创始人和执行官。风险投资家给有能力的创始人投资的一个重要原因就是锁定和他的长期关系。如果后者创业成功固然好,万一失败了,风投资本家在合适的时候会把他派到自己投资的公司来替自己掌管该公司日常事务。一个风投公司要想成功,光有钱,有眼光还很不够,还要储备许多能代表自己出去管理公司的人才。这也是著名风险投资公司比小投资公司容易成功的原因之一,前者手中攥着更多更好的管理人才。

风投公司首先会帮助被投资的公司开展业务。自己开公司的人都知道,一个默默无闻的小公司向大客户推销产品时,可能摸不对门路。这时,“联系”广泛的风投公司会帮自己投资的小公司牵线搭桥。越是大的风险投资公司越容易做到这一点。风投公司还会为小公司请来非常成功的销售人才,这些人靠无名小公司创始人的面子是请不来的。风投广泛的关系网对小公司更大的帮助是,它们还会帮助小公司找到买主(下家)。这对于那些不可能上市的公司尤其重要。比如,KPCB 早期成功地投资太阳公司后,就一直在太阳公司的董事会里,利用这个方便之处,KPCB 把它自己后来投的很多小公司卖给了太阳,这些小公司对太阳是否有用就不得而知了,但是,投资者的钱是收回来了,创业者的努力也得到了客观的回报。在这一类未上市公司收购案中,最著名的当属 Google 收购 YouTube 一事。两家公司都是由红杉风投投资,著名投资人莫利兹同时担任两家公司董事。YouTube 能成功地卖给 Google,红杉风投作用不小。风投行业经过几十年的发展,就形成了一种马太效应。越是成功的风投公司,投资成功上市的越多,它们以后投资的公司相对越容易上市、再不济也容易被收购。因此,大多数想去小公司发财的人,选择公司很重要的一个原则就是看它幕后的风投公司的知名度。Google 在很早的时候就已经是求职者眼中的热门公司了,固然有它许多成功之处和吸引人的办法,以及创始人的魅力,但是还有非常重要的一条就是它是第一家KPCB和红杉风投在同一轮一起投资的公司,在此以前,这两家风投从不同时投一家公司。

风投是新兴公司的朋友和帮手,因为它们和创始人的基本利益是一致的。但是通常也有利益冲突的时候。任何一个公司的创办都不是一帆风顺的,当一个被投公司可能前景不妙时,如果投资者对它是控股的,可能会选择马上关闭该公司或者贱卖掉,以免血本无归。这样,创始人就白忙了一场,因此创始人一定会倾向于继续挺下去,这时就看谁控制的股权,更准确的讲是投票权(Voting Power)多了。当一家公司开始盈利有了起色时,风投会倾向于马上上市收回投资,而一些创始人则希望将 公司做得更大后再上市。投资人和创始人闹得不欢而散的例 […]

Category

Archives