我： 你好啊，我的博客，以后会在这里记录很多东西，谢谢你给我誊写的地方哦。
博客： 这么卖萌，一看就是个闷骚的男人。
我： 。。。
博客： 好了啦，写就写啦，但是记得坚持哦。
我： 恩恩额。
博客： 正经点说，你为什么要写博客呀。
我： 嗯，这是个好问题，那我就认真回答一下吧。
这是个碎片化，同时也是知识爆炸的社会，我们日常生活、工作中学习到的技能，总结的经验总是零零散散而缺乏有效的组织，因此在有意识地去组织这些零散而有用的知识技能是重要而有意义的。而写作是一个很好的对知识点总结和思考的过程，在这个过程中，你可以加深理解，独立思考原来没有发现到的角角落落。这使得你对知识点的理解更加全面，对技能的掌握更加熟练，对你的职业生涯和生活都有莫大的帮助。基于如此的思考，我也开始了博客生涯，千里之行始于足下么！
机器学习依赖许多数学基础，其中一个入门级的优化就是最小二乘法。
最小二乘法分为两类：线性最小二乘法和非线性最小二乘法。其主要区别是拟合函数是否线性，我们主要介绍线性最小二乘法。
线性最小二乘法：
给定函数\(f(x)=w^T*x + b\)，
给出m组数据\(x^i\),\(y^i\):i=1…m,其中\({x,y,x^i,y^i,w}\in {\mathbb R}^n\)。
求w,b，使得：
$$cost(w,b) = \min \sum_{i=1}^m (f(x^i)-y^i)^2$$
对于线性最小二乘法，利用一阶偏导数cost’(w,b) = 0可以求得解析解，这里我们就不深入讨论了。因为解析解涉及到求解逆矩阵，当矩阵很大时，逆矩阵的计算量非常大，所以我们想是不是可以求解数值解，这样虽然可能有一点点误差，但是计算量也会少很多；而且，对于非线性最小二乘法而言，本身就很难获取解析解。所以计算优化的主要目标还是求解最小二乘法的数值解。
梯度，直观的理解是cost函数变小的方向。
我们以一维来举例说明，高维情况可以类推。
函数\(q(x) = (1-x)^2\),当\(x=x_0\)时，其导数\(f’(x_0)\)的反方向即q(x)大小减小的方向。
也就是说:
$$x_1 = x_0 - \Delta * f’(x_0), f(x_1) <= f(x_0)$$
这样理论上，我们每步减去一个\( \Delta \) 时,就可以不断接近q(x)的最小值。
这样梯度下降逐渐收敛时，我们就得到了数值解
下图即为等高线图演示梯度下降。
wiki的定义写的很好
动态规划(英语：Dynamic programming，简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
个人理解：撇去规范的定义，动态规划(dynamic programming)的本质很简单，就是一个递推算法，特点是牺牲空间换取时间。
问题具备3个主要特点：
个人理解：
一个问题可以分解成子问题的组合，那么这个问题通常可以用递归的形式解决（最优子结构），但是递归时我们发现有些子问题是重复的（重叠子问题），为了节省时间，我们不想重复计算这些子问题，有什么办法可以“记忆”这些求过的解呢？
在满足无后效性特点的情况下，其实我们求解的时候可以反过来用递推的方式去保存出现的解，这样递推地求取最终的动态规划结果。最后获取结果其实就是去查表，表格里保存着递推过程中获取的解。
有很多经典问题，用动态规划可以获取可行解。例如：
它们的讲解在网上可以找到非常丰富的资源，本文就不在详述。
本文主要结合博主在刷leetcode过程中碰到的DP类问题来讲述DP算法。
给定一个向量a[N], a[i]代表一双袜子在第i天的价格，你可以在低价的时候买入袜子，在高价的时候卖出袜子来获取利润，问在最多可以完成k次交易的情况下，最大可以获取多少利润。
注：手上最多可以持有一双袜子，即结束上一次交易前，不可以买入新袜子。
这个问题直觉上看着就像一个动态规划问题。
阿光：怎么看出来，我怎么看不出来？
我：直觉
阿光：直觉是什么鬼？
我：作为程序员，要培养那些抽象的看问题的直觉。
阿光：。。。。。
我：多学，多练
洲妹：这个B装的我服！
我: 2
阿光：8
我们用动态规划的假设去套套看，假设最大利润函数是L(n, k):n表示只在前n天交易，k表示交易次数。那么L(n,k)是不是可以表示成f(L(n-1, k),L(n,k-1))的形式呢，也就是一个可递归的形式呢？
我刚开始分析的时候想了半天没想出来，后来实在忍不住看了一下leetcode上的discuss，看到别人代码一下子就豁然开朗了。简单的用标量L(n,k)是不行的，应该采用向量的形式，即(buy(n,k), sell(n,k))
其中sell(n,k)即表示n天内完成k次交易的最大利润，而buy(n,k)表示n天内完成k-1次交易同时减去买一双袜子的钱后手上的最大利润，本质上buy(n,k)其实是为了获取第k次购买时购买的最低价。
这样递归的形式就很清晰了:
buy(i,k) = max(buy(i-1,k), sell(i-1,k-1)-a[i])
sell(i,k) = max(sell(i-1, k), buy(i-1,k)+a[i])
对上述递推的理解也很简单
那么我们就得到了一个递归的形式，反向地也就得到了递推形式，这样就得到了一个时间复杂度O(kn)的动态规划算法。
代码如下：
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (k>=n/2) {
int sum = 0;
for(int i=1; i<n; i++){
if(prices[i] > prices[i-1]){
sum += prices[i] - prices[i-1];
}
}
return sum;
}
vector<int> buy(k+1, INT_MIN), sale(k+1, 0);
for(int i=0; i<n; i++){
for(int j=1; j<=k; j++){
buy[j] = max(buy[j], sale[j-1]-prices[i]);
sale[j] = max(sale[j], buy[j] + prices[i]);
}
}
return sale[k];
}
记住动态规划就是一个递推算法，特点是牺牲空间换取时间。
阿光，洲妹，学到了么？
ps： 码字好累
暗号： “凯” 请阿光对接！
向被惠子老师发卡的阿光致敬
问题来了，复仇之怒打死1只，2只，3只精灵龙的概率
还是用穷举的方法去解决这个问题，不过因为概率空间比较大，我们编程实现。
我们用0，1，2，3分别表示对方英雄，以及三只精灵龙，那么概率空间中的元素可以表示成一个1x8的向量。
例如：[0,1,2,3,3,2,0,0]表示8发复仇之怒分别打中0（英雄），1（第一只精灵龙），2（第二只精灵龙），… ，0(英雄)
那么这个离散概率空间的概率分布是什么呢，或者说每一个基础元素的概率是多少呢？
为了解决这个问题，我们引入马尔科夫链，为了叙述（画图）方便，我们就用这个图来讲述一下概率分布。
上图为问题《一只奥数飞弹打死一只精灵龙》的马尔科夫链
同样类似，对于本文中的问题
玩炉石的朋友经常会遇到这种情况：
这时候，问题来了：要不要用奥术飞弹呢，奥数飞弹解掉精灵龙的概率是多少呢？
这个其实是一个概率论的问题。
我们知道3发奥数飞弹全打脸的概率是1/8=(1/2 x 1/2 x 1/2),那3发奥数飞弹打死一个2血的精灵龙的概率是多少呢。
这个问题其实我们可以用穷举法表示，我们用[1,0,1]来表示第一法打中精灵龙，第二发打中英雄，第三发打中精灵龙。那么所有情形我们可以写出来：
我们发现其实[1,1,1]是不存在的，因为精灵龙中了2发奥数飞弹就被消灭了，不可能中3发，所以他的概率是0.而[1,1,0]的概率为什么是1/4呢，因为前两发打中精灵龙后，最后一发必打脸，所以概率是1/4=(1/2 x 1/2 x 1)，所以我们发现精灵龙被消灭的概率是所有打中精灵龙2发奥数飞弹的情况，即1/8 + 1/8 + 1/4 = 1/2
这是阿光智商的分割线，以下内容请勿看
为了解决更复杂的问题，我们介绍几个概率论的定义
那么本文的例子其实是求一个事件（精灵龙被消灭）对应的概率。
对于离散的的概率空间（Ω,F,P)而言,针对本文的情况，有一个很好的模型可以去解决这种问题：马尔可夫链
发现了么，其实我们可以用一个马尔科夫链表去刻画这个情形,所有叶子即概率空间的元素(从上到下的路径)
那么问题来了: 场上3只精灵龙，复仇之怒打死2只精灵龙的概率是多少？
请听下回分解：马尔可夫链之九层妖塔。