算法及机器学习日记

机器学习笔记 - Regularization by Bayesian Inference

今天一直在思考一个关于Loss Function Regularization的问题，L1和L2约束项，到底是怎么来的？如何以Bayesian inference的角度去阐释它？查阅了一些资料，主要是Bishop的Pattern Recognitioin那本书之后，有了一点心得。

从Bayes的观点看，Regularization其实就是对于模型参数引入了先验分布。我推导了一下公式，很容易可以看出端倪：

（本来应该用LaTex写的，不过今天实在没时间了。捂脸！）

从上面的推导可以看出，最大似然函数的最大值，在y - x * w的最小值处取得。所以w的Maximum a Posterior Probability就是最小二乘法的公式。这里没有考虑误差epsilon，很容易过拟合。

在L2 Regularization中，我们假定误差epsilon和w都服从高斯分布，通过同样的最大似然估计，我们就推导出L2 regularization的范式，也就是Ridge Regressioin，岭回归。到这才恍然大悟，原来regularization不是拍脑袋想出来的，而是有严谨优雅的数学证明的。

正则化参数等价于对参数引入先验分布，使得模型复杂度变小（缩小解空间），对于噪声以及outliers的鲁棒性增强（泛化能力）。整个最优化问题从贝叶斯观点来看是一种贝叶斯最大后验估计，其中正则化项对应后验估计中的先验信息，损失函数对应后验估计中的似然函数，两者的和即对应贝叶斯最大后验估计的形式。这样就好理解了，在优化过程中，加入先验分布，效果自然好！

356. Line Reflection

思路：几何题。首先复习一下初中平面几何，两个点关于平行于Y轴的直线（x = n）对称，则有n - x1 = x2 - n,即2 * n = x1 + x2.也就是说两个对称点的横坐标和，永远等于2 * n.利用这个性质，我们求出所有点的上下限，这两个点一定对称，进而获得sum = 2 * n.然后再用sum去HashSet中，验证每一个点的对称点是否存在。TC是O(n).

这道题的另一个关键，就是Wrapper class中override的两个函数，equals和hashcode,它们是能用HashSet对Point class进行O(1)查找的关键，它们俩缺一不可。另一个tricky的办法，是把point用String代替，相当于利用了String类的equals和hashcode函数。

416. Partition Equal Subset Sum

思路：DP类型题。这道题是Knapsack的变形，首先求出target目标值，它等于数组元素和的一半，然后建立boolean类型DP数组，dp[i][j]表示前i个数能否组成j，状态转移方程是dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j].前半部分表示选择当前数字i，后半部分表示不选择当前数字i。因为DP数组的第一维比nums数组大1，所以方程中用nums[i - 1].最后返回的结果，是dp[nums.length][sum / 2],表示数组能不能组成目标值target。TC是O(nums.length * sum / 2), SC也是O(nums.length * sum / 2)

进一步观察，我们可以用滚动数组技巧来压缩空间。注意，因为dp的当前状态，之后上一行，以及更小的target有关，所以一维dp数组更新的顺序是从右到左，否则就会把比自己小的target覆盖掉。

这道DP真是轻松愉快呀！

548. Split Array with Equal Sum

思路：数组类型题。这道题我们先从一个分割点，分成两个数组开始考虑。首先，找一个数组的分割点，使左右subset相等，最好的方法是用prefix sum，可以通过一次遍历O(n)时间完成。所以，这道题首先把原数组变成Prefix sum数组。然后，如果原数组是单调递增的，那么左右两个subset的和只可能有一个，分割点也只能有一个，但是数组中可能有负数，所以prefix sum并不是单调递增的，subset的和也可能有多种。比如[3, 2, -2, 5],以2分割，两边都是3，以-2分割，两边都是5。这就需要用一个HashSet来存储subset的和，便于O(1)时间查找，以验证左右两边的subset和相等。

这道题的最关键的地方，是处理下标。用left，mid，right三个指针来指向三个分割点，题中要求严格大于，排除了等于的情况。构造Prefix sum，比原数组长度大1，所以mid要从4开始，left从2开始，right从mid+2开始。左边找到相等分割点，加入Set，等待右边验证有相等的subset。遇到下标复杂的题，用一个example对照写。

Math is beautiful !