通常考察一个算法的性能通常用局部搜索能力和全局收敛能力这两个指标。局部搜索是指能够无穷接近最优解的能力，而全局收敛能力是指找到全局最优解所在大致位置的能力。



人同样不也有与这类似两种能力么？局部搜索能力对应人对于自己所遇到的事情刨根究底，从而精通的能力。举个例子，这种能力可以是与人交往的能力，学好功课的能力，创业的能力，做饭的能力，甚至蹭饭的能力。。。而全局搜索能力则对应着一个人的是否对全局信息有较好的把握，在不断失败的尝试中，然后找到了自己喜欢的一种生活状态。



局部搜索能力和全局搜索能力，缺一不可。如果一味强调精而忽视广，就会陷入极其狭隘的空间，成为了井底之蛙。如果过于喜新厌旧，浅尝辄止，则会失去了体验生活独到之处的机会。



我们不也正是这样么？高中毕业时，大家走向了不同的大学，从此我们的搜索空间开始不同。有的人到了大学，在“娱乐”这个解附近徘徊不前，精通“娱乐”这门艺术；有的人喜欢上了“学习”，学习使他们产生了一种偏执，“万般皆下品，惟有读书高”；更多的人游荡在大学中我们可能接触到的解附近，寻寻觅觅想找到自己梦中的归宿，苦苦追寻想看清自己的未来。



向最优解的导向，对于任何智能算法的性能都是很重要的。同样，我相信，对“人生最优解”的渴望，将引导着我走向自己人生最美的地方。

 
 
 
 
 $\textbf{平时我看起来很坚强，}$ 
 
 
 
 $\textbf{可是遇到你，我会变成另一个模样。}$ 
 
 
 
 $\textbf{我不想考虑太多，}$ 
 
 
 
 $\textbf{因为追随内心，你已经走进我的心墙。}$ 
 
 
 
 $\textbf{我想让你知道，}$ 
 
 
 
 $\textbf{我从未想过放手，}$ 
 
 
 
 $\textbf{只愿陪你到永远。}$ 
 
 
 
 $\qquad\qquad\quad\textbf{——畅宝宝的傻逼哥哥}$ 
 
 

 
如果一个算法满足这样的性质：任意的初始点$\textbf{x}_0\in X$都会产生一个收敛的点序列$\{\textbf{x}_k\}_{k=0}^\infty$，那么称该算法是全局收敛的。实际上，如果某些条件不满足，甚至非常有效的算法都会失效。例如算法可能产生不收敛的序列或者收敛的点不是所求的解，存在一些导致算法失败的因素，但是如果我们很清楚的了解他们，那么我们就能采取某些避免失败的措施，所以全局收敛成为理论学者与实践者共同的兴趣。
 
大部分全局收敛理论处理的是保证全局收敛的环境与条件，其中一个重要的理论如下：
 
$\textbf{定理1：}$令A表示X上的算法并假设初始点$\textbf{x}_0$将产生一个无穷序列$\{\textbf{x}_k\}_{k=0}^{\infty}$，其中 
 
 $$\textbf{x}_{k+1}\in A(\textbf{x}_k)$$ 
 
如果该算法的解集S与下降函数$D(\textbf{x}_k)$存在，使得
 
所有点$\textbf{x}_k$包含在X的紧子集中
$D(\textbf{x}_k)$满足下降函数的定义且
A的映射对S外的所有点都封闭
 
那么任何收敛序列$\{\textbf{x}_k\}_{k=0}^{\infty}$的极限都是解。
 
$\textbf{证明：}$这个定理的证明分两部分。对a部分，我们假设$\hat{\textbf{x}}$是任何序列$\{\textbf{x}_k\}_{k=0}^{\infty}$子序列$\{\textbf{x}_k\}_{k\in I}$的极限，其中I是整数的一个集合，并且说明$D(\textbf{x}_k)$对无限序列$\{\textbf{x}_k\}_{k=0}^{\infty}$收敛。对b部分，我们说明$\hat{\textbf{x}}$是集合S的解。
 
