博文

与师生谈研究策略3：人人信之而善忘的黄金法则精选

已有 17666 次阅读 2012-10-29 11:58 |系统分类:教学心得

学：学生，教：教师，李：李晓榕。

李：关于第二要素——描述，我想强调一个

黄金法则：回避比原问题更难的子问题。

一个问题的解决不应依赖于一个更难的待解问题。所以，在描述问题时，不应在中间引入更难的待解子问题。我想这点大家都能理解和认同。

教：这一法则是您发现或总结的吗？

李：我清楚地认识到这一法则，深受VladimirVapnik的启发。他是统计学习理论的大家、支撑向量机的开创者。他在《StatisticalLearning Theory》中说，在信息有限时，要直接求解，决不在中间步骤求解更一般的问题，信息可能足以直接求解，但不够求解更一般的中间问题。（If you possess a restricted amount of information for solving someproblem, try to solve the problem directly and never solve a more generalproblem as an intermediate step. It is possible that the available informationis sufficient for a direct solution but is insufficient for solving a moregeneral intermediate problem.）我看后深受启发，但是“一般”不很准确，“难”应该更本质。前面谈选题时说过，更一般的问题未必更难。何况，不少时候把解决一个更一般的问题作为中间步骤，是合理而行之有效的，这也正如莱布尼兹所建议的。当特殊的问题涉及不少无关宏旨的枝节，而问题的本质被掩盖时，更是如此。比如，我们经常把一个特殊的算术问题转化为一个更为一般的代数问题加以求解。除此之外，我不知道还有谁这么明确地提出这一法则。值得注意的是，

各行各业违背这一法则的例子屡见不鲜。

一个简单例子是：为了估计和式，先估计各项再做和，因为每项都有现成的方法去估计。然而，虽然和是可估计的，信息却未必足以估计每一项，至少效果不佳。目的是要估计和，所以应避免估计每一项。将粒子滤波（particlefiltering）用于目标跟踪，现在很热，文章铺天盖地。我认为这很值得商榷。粒子滤波本身是个好东西，它在本质上擅长于对付动态密度估计，而目标跟踪一般只需要估计目标的状态向量，而不是其密度，因为那是奢求。大多数情况下数据量不足以估计密度，所以要现实一点，只估计向量。密度估计比向量估计难得多，所以粒子滤波对大多数目标跟踪问题未必好，它违背上述法则，杀鸡用牛刀。这把牛刀还被用来杀各种其他动物，包括飞鸟。

教：现实中哪些问题需要对整个密度进行估计？

李：那是有的，没有状态演化的动态方程的问题往往如此。但对大多数目标跟踪问题是不需要的，不切实际。

学：一旦知道状态的概率密度，不就完全掌握了状态向量的所有信息？那状态估计的所有问题不都解决了吗？这样不是解决得更彻底吗？

李：让我用归谬法来反驳。照你说的道理，更进一步，我们最好先建立一个万能理论，从而所有问题都迎刃而解。这个观点的错误在于，它没考虑这样一个理论能否建立以及是否容易建立。

学：粒子滤波对数学的要求不高，缺点是计算量太大，好处是操作简单。所以在目标跟踪中有很多应用。

李：关键是感兴趣的不是那个更难更一般的问题，想要解决的是这个简单容易的问题。而且，数据不足以足够精确地确定密度。这好比弱不禁风、手无缚鸡之力的人却偏要用牛刀杀鸡。在这儿，动态密度估计是“牛”，状态向量估计是“鸡”，数据不足是弱不禁风，粒子滤波是牛刀。

学：但它是一个一般的办法，并且也不难用。

李：这相当于说：“它是一把牛刀，而且用起来不难。”这并不说明这把对付动态密度估计这头“牛”的刀，很适合于屠宰状态向量估计这只“鸡”。它的长处是估计动态密度，没用它的长处，就是没用牛刀杀牛。由于它针对的对象不同，它不能充分地利用所有信息来解决我们的问题。

教：粒子滤波是一种数值方法，而向量估计问题也可以用数值方法解决。比如说，点估计中的条件均值其实就是一个积分，它可以用粒子滤波这种数值方法来计算，只是运算量大而已。

