感想
线性回归是机器学习里面很经典的算法了，但是谈到一些理论假设，我想一般人可能弄不清楚，我也忽略了，看来简单的东西只是看似简单，很容易就变得很难。
problem

关于线性回归的描述,以下正确的有:
A  基本假设包括随机干扰项是均值为0,方差为1的标准正态分布
B  基本假设包括随机干扰项是均值为0的同方差正态分布
C  在违背基本假设时,普通最小二乘法估计量不再是最佳线性无偏估计量
D  在违背基本假设时,模型不再可以估计
E  可以用DW检验残差是否存在序列相关性
F  多重共线性会使得参数估计值方差减小
答案：B C E
analysis

一元线性回归的基本假设有
1、随机误差项是一个期望值或平均值为0的随机变量； 
2、对于解释变量的所有观测值，随机误差项有相同的方差； 
3、随机误差项彼此不相关；
4、解释变量是确定性变量，不是随机变量，与随机误差项彼此之间相互独立；
5、解释变量之间不存在精确的（完全的）线性关系，即解释变量的样本观测值矩阵是满秩矩阵；
6、随机误差项服从正态分布

违背基本假设的计量经济学模型还是可以估计的，只是不能使用普通最小二乘法进行估计。 
当存在异方差时，普通最小二乘法估计存在以下问题： 参数估计值虽然是无偏的，但不是最小方差线性无偏估计。

杜宾-瓦特森（DW）检验，计量经济，统计分析中常用的一种检验序列一阶 自相关 最常用的方法。 
（说实话，DW本人不是很懂，不知道为什么出现了这么个新鲜词儿，机器学习学了这么久，我也只是在这道题目里面见到。）
所谓多重共线性（Multicollinearity）是指线性回归模型中的解释变量之间由于存在精确相关关系或高度相关关系而使模型估计失真或难以估计准确。影响
（1）完全共线性下参数估计量不存在
（2）近似共线性下OLS估计量非有效
多重共线性使参数估计值的方差增大，1/(1-r2)为方差膨胀因子(Variance Inflation Factor, VIF)
（3）参数估计量经济含义不合理
（4）变量的显著性检验失去意义，可能将重要的解释变量排除在模型之外
（5）模型的预测功能失效。变大的方差容易使区间预测的“区间”变大，使预测失去意义。

参考文献
[1].牛客网.https://www.nowcoder.com/questionTerminal/94d56244abed40bf92f58e60defb03f3

说明：

本文仅提供关于两个算法的正确性的证明，不涉及对算法的过程描述和实现细节
本人算法菜鸟一枚，提供的证明仅是自己的思路，不保证正确，仅供参考，若有错误，欢迎拍砖指正
 
-------------------------------------------
 


Dijkstra算法和Floyd算法用于求解连通图中任意两个顶点之间的最短路径
 
Dijksra算法从一个顶点v0出发，每次为一个顶点vi确定到达v0的最小路径
 
Dijkstra算法用distance[i]记录顶点vi到v0的最短路径，用path[i]记录在最短路径中vi顶点的前继顶点，另外再用found[i]来标志顶点vi的最短路径是否已经确定
 
distance[]初始化为v0在邻接矩阵中的对应行，distance[i]记录了 以目前已经探明最小路径的顶点（以下简称已定顶点）（包括v0）为前继顶点 的所有路径中最短的路径长
Dijkstra算法做出了这样一个判断：每次从尚未确定最小路径的顶点中（一下简称 未定顶点）挑选一个distance值最小的顶点vj，则该顶点对应的distance[j]必定是vj的真实的最小路径长度，下面证明这个判断：
 
对于任意一个未定顶点，其最小路径中必定至少包含一个已定顶点（至少会包含v0），则该路径中至少有一个未定顶点vm以一个已定顶点vn为前继顶点，而length(v0-vn-vm) >= diatance[m] >= distance[j]，也就说任意一个未定顶点的最小路径长必定不小于distance[j]，由此就可以确定distance[j]必定是vj真实的最小路径长
 
Dijkstra算法的复杂度是n^2，每次确定一个顶点的最短路径，而确定一个顶点的最短路径需要遍历并比较distance数组，并且确定之后需要遍历更新distance数组，所以是n*n的开销
 
--------------------------------
 