证明的第二部分非常依赖于魏尔斯特拉斯定理，如果W是紧集，那么序列$\{\textbf{x}_k\}_{k=0}^{\infty}$的极限点在W中，其中$\textbf{x}_k\in W$。如果集合W是闭的，那么它也就紧集。如果W边界上的所有点都属于W，那么W是闭集。如果W能被一个有限半径的超球包围，那么W是有界集。魏尔斯特拉斯定理的一个结论是$\{\textbf{x}_k\}_{k=0}^{\infty}$的任何子序列$\{\textbf{x}_k\}_{k\in I}$的极限位于集合$\bar{W}=\{\textbf{x}_k:k\in I\}$中，因为$\bar{W}$是W的子集，所以它也是紧集。
 
(a)因为$D(\textbf{x}_k)$在X上是连续的且$\hat{\textbf{x}}$是序列$\{\textbf{x}_k\}_{k\in I}$的极限，所以存在正数与整数K使得当$k\geq K$时 
 
 $$D(\textbf{x}_k)-D(\hat{\textbf{x}})<\varepsilon$$ 
 
其中$k\in I$，因此$D(\textbf{x}_k)$对子序列$\{\textbf{x}_k\}_{k\in I}$收敛。然而我们还必须证明$D(\textbf{x}_k)$对无限序列$\{\textbf{x}_k\}_{k=0}^{\infty}$收敛。
 
对于任意$k\geq K$，我们有 
 
 $$D(\textbf{x}_k)-D(\hat{\textbf{x}})=[D(\textbf{x}_k)-D(\textbf{x}_K)]+[D(\textbf{x}_K)-D(\hat{\textbf{x}})]$$ 
 
如果$k=K$，那么 
 
 $$D(\textbf{x}_K)-D(\hat{\textbf{x}})<\varepsilon$$ 
 
如果$k\geq K$，那么$D(\textbf{x}_k)\leq D(\textbf{x}_K)$，因此 
 
 $$D(\textbf{x}_k)-D(\textbf{x}_K)\leq 0$$ 
 
由此可得对任意$k\geq K$ 
 
 $$D(\textbf{x}_k)-D(\hat{\textbf{x}})<\varepsilon$$ 
 
因此 
 
 $$\lim_{k\to\infty} D(\textbf{x}_k)=D(\hat{\textbf{x}})$$ 
 
即当$\textbf{x}_k\to\hat{\textbf{x}}$时$D(\textbf{x}_k)$相对于无限序列收敛。
 
(b)假设$\hat{\textbf{x}}$不在解集中，因为子序列$\{\textbf{x}_{k+1}\}_{k\in I}$的元素属于属于紧集，根据魏尔斯特拉斯定理可知存在紧子集$\{\textbf{x}_{k+1}:k\in\bar{I}\subset I\}$使得$\textbf{x}_{k+1}$收敛到极限$\bar{\textbf{x}}$。根据部分(a)，我们说明了 
 
 $$\lim_{k\to\infty}D(\textbf{x}_{k+1})=D(\bar{\textbf{x}})$$ 
 
因此 
 
 $$D(\bar{\textbf{x}})=D(\hat{\textbf{x}})$$ 
 
另一方面 
 
 $$\begin{align*}
\textbf{x}_k\to\hat{\textbf{x}}\quad &for\ k\in\bar{I}\\
\textbf{x}_{k+1}\to\bar{\textbf{x}}\quad &for\ \textbf{x}_{k+1}\in A(\textbf{x})
\end{align*}$$ 
 
根据假设$\hat{\textbf{x}}\notin S$，并且A对S外的点是闭的，我们有 
 
 $$\bar{\textbf{x}}\in A(\hat{\textbf{x}})$$ 
 
因此 
 
 $$D(\bar{\textbf{x}})<D(\hat{\textbf{x}})$$  
 
得出矛盾，因为$\{\textbf{x}_k\}_{k=0}^{\infty}$的任何收敛子序列的极限是解。
 
对于简单的情况，上面的定理说明，如果
 
算法生成的点在有限的$E^n$空间中
可以找到满足要求的下降函数
算法在解邻域的外边是封闭的
 
那么算法是全局收敛的。进一步，我们可以在有限次迭代下得到近似解，因为$\{\textbf{x}_k\}_{k=0}^{\infty}$的任何有限子序列的极限都是解。
 
定理1的推论同样非常重要：
 