李：一个密度需要无穷多个标量方程才能唯一确定，所以密度估计在理论上相当于估计一个无穷维向量。粒子滤波用有限个点的值来近似密度，相当于估计一个极其高维的向量，如果用一万个粒子，维数就是一万。为简单起见，可以用一维状态的例子来说明。这时条件均值是个一维积分，也就是一个标量和。估计一个和，不必估计它的每一项，而用粒子滤波估计状态，就相当于先估计每一项，再用它的和来估计这个和，不仅运算量大，性能也未必好。给定十个数据点，可以估计这个标量和，但能不能很好地估计那个一万维向量？

教：为什么数据少就不能估计密度？我们在做粒子滤波时都知道，不管数据多少，都能实现。所以我觉得即使数据少，粒子滤波照样可行。

李：那是因为粒子滤波是贝叶斯滤波，它假设我们有完全的先验知识，也就是预报密度，数据的作用只是改动预报密度，使之成为后验密度。当数据少时，后验密度主要依赖于预报密度。事实上，我们并没有完全的先验知识，预报密度往往不好，所以数据量不够时，后验密度也不好。给定十个数据点，如果那一万维向量的先验估计不好，后验估计也就不好，它们之和的估计一般也就不好。在相同情况下，对和的先验直接估计完全可能已经不错，给定十个数据点，其后验直接估计更是不错。

学：但是粒子滤波器操作起来简单啊。

李：操作简单与否是另一回事。关键在于密度估计明显比向量估计难。即便粒子滤波比现有状态向量估计方法好而简单，也只能说明向量估计还没做好，还应努力直接做，不经过密度估计。也就是研制有效的鸡刀，而不是始终依赖牛刀或改进牛刀以适应之，尽管可以暂且这么用，特别是想偷懒时。就像杀鸡没有鸡刀，权且用牛刀一样。让我东施效颦，学庄子讲一个自编的寓言“滥用关刀”。关公的青龙偃月刀，堪称兵器之王。关公死后，机缘巧合，有个莽汉得到此刀。他想，既然此刀有如此威名，它应足以对付任何需要用刀的情形。于是，他就用来劈柴、切肉、杀鸡、割纸甚至“抽刀断水”。有人笑话他，并建议他用来剪指甲，他说：“你有所不知，如果这些柴、肉、鸡、纸都是铜做的大家伙，不就显出我的智慧和本事了么？”是啊，粒子滤波对付动态密度估计不错，知道密度后，所有统计问题都迎刃而解。所以，粒子滤波不就是这么一把青龙偃月刀吗？它被到处乱用，这不又是前面所说的“突破-泛滥”常见模式的再现吗？将这82斤的青龙偃月刀用于打斗，那些能够挥舞自如的好汉，当然不在被取笑之列。

教：真是啊。为什么那么多人都没想到这么简单的道理呢？您是怎么想到的呢？

李：不是没想到，是根本没去想。我是2003年夏天从澳洲回美国时在飞机上想到的，当时我考虑目标跟踪中的粒子滤波，想到了上述黄金法则，马上意识到这么做很不妥。从此我就敬而远之了。几年前有人找我，给钱让我做这方面的研究，我也没接受。很遗憾，我有此认识时只跟我的团队的师生说了这事儿。如果我当时大声疾呼，也许误入歧途之人会少些。不过，这几年我在讲学时，常常指明这一点。无独有偶，数据关联被普遍认为是杂波下目标跟踪的必由之路。事实上，数据关联往往比杂波下目标跟踪本身（不做数据关联）更难。确实，数据关联是目标跟踪的老大难问题，一旦解决，剩下的就是状态估计问题。然而，我逐渐认识到数据关联问题比目标跟踪问题本身还难。目标跟踪就是目标状态的动态估计，它是一个连续型的优化问题。数据关联是指找出数据与来源之间的对应关系，是离散问题。离散优化比连续优化一般来说都难不少。而且数据本身告诉你什么？它绝不直接披露自身的来源，但可能直接告诉你目标状态的信息。所以要想解决数据关联问题很难，比杂波下目标跟踪本身更难。目标跟踪的目的和应用，一般不需要知道这种关联，主要是想知道目标的状态，对数据从哪来并无直接兴趣，因而描述时不该把关联问题作为待解问题放进去。所以，我说目标跟踪从60年代以来一直在犯这个严重错误。很可惜，好多人误入歧途，浪费精力。

