argmax：从未来推理现在 整个机器学习(最优化)，背后的根本数学原理是下面这个公式: arg_max_{x∈X} F(x) 它的含义是：在所有可能的输入 x ∈ X 中，找出让目标函数 F(x) 最大的那个 x。这个公式返回的是最优解 x，而不是最大值本身。 这个公式代表【从未来推理出现在的最佳选择】，因为所有的x有哪些，实际上是没办法穷尽的，以及F有哪些，是未来才知道的。代表一种完全信息视角。 这个和“传统”的数学递推公式是反过来的，传统的递推公式是，利用过去的推理未来的，例如斐波那契额数列 ，假设的是F(n-1)和F(n-2)我们已经知道，我们就可以推理F(n)（这也是动态规划算法的核心）。这个是【利用过去的信息推理未来的】。 因此，机器学习/最优化，本质是预测未来。实际上，arg_max 公式，如果用编程语言来表达，非常好理解： 这个思维方式代表的是“从未来反推现在”：F(x) 是未来某种评估函数，我们假设它存在，并试图找到现在该做什么（x）才能让它最大。 def arg_max(X, F): best_x = None best_score = float('-inf') …
2018年7月19日
ACM题解, 学习笔记, 数学, 数据结构与算法, 有意思的, 程序员, 程序设计, 算法, 编程, 计算机, 软件工程, 面试
这题据说是 GOOGLE的面试题, 但是却真实的被一些软件公司拿来考应聘者. 比如我在前几年面试剑桥的博通公司/Broadcom, 在第二轮也被问到了这个问题. 题意是: 给你两个鸡蛋, 有个100层楼, 你可以把鸡蛋从任意一层楼扔下, 鸡蛋可能破, 也可能不破, 如果不破的话, 你可以继续用这个鸡蛋扔. 你需要用这两个鸡蛋来试出鸡蛋会破的最小楼层高度. 这两个鸡蛋一模一样. 问你采用什么策略可以使最坏情况下的尝试次数最少? 什么是最差情况? 如果你只有一个鸡蛋, 那么你最坏需要100次(需要从1层楼开始测试)才可以得到结论. 最直接的做法就是从第一层开始试, 然后第二层以此类推, 但是这种方法只需要用到1个鸡蛋即可. 如果第N层鸡蛋没碎但是第N+1层碎了, 答案就是N. 这种情况下最坏需要尝试100次. 如果我们在第50层扔呢? 如果鸡蛋碎了, 那么答案就在第1到第49层, 反之答案就在第51到第100. …
动态规化 (Dynamic Programming) 是个计算机领域里很重要的算法,我在高中参加过三次信息学奥林匹克竞赛 (ACM),每年必有一题用动归(DP)来解答. 动态规化其实就是 把问题分解成子问题+记忆子问题求解的一个过程. 你如何教你的孩子DP是什么呢? 比如:你给你的孩子5根火柴,你的孩子数了数然后说有5根.然后你再给你的孩子1根火柴然后问一共有多少根,这时候你的孩子会马上说出6根,因为他知道已经有5根了,再加上1根就是6根. 原理就是:把问题分析成更小的问题,并分而求之,子问题的解会被保存下来这样在求解更大的问题的时候就不需要再重新把中间结果再算一遍了. 动态规化的解法经常是较优的一种解法,我们来看这么一道面试题: 给定一个正整数,将它拆分成至少两个正整数,求出这些正整数的最大乘积.比如 整数2,可以拆分成1+1, 乘积是1,当输入是10,需要分解成3+3+4,这样所得的最大乘积是36. 你会怎么解?暴力搜索?这种解法不好写,而且时间复杂度也大.可以用回溯+剪枝,但时间复杂度也相对较大,特别是当N较大的时候也会时间太久Time Exceeded. 动规解答这题就较为简单.这题并没有让你详细写出怎么拆分的方案,只需要解出最大的乘积即可.所以我们有以下的方案: f(n) = max(f(n), max(i – j, f(i – j)) * j)) for …