Floyd算法的执行逻辑甚为简单，包含了三个循环的嵌套；其思路是遍历图中的每一个点，针对这个点vm，遍历图中任意两个顶点的两两组合vi和vj，比较vi和vj当前的最短连接和通过vm的连接的大小，并且把新的当前最短连接重置为其中更小的那个值；这样一圈遍历下来，就可以保证得到图中任意两个顶点之间的最小距离
 
这看起来并不靠谱，因为在最初vi和vm、vj和vm之间的最小路径都尚未安全确定下来的时候，如何能够马上就拿来比较，这时的比较不应该是无效的吗？
 
但是事实上并不需要每一步都实现严格的有效的比较，因为全部遍历下来之后，肯定会发生一次有效的比较
 
下面给出证明：
假设vi、vj之间的最小路径一共包括x个其它顶点，显然这条路径也确定了其中任何两个顶点之间的最小路径，否则比如vm、vn之间有不属于当前路径的最小子路径，则用该子路径替代当前的子路径，就可以得到更小的vi、vj之间的最小路径
 
对于这条路径上的任意三个相邻（至少会有一组相邻三顶点）顶点vm1、vm2、vm3，当遍历到vm2时，显然此时vm1-vm2-vm3这条最小子路径就会被连接起来（因为这条路径必定是vm1到vm3的最小子路径）；事实上，当遍历到这条最小路径上的任意一个顶点的时候（除了vi、vj），就会把相邻的两个顶点连接起来；当所有顶点都被遍历之后，这x个顶点也必定已经把其在最小路径上相邻的顶点全都连接完毕，包括分别在两端的vi和vj顶点；换句话说，vi和vj之间的最小子路径必定已经被找到
 
Floyd算法的复杂度为n^3
转载于:https://www.cnblogs.com/tahitian-fang/p/5754946.html

 


说明：

本文仅提供关于两个算法的正确性的证明，不涉及对算法的过程描述和实现细节
本人算法菜鸟一枚，提供的证明仅是自己的思路，不保证正确，仅供参考，若有错误，欢迎拍砖指正
 
-------------------------------------------
 


Dijkstra算法和Floyd算法用于求解连通图中任意两个顶点之间的最短路径
 
Dijksra算法从一个顶点v0出发，每次为一个顶点vi确定到达v0的最小路径
 
Dijkstra算法用distance[i]记录顶点vi到v0的最短路径，用path[i]记录在最短路径中vi顶点的前继顶点，另外再用found[i]来标志顶点vi的最短路径是否已经确定
 
distance[]初始化为v0在邻接矩阵中的对应行，distance[i]记录了 以目前已经探明最小路径的顶点（以下简称已定顶点）（包括v0）为前继顶点 的所有路径中最短的路径长
Dijkstra算法做出了这样一个判断：每次从尚未确定最小路径的顶点中（一下简称 未定顶点）挑选一个distance值最小的顶点vj，则该顶点对应的distance[j]必定是vj的真实的最小路径长度，下面证明这个判断：
 
对于任意一个未定顶点，其最小路径中必定至少包含一个已定顶点（至少会包含v0），则该路径中至少有一个未定顶点vm以一个已定顶点vn为前继顶点，而length(v0-vn-vm) >= diatance[m] >= distance[j]，也就说任意一个未定顶点的最小路径长必定不小于distance[j]，由此就可以确定distance[j]必定是vj真实的最小路径长
 
Dijkstra算法的复杂度是n^2，每次确定一个顶点的最短路径，而确定一个顶点的最短路径需要遍历并比较distance数组，并且确定之后需要遍历更新distance数组，所以是n*n的开销
 
--------------------------------
 
Floyd算法的执行逻辑甚为简单，包含了三个循环的嵌套；其思路是遍历图中的每一个点，针对这个点vm，遍历图中任意两个顶点的两两组合vi和vj，比较vi和vj当前的最短连接和通过vm的连接的大小，并且把新的当前最短连接重置为其中更小的那个值；这样一圈遍历下来，就可以保证得到图中任意两个顶点之间的最小距离
 
这看起来并不靠谱，因为在最初vi和vm、vj和vm之间的最小路径都尚未安全确定下来的时候，如何能够马上就拿来比较，这时的比较不应该是无效的吗？
 
但是事实上并不需要每一步都实现严格的有效的比较，因为全部遍历下来之后，肯定会发生一次有效的比较
 
下面给出证明：
假设vi、vj之间的最小路径一共包括x个其它顶点，显然这条路径也确定了其中任何两个顶点之间的最小路径，否则比如vm、vn之间有不属于当前路径的最小子路径，则用该子路径替代当前的子路径，就可以得到更小的vi、vj之间的最小路径
 
