算法及机器学习日记

机器学习笔记 - 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 !

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180410G0Q94F00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

同媒体快讯

扫码关注腾讯云开发者

领取腾讯云代金券