|
问题和问题求解 实际问题千变万化，我们考虑一种抽象的统一说法：一个问题就是从一个实例描述集合到解集合的映射， 计算机只会做一件事，就是自动执行程序。用计算机解决一个问题，就要写出一个解决这个问题的有穷程序（无穷长的程序写不完）。如果针对问题T 写了程序P，把T 的任意实例i作为P 的输入，P 的输出总是o=T(i )，我们就可以说P 解决了问题T。 针对问题写出程序是计算机领域最重要的工作。要完成这种工作，首先要确定一种技术路线（一种方法），确定需要从问题中挖掘出什么信息（知识），怎样利用得到的知识构造程序。参考几十年的研究和实践，本文总结出三类方法。是否还有第四类？请读者考虑。 基于算法的系统(Algorithm-Based Systems, ABS) 这个太显然。但是，采用这一方法有什么前提条件？在什么情况下有可能得到解决问题的算法，并实际写出能解决问题的程序？我们可以提出下面一些条件。 首先，该问题必须是“可计算的”，这是理论要求。证明问题是否可计算常常很不容易，但做出算法就是正面的证明。其次，要做出算法，要求我们对问题及其求解完全理解，知道如何处理问题的任意实例，能处理求解过程中可能遇到的任何情况。 算法的优点是直接针对具体问题，是专用的，因此效率高。另一方面，我们比较容易把算法转换为解决问题的程序，也比较容易判断一个程序是否确实解决了问题。 注意：任何有穷问题都有算法。由于情况（输入）有穷，理论上总是可以对其做穷尽分析，分情况给出解。求解程序如下（假定问题只有n 个实例，x 是输入）： 无穷问题也可能写出有穷算法，例如求最大公约数问题。 现在看看用计算机下围棋的问题。围棋要求对弈双方在19×19的棋盘上交替落子，目标是占据最大的地盘。下围棋程序只需要解决一个问题：对任何棋局，确定下一个棋子的最佳位置。由于局面有穷，本问题为有穷问题。按前面的说法，存在确定最佳位置的算法。基于这一算法的围棋程序绝不会犯错，其棋力不会弱于（昨天、今天或未来的）任何棋手，或任何下围棋的程序，包括AlphaGo和AlphaZero。 我们很容易规划出一套写这个算法的系统化方法，只要有充分的耐心和时间，就能做出一个这样的围棋程序。但是，由于可能局面太多（约为3361≈10172），彻底分析每个局面需要的时间太长，这一工作不可能在合理的时间内完成。另一方面，即使能写出来，程序也太长，计算机没有足够的存储器存放它。这一实例说明，理论上有算法，但并不代表能用算法解决问题。 算法的另一个限制是计算机专业人士最熟悉的：必须足够高效（复杂性不高），保证每次执行可以在合理时间内完成。例如，如果一个围棋程序在求解中，需要检查的局面个数可能达到10172，则这个程序（实际上）毫无意义。 下面是能用算法解决问题的一些条件：
如果找不到算法，或者虽然有算法但不适用，我们就只能考虑其他方法。 基于搜索的系统(Searching-Based Systems, SBS) 用计算机解决问题的另一类方法是搜索，也就是通过探查和回溯的方法寻找解。搜索方法并不要求我们对问题及其求解过程有全面的认识，但需要有一些清晰的知识片段，以这些知识片段作为搜索的基础。例如，对基于规则的系统，需要有针对问题的规则库；自动推理需要有事实和推理规则。基于搜索的系统由两部分组成：一部分是针对问题的知识库，包含一集知识片段（规则）；一部分是搜索算法，它设法利用知识库去拼凑出实例的解。 人工智能领域研究过许多搜索方法，开发了一些通用框架（如产生式系统、黑板系统）；提出了许多技术（如各种启发式搜索算法），实现了一些应用（如基于规则的专家系统）；提出了一些编程泛型（如逻辑程序设计、约束程序设计）。还有自动推理、定理证明等方面的大量研究和成果。赫伯特·西蒙（司马贺）等人称搜索为通用问题求解(general problem solving)方法。 只有解决问题的片段知识（规则），通常做不出算法。规则可能不完全，无法处理所有实例或所有情况，也没有处理策略（顺序和过程）。但规则可以用于搜索，通过试探和回溯的方式去求解。搜索的特点是，算法不直接针对问题，而是针对规则的使用。规则可独立描述，也可以嵌入搜索算法中。搜索也已广泛用于实践，例如自动泊车系统常包含搜索。 关于计算机下棋的研究已有几十年历史，基本方法就是博弈树搜索，评价各种可能，选出最佳棋着。围棋的规则很简单，很容易实现一个基于搜索的围棋程序。为此，我们只需实现一个处理博弈的通用搜索引擎，让它用围棋规则去做穷尽搜索，找出最佳棋着。 当然，稍微了解计算机的人都会说上述方案不可行。规模为10172的状态空间太大，朴素搜索方法实际无用。这个不可行的原因是实际计算开销，而不是理论不正确。这也说明了搜索方法的一个重要弱点：求解中需要探查的空间通常以相对于实例规模的指数方式增长。因此，对复杂一些的问题或规模较大的实例，我们可能无法等到结果。 实际围棋程序（包括AlphaGo和AlphaZero）都采用了一些策略，如限制最大搜索深度（或限制搜索时间），加入随机性因素等。设法在不能穷尽搜索的情况下合理地评估局面，只能评估检查到的那些局面，并从中选择可能通向“最佳路径”的棋着等。 搜索方法的优势是有可能利用部分知识解决问题，但也存在许多固有的缺陷：
假设有了一集规则，在采用基于搜索的方法时，需要考虑搜索策略（宽度优先、深度优先、其他），规则选择策略（固定顺序、估值序、随机等），还需考虑状态评估，可能的剪枝策略，局部搜索（限制搜索深度、与评估结合）等问题。 基于实例的系统(Case-Based Systems, CBS) 如果对问题的了解非常少，或基本上没有有关求解的知识，还能用计算机吗？实际情况经常如此：我们认为面临的是一个问题，有需要处理的情况，人能得到有用的结果。例如，医生看了检查报告说“可能××有炎症”，或围棋大师看到一个局面说“感觉不错”。 假设我们“认定”了一组输入和结果 这个程序与前面类似，但本质不同。这里的实例可能只是所有可能实例中的一部分。 人们通常不满意这种“死记硬背”，希望推而广之，这样就需要“归纳”或“学习”。用计算机自动推广就是“机器学习”，也就是第三种方法——基于（实例）学习的求解方法，设法通过自动处理一些“情况-解”实例，得到一个能处理该问题的更多实例的系统。 用机器学习方法解决问题，需要设计一种具有可调整要素的（数据）结构S，一个（能利用实例调整S 的）学习算法L，和一个使用S 解决问题的算法U。对已有的实例集E，学习算法得到L(E, S ) = S'，而U[S'] 就是利用调整后的结构解决问题的程序。学习算法L有效，首先要求将U[S'] 应用于E中的实例输入 例如，多层神经网络是目前常用的一种结构，其中的可调整要素就是神经元之间的连接系数。针对这种结构，人们提出了一些学习算法，该结构的使用算法很简单。 复杂性使我们无法通过穷尽搜索的方法评价围棋棋局。以前人们利用专家知识做评价，主观而且不准确。AlphaGo的创新就在于通过机器学习自动产生评价函数。AlphaZero和AlphaGo的差异在于学习实例的来源，AlphaGo用历史上的围棋实战作为实例，AlphaZero用自对弈棋局作为实例。结合其他机制，Alpha系列程序取得了令人瞩目的战绩。 实际上，机器学习就是用某一类函数去“拟合”一组数据。数学抽象就是：有一组数据和一个函数类，设法找到能最好地表达这组数据的函数表示。图1是一个用线性和二次多项式拟合几个数据点的例子。那么，哪个结果更好地表达了数据中蕴含的关系呢？  图1 线性和二次多项式拟合数据点示例 我们的目标是希望拟合得到的函数能用于处理其他实例。但是，目前对问题的理解只有这一组数据（而且数据可能有误差），因此我们无法回答“哪一个更好”这个问题。 对具体的基函数组，可以设计一种评价标准（某种最小偏差）。而对这组数据的拟合，则无法确认这种标准。真正的标准应该来自问题，基于对被处理问题的全面理解。只有目前这组实例，不可能做出“正确”判断。即使拟合函数对现有数据都完全重合，也未必是最好的预测。例如，对4项数据可以做一个3次多项式，使之经过每个点。图2表示了拟合函数的情况。人们一般都不认为这个拟合更好。  图2 多种拟合示例 对函数拟合的研究提出了两个重要情况。欠拟合：由于函数结构太简单，无法反映问题的重要特征，对应于机器学习中使用的结构过于简单。过拟合：函数类过于丰富，反映具体实例的过多细节，掩盖了目标问题的本质性特征，对应于机器学习中使用的结构过于复杂，导致结果函数震荡剧烈，降低了学习结果的预测能力。从有关函数拟合的讨论中，可以看到学习方法固有的局限性：由于没有对问题的完整理解，我们无法讨论学习结果的正确性，只能问得到的结果“好不好”，而“好不好”也只能通过实例来检验。 常见检验方法有两种：一种是在真实世界里检验，例如自动驾驶，只能在实际道路上试验，希望车辆不出事故、不撞车、不撞物撞人等。另一种方法是把已有实例分为不相交的两部分R = R1 ⊕ R2，其中的R1用于学习，R2用于检验学习效果。 实际上，基于学习的方法还有一些未说明的假设，只有在这些条件下，学习方法才可能有效：首先是假设问题实例和解的关系是连续的；其次是假设每个样本（实例和解）都必定包含了一些反映问题的整体性质的全局信息，因此样本越多越好，信息越多偏差越小。实际上，这些假定都是有疑问的。另外，在不理解问题的情况下，这些条件都无法检查。因此机器学习系统的设计和实现有很大的主观性和试探性，最后只能是“结果决定一切”。 基于（实例）学习系统的另一个缺点是学习代价可能很高。例如，AlphaGo采用超级计算机，学习中对弈超过3000万盘。AlphaGo Zero自对弈3天（约500万盘），水平可超越之前的AlphaGo，自对弈30天可以超越后来的AlphaGo Master版本。由于围棋的特点，实例易得。但很多问题难以得到大量实例，采用这种技术路线的有效性存疑。 根据上面讨论，我们可以总结出适合用机器学习求解的问题的一些特点。首先，问题具有信息完全的场景（静态的、公开的）。一些棋类有这种性质，包括围棋，但许多问题不是这样。其次，存在（或容易得到）大量可用实例。围棋有很多积累，而且容易自动生成。再次，学习效果比较容易判断。例如围棋的胜负和统计可以作为评价。最后，由于学习结果的不可控性，机器学习慎用于安全攸关的应用（否则就需要其他安全措施）。 目前机器学习领域非常热，许多研究者和企业投入其中，也有一些原因：首先是做出了一些有影响的实例，特别是AlphaGo及其后续工作；再就是已经取得了一些成果，使人们看到一些用传统方法不能处理的问题有了新的解决途径。人类不清楚如何解决的问题大量存在，因此存在丰富的有可能用机器学习去探索的问题和应用领域。随着有关研究工作的开展，人们也开发出各种与神经网络类似或有些不同的模型，这些情况都推动着机器学习领域研究和应用的开展。另一方面，计算机能力增强也是机器学习取得进展的重要原因。 但学习方法属于试探性方法，类似于实验科学，与计算机科学技术的常规方法距离比较远。通过学习，从实例得到的结果能外推到什么程度，实际上是不清楚的。因此，机器学习方法更适合于那些只有优良程度要求（而非判定性要求）的应用。例如：要求精确结果的整函数通常无法学习，如斐波那契函数、最大公因子等。我们也应该注意机器学习的性质和本质弱点，避免可能的危害。 三种方法的比较和总结 从前提条件看：采用算法，需要有对问题及其求解的完整知识；采用搜索方法，需要有对问题及其求解的片段知识；采用学习方法，只需要问题和解的实例，无需其他知识。 从技术上看：算法只需要一个直面问题的解决方案；采用搜索，通过一个间接的搜索算法去应用有关问题的片段知识。学习方法需要一个结构和两个算法：一个具有可调要素的结构承载学习结果，一个利用实例调整该结构的算法和一个利用该结构处理实例的算法。 从效果看：正确的算法必定给出正确的解，求解效率可以预估，但也有复杂性太高的可能性。由于知识有限，搜索方法通常不能保证得到解，得到解的代价也很难预估，但有可能保证解的正确性。另一方面，搜索通常不能保证得到一个解。由于知识贫乏，我们只能说学习方法得到的结果可能有用，其他方面都没有保证。 可见，这三类方法各有各的前提条件、优势，以及固有的缺陷。遇到一个问题时，我们应该根据对问题的潜在认识程度、问题的实际需要等选择合适的求解方法。 请注意，为了简单起见，本文对各方面情况做了极度简化。实际应用这些方法时可能有很大变化，也完全可能在一个求解系统里融合了多种方法的要素，特此说明。 作者介绍
|
|
|
来自： Jason_YuHu > 《科学技术与工程》
。如果I是有穷集，T 就是有穷问题，否则 T 是无穷问题。
或
称为问题 T 的实例，o=T(i ) 称为问题T 对应i 的解。
是一个问题的实例，就可能实现一个简单的求解程序（设x 为输入）：
时，得到的结果近似于
。