对于这条路径上的任意三个相邻（至少会有一组相邻三顶点）顶点vm1、vm2、vm3，当遍历到vm2时，显然此时vm1-vm2-vm3这条最小子路径就会被连接起来（因为这条路径必定是vm1到vm3的最小子路径）；事实上，当遍历到这条最小路径上的任意一个顶点的时候（除了vi、vj），就会把相邻的两个顶点连接起来；当所有顶点都被遍历之后，这x个顶点也必定已经把其在最小路径上相邻的顶点全都连接完毕，包括分别在两端的vi和vj顶点；换句话说，vi和vj之间的最小子路径必定已经被找到
 
Floyd算法的复杂度为n^3

 
转载自：https://www.cnblogs.com/tahitian-fang/p/5754946.html
 
 

转载于:https://www.cnblogs.com/oycy0306/p/9280350.html

定义：

算法是指对特定问题求解步骤的一种描述。

 

 

特性：

（1）有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。

（2）确定性：每条语句有确定的含义，无歧义。

（3）可行性：算法在当前环境条件下可以通过有限次运算实现。

（4）输入输出：有零个或多个输入，一个或多个输出。

 

 

“好”算法的标准如下：

（1）正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期的需求。

（2）易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。

（3）健壮性：算法对非法数据及操作有较好的反应和处理。例如，在学生信息管理系统中登记学生年龄时，若将21岁误输入为210岁，系统应该提示出错。

 

（4）高效性：高效性是指算法运行效率高，即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。现代计算机一秒钟能计算数亿次，因此不能用秒来具体计算算法消耗的时间，由于相同配置的计算机进行一次基本运算的时间是一定的，我们可以用算法基本运算的执行次数来衡量算法的效率。因此，将算法基本运算的执行次数作为时间复杂度的衡量标准。

（5）低存储性：低存储性是指算法所需要的存储空间低。对于像手机、平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小称为空间复杂度。

 

 

算法的两大分类：

一个是数据结构（数据对象）：数、矩阵、集合、串、排列、图、表达式、分布等。

另一个是算法策略：贪心、分治、动态规划、线性规划、搜索等。

 

这两条线索是相互独立的：同一个数据对象（比如图）上有不同的问题（如单源最短路径和多源最短路径），就可以用到不同的算法策略（例如贪婪和动态规划）；而完全不同的数据对象上的问题（如排序和整数乘法），也许就会用到相同的算法策略（如分治）。

 

 

如何学习算法（个人想法）：

（1）HACK精神：对这个事物拥有这极高的热情，对这个事物有一种快速掌握的渴望，对这个事物不断问为什么，亲自去做并在这个过程中明白当初问为什么的到底是个啥以及明白这个问题的答案是什么。

（2）数学与逻辑：在我的学习编程或是在学习算法的过程中，无数次的实践告所我——算法的灵魂是数学以及思维逻辑。例如，在编程1+2+3+ …… +n时，采用 "for(int i=1;i<=n;i++) { sum+=i; }" 和直接用等差数列求和公式是完全不一样的。所以掌握一定的数学和逻辑方法是必要的。

（3）适合自己的学习材料：对于我来说，学习一样新的事物，学习的资料是十分重要的，或者直接说，学习的材料直接决定我第一次学习时的效率和深度；那么对于你来说，也是一样，找到真正适合自己的学习材料是你在学习前应该着重做的事情；那么，应该怎么找寻材料呢？例如，图书馆的图书，博客，个人网站等；需要注意的是，如果选择博客或个人网站作为学习材料，那个博客或个人网站应该有成体系的知识结构和层次。

（4）去做：当你看懂了材料所描述以后，立即需要做的就是去实现它——自动编程实现它，这是为了避免“产生了学会了的错觉，实际上是看懂了的感觉”。其次，也是最重要的，就是做好笔记，便于复习。在做笔记时，我的原则是“① 不做冗余的笔记——只有自己真正实践或理解才做；笔记的真正目的是为了以后的快速复习！ ② 在自己所做的笔记中，无论知识怎么难，只要是理解了所做的笔记，如果在下一次去看，不能快速看懂的，就是垃圾一样的笔记！”

（5）适时复习：这一点没什么可说的，你可以参考“艾宾浩斯遗忘曲线”来自定义复习时间。

 

 

[ 注: 部分内容出自《趣味算法》作者：陈小玉 (人民邮电出版社) ]