$\textbf{推论1：}$如果定理1的条件成立，解集S由一个点$\hat{\textbf{x}}$组成，那么序列$\{\textbf{x}_k\}_{k=0}^{\infty}$收敛到$\hat{\textbf{x}}$。
 
$\textbf{证明：}$如果我们假设有一个子序列$\{\textbf{x}_k\}_{k\in I}$不收敛到$\hat{\textbf{x}}$，那么对于所有的$k\in I,\varepsilon>0$， 
 
 $$\Vert\textbf{x}_k-\hat{\textbf{x}}\Vert>\varepsilon$$ 
 
集合$\{\textbf{x}_k\in I^{'}\subset I\}$是紧集，$\{\textbf{x}_k\}$

最优化理论课程的作业，证明line search Newton下的全局收敛性质
 利用gradient related的性质，通过反证法得出结论，资源正在上传中

图像特征分为全局特征和局部特征两种，其中全局特征代表了图像的整体表现特性，比如颜色直方图，而局部特征代表了图像的局部特性，往往能够从一幅图片中提取出若干个数量不等的局部特征， 
 这些局部特征组合起来代表了整幅图像的特征分布。其中局部特征提取算法（比如SIFT）提取出来的局部特征称为描述子，比如SIFT描述子的维度为128，那么如果从一张图像中提取出m个描述子， 
 该幅图像的描述子矩阵为m*128。每一张图片提取出的局部特征数可能是不同的，那么我们需要将这些不同数目的描述子融合成一个特征向量（假设维度为n）来表征整个图像，这样一张图片就可以用一个1*k 
 的向量来表征。这样做后就可以方便的实现图片检索，分类任务。
 
其中将局部特征融合为图片全局特征表示需要一个模型来转化。
 
BOW 
 其中源自文本分类领域的词袋模型（BOW）被应用于此就是一个很成功的应用案例。词袋模型通过对局部特征描述子进行聚类得到视觉单词，有了视觉单词就可以很方便地构建视觉词典。BOW典型的做法是计算图片所有描述子映射到离描述子最近的视觉单词，通过计算视觉单词词频来表征图片特征，其中这儿可以类似文本分类算法计算视觉单词的权重系数（IDF 
 inverse document frequency）来优化特征向量，还可以进行正则化（L2正则）。BOW得到的特征向量维度和视觉词典大小有关（也就是聚类中心数有关）
 
Fisher vector 
 fisher vector是通过fisher kernel计算。。。这儿fisher vector的计算过程很复杂，参考论文。 
 其中VLFEAT提供了fisher vector的计算接口，可以得到2*D*K维的fisher vector向量，该向量就是将一张图片中 
 的m*128维（假设用SIFT提取的特征）的描述子转化为一条表征整个图片的特征向量，最后得到的特征向量和BOW模型得到的特征向量是一样的效用。
 
聚类分为hard，soft聚类
 
hard聚类是非1即0型也就是说某个待聚类样本只能属于某个聚类中心，不属于其他聚类中心。（此方法的hard就这个感觉）
 
soft聚类以概率表征待聚类样本属于哪个聚类中心，这也比较合理。（某些样本离某些聚类中心又不近又不远，用概率表示归属于哪个聚类中心也比较符合自然感受）
 
典型的聚类算法有Kmeans，GMM等
 
GMM算法主要采用EM算法来计算聚类中心，Kmeans类似
 
EM算法可以说是用极大似然估计求参数估计的升级版本，EM算法是求得含有隐变量的利器，在求GMM算法的参数估计中发现样本标签算得上是隐变量了，EM求GMM参数估计的核心思路就是先初始化GMM参数值，计算在当前GMM参数下样本的聚类结果（分类结果，也就是求得了隐变量），该步骤称为E步骤。接下来再根据上面求得得样本标签（也就是隐变量）来求似然函数的极大参数估计，此步骤称为M步。接下来将M步求得的GMM参数计算E步，如此反复迭代，直到模型收敛且估计的参数不再有大变动。其中EM算法求得的GMM参数也可能是局部极值。 
 
参考python实现fv，vlad，bow https://github.com/jeromewang-github/computer_vision
 
参考资料：论文，http://yongyuan.name/blog/CBIR-BoF-VLAD-FV.html