教：这个说法不是危言耸听，就是石破天惊。除了先关联数据之外还能怎么做？

李：比如可以考虑目标的集合以及量测的集合，考虑这两个集合之间而不是元素之间的对应关系，在集合的层面上求解，这就撇开了关联问题。再如，可以把目标跟踪问题描述成不完全信息下的问题，数据关联就是丢失的信息，用EM算法求解。我最近在《10000个科学难题·信息科学》中撰文阐明此事。我从2005年前后开始就在公开场合指明这一点，你从未听说？

教：为什么违背上述法则的错误会那么常见呢？

李：在中间过程中引入更难的子问题往往很“自然”，

错误往往根植于“套用已有解法”。

这是一种自然倾向和习惯。人们知道某些问题有解，往往就希望把当前的问题转化成那个问题，好比棋手想把棋局导向有利的已知残局。一不小心，忽视这个法则，引入的问题就可能比原问题更难。比如想解决一个问题，按照某个描述，知道怎么解其中的三步，只有一步不知道。好多人就想当然地去攻克这一步，而不想想这一步可能比原问题还难。一旦解决数据关联问题，就知道怎么做目标跟踪，套用现有的滤波方法即可。更难的中间问题也许可解，但往往解得不好。依赖于解决一个更难的子问题效果应该更差，因为可以根本不解决这个子问题。一般而言，求解这个中间的待解难题，无论如何是额外的束缚。没有这个束缚的解至少可能更好，也往往更好。

教：但是问题的难易很难判断啊。怎么知道中间的子问题是不是更难呢？

李：我这是在倡导一个法则。判断问题的难易程度确实不一定轻而易举，得慎重。面对一个具体问题，具体对待，很可能是有数的。比如,对于粒子滤波用于目标跟踪，或者数据关联问题之于目标跟踪，我觉得问题的相对难易程度不难判定。不可否认，任一法则都有应用困难，也都有例外，但没有充分理由认定是例外时，不该认为是例外。要有意识地去想引进的问题是不是更难。要是判断错误，那是水平、判断力的问题，没办法。但是如果认定这个子问题更难，那就不该这么描述。遗憾的是，绝大多数人根本不加判断就匆匆求解了。有时我的学生提出某个东西，我点破说又违反这个原理了，他马上认同。如果不清楚这个原理，就会迷茫而争论不休，如果清楚，一说就明白。对于这个原理，人们都有所领悟。一旦明确提出，没多少人会怀疑，但实践起来并不容易。不信，你可以观察，保证有不少人、在不少地方违背这个原理。这也是不应跟风的原因之一：有时热门、流行的做法是错的，根本不该跟，用粒子滤波做目标跟踪就是一例。意识到数据关联大都比目标跟踪更难以后，我就没做过数据关联问题。

教：实际问题往往很难，我们做研究时往往把它简化。

李：这要从两方面考虑。如果把一个实际问题完备地描述成一个理论问题，在各方面都解决它，这个理论问题往往太复杂、不可解。不少研究者强调他们的问题很难，是NP-难或NP-完备的。其实，这不稀奇。大多数实际问题的完备描述都应该是NP-难或NP-完备的。面对一个实际问题，只有简化，抓住主要方面。另外，实际问题也有实际对策：撇开其他方面，仅仅解决某个方面。

正在出的博文系列：

与师生谈现代化之弊

1：崛起的代价

与师生漫谈科研

1：我有科研之才吗？ 2：我该做科研吗？

3：逻辑推理的作用 4：人生价值

5：生命的延续

已出博文系列：

与师生谈科学之弊

1：线式因果思维1 2：线式因果思维2

3：线式因果思维3 4：螺环之奇妙

5：幻化的因果 6：不牢靠的因果推理