归并排序

首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中  
void merge(int a[], int n, int b[], int m, int c[]) {
    int i, j, k;  
    i = j = k = 0;  
    while (i < n && j < m) {  
        if (a[i] < b[j]) c[k++] = a[i++];  
        else c[k++] = b[j++];   
    }  
    while (i < n) c[k++] = a[i++];  
    while (j < m) c[k++] = b[j++];  
}  

可以发现合并有序数列的效率是非常高的,有O(N)此时N = len(a)+len(b)。

加上一点分治的想法:
mergesort1

从而对于一个数组,我们可以如下的方式二分分治:
mergesort2

如上图所示,最下面是我们需要排序的数组。我们把它分成N个长度为1的区间。那么相邻两个区间进行一次… Read the rest

什么是LaTeX

了解LaTeX之前,首先要知道TeX,TEX(TeX)是由著名的计算机科学家Donald E. Knuth(高德纳)发明的排版系统,本质上还是一门宏语言。而LaTeX是基于这门宏语言,经过后人不断的完善形成的一种排版格式。

其和现在很多人使用的、常常用于写文章的Markdown格式,没有本质的不同,都是通过不同标签来控制文章的格式。

快速安装

先给出结论:推荐使用TeX Live( https://tug.org/texlive ) (编译器、内核)+Atom(https://atom.io) (编辑器、IDE)

  1. 分别完全安装上述两个软件
    • TexLive的安装时间会很长,因为它会下载很多可能会用到的宏包,慢慢等待吧=v=
  2. 打开Atom,File -Settings -Install,搜索并安装
    • language-latex
    • latex
    • pdf-view
  3. 安装后,File -Settings -Packages,点击latex的settings选项
  4. 在第一个空白栏“Tex Path”中添加自己安装latex所在的bin目录
  5. 环境已经配置成功,输入下面的测试代码并使用Ctrl+Alt+B运行(或者通过 Packages -LaTeX
Read the rest

前言

本文用尽量简短和明了的方式说明什么是模糊评价模型,以及怎么使用,所以表述可能在数理上不太严谨,请读者多加包涵。

什么是模糊数学模型

1965 年,美国著名计算机与控制专家查德(L.A.Zadeh)教授提出了模糊的概念,并在国际期刊《Information and Control》并发表了第一篇用数学方法研究模糊现象的论文“Fuzzy Sets”(模糊集合),开创了模糊数学的新领域。

模糊数学中有一个研究的热点问题就是“模糊决策”,它就是研究在模糊环境下或者模糊系统中进行决策的数学理论和方法。模糊决策的目标是把决策论域中的对象在模糊环境下进行排序,或按某些模糊限制条件从决策域中选择出最优对象。

当被评价的对象有两个以上时,从多个对象中选择出一个最优的方法称为多目标模糊综合评价决策法。可以将多个事物排序,得到相对排名和得分。
对于美赛,很多问题都可以通过模糊评价模型来得到答案。

基本步骤

  1. 为属性确定特征及其隶属函数
  2. 计算隶属度矩阵
  3. 确定评价矩阵,计算权重
  4. 检验评价矩阵
  5. 计算最后得分并排序
  6. 选取前6个

模糊评价模型的基本概念

模糊集和隶属函数

模糊集:我们要排序的事物集合,这里不妨记作A。
特征:为了将A排序,我们自然… Read the rest

什么是哈夫曼树

给定n个权值,作为n个叶结点,构造一棵二叉树,而这棵树的特点是,有n个叶节点,叶节点的值为给定的权值。而内部节点的值为子树的权值和。

这样的二叉树有很多,但树的带权路径和达到最小,则这棵树被称为哈夫曼树。
huffman tree 1

Note:带权路径和指的是所有叶节点的权值*深度和,即\(\Sigma value∗deep=100+2∗50+3∗20+3∗10\)

而我们不妨让内部节点的值为子树的权值和,我们可以发现,实际上一棵树的带权路径和=这棵树的所有节点值之和-根节点的值。(显然)

哈夫曼树有什么用

哈夫曼树主要应用在文本编码上。我们考虑如何将文本中出现的单词编码为二进制数(01串),让文本的总长度最小。

对于文本{1, 1, 2, 2, 3, 3, 3, 5},我们可以将单词1、2、3、5出现的频率作为叶节点的权值,为{2, 2, 3, 1}。那么上述最短编码问题等价于寻找一棵树,其带权路径和最小,也就是找对应的哈夫曼树。

唯一可译码

如果我们直接将单词按照频率的从高到低排序,不就得到了一个编码了吗?

但这样的编码不是一个“唯一可译码”,即对于10001010100101,我们不… Read the rest

前言

梯度是机器学习中的重要概念,其和拉格朗日乘数法、梯度下降法之间的联系密不可分。所以本文给出了梯度的定义,并证明负梯度的方向是函数下降最快的方向(梯度的方向是函数上升最快的方向)。

至于为什么梯度下降算法能够work,是因为对于凸函数,随着函数下降的方向,一定能到达最小值。取梯度是为了沿最快下降方向,降低迭代次数。后来发现对于非凸函数,梯度下降算法表现不错,所以对于非凸函数也有使用。更具体的内容,见下一篇文章《梯度下降算法》。

本文重点结论

本文有大量证明,部分读者可能会感到有些冗余,故将重点结论罗列于下:
1. 梯度\(
\nabla f\left( {{\theta_1},{\theta_2},\cdots,{\theta_n}} \right) = \left( {\frac{{\partial f}}{{\partial {\theta_1}}},\frac{{\partial f}}{{\partial {\theta_2}}},\cdots,\frac{{\partial f}}{{\partial {\theta_n}}}} \right)
\)
2. 梯度的方向是函数上升最快的方向
3. 梯度是 || … Read the rest

前言

最小二乘法在统计学的地位不必多言。本文的目的是全面地讲解最小二乘法,打好机器学习的基础。本文主要内容是最小二乘法的思想及在线性回归问题中的应用。后面的系列文章会继续讲解最小二乘的正则化。
至于非线性最小二乘和广义线性模型,如果以后有时间会进行整理。

不熟悉极大似然法的读者可以阅读我的另一篇文章《十分钟学习极大似然估计

updata 2019/6/13:添加了对线性回归问题的矩阵定义和简要介绍,修改了少量句子,修正了公式中的少量错误。

核心思想

最小二乘法是勒让德( A. M. Legendre)于1805年在其著作《计算慧星轨道的新方法》中提出的。它的主要思想就是求解未知参数,使得理论值与观测值之差(即误差,或者说残差)的平方和达到最小:
\[E = \mathop \sum \limits_{i = 1}^n e_i^2 = \mathop \sum \limits_{i = 1}^n {\left( {{y_i} – \hat y} \right)^2}\]
观测值\(y_i\)就是我们的多组样本,理论值\(\hat y\)就是我们的假设拟合函数。目标函数也就是在机器… Read the rest

前言

参数估计是机器学习里面的一个重要主题,而极大似然估计是最传统、使用最广泛的估计方法之一。

本文主要介绍了极大似然估计,简单说明了其和矩估计、贝叶斯估计的异同,其他估计(如MAP)并不涉及。

为什么要用极大似然估计

对于一系列观察数据,我们常常可以找到一个具体分布来描述,但不清楚分布的参数。这时候我们就需要用极大似然估计来求解这个分布的参数。换句话说,极大似然估计提供了一种给定观察数据来评估模型参数的方法,即:“模型已定,参数未知”。

极大似然估计概述

下面结合一个例子介绍极大似然估计法的思想和方法:

设一个袋子中有黑、白两种球,摸到白球的概率为p,现在要估计p的值。
我们令总体X为
\[
X = \left.
\begin{cases}
0,\quad 从袋中取得一白球,\\
1,\quad 从袋中取得一黑球.\\
\end{cases}
\right.
\]
则X服从01分布\(B(1,p)\)。

我们先进行有放回地摸球10次,其结果可用随机变量\(x_i\)表示,则\(x_1,x_2,⋯,x_10\)是… Read the rest

前言

我撰写本文的目的在于简单总结LaTex数学公式的语法。更具体的说,本文是面向仅需要使用LaTex来生成数学公式的初学者和希望通过mathjax插件在文章里插入数学公式的作者们。

本文分为上下两个部分,上半部分介绍基本的公式,看完你就能打出任何一本数学书籍中的单行公式了。下半部分难度稍高,包含介绍如何书写跨行公式、如何绘制表格等内容,具体见“LaTex数学公式简明教程(下)”。

所以本文不涉及与数学公式不太相关的LaTex内容。换句话说,不会出现对诸如“如何让小数点对齐”、“如何添加编号”问题的解答。

概述

LaTex 使用一种特殊的模式来排版数学符号和公式(mathematics)。
段落中的数学表达式应该置于 \(\)$$ 或者 \begin{math}\end{math} 之间,它们是嵌入文本的。
对于较大的数学式子,最好的方法是将它们放置于 \[\]\begin{displaymath}\end{displaymath} 之间。这样公式会单独占用一行。

Note:

  • 在使用Markdown编辑器时,\( 应该转义为\\(,换行的\\转义为\\\\,大括号\{转义为\\{
  • 这里的“转义”可以
Read the rest

前言

本文简述了离散型分布,阐明了泊松分布的来源,推导出泊松分布的公式,列举了泊松分布常用的情况,总结了泊松分布相关数值。

离散型分布概述

离散型分布包括几何分布、超几何分布、二项分布和泊松分布。其中二项分布和泊松分布最重要。

伯努利试验

对于一个试验(事件),如果重复发生的概率是独立地(上一次的结果不影响这次),那么它是独立试验。特别地,如果这个试验只存在两种结果,则称其为伯努利试验。

随机变量

对于有现实世界意义的数,我们根据意义的不同,将其划分为不同的类,而对于同一类的数,都使用同一个随机变量来称呼。比如,x年x月x日下雨量,我们就可以使用“随机变量X”来称呼;x年x月x日下雨可能性,我们就用“随机变量Y”来称呼。

需要明确的是:

  • 随机变量是一类有相同意义的数,而不是某个数
  • 当使用随机变量作为一个数时,我们需要指定这个随机变量。比如“2017年1月25日下雨量”在数学上才是一个具体的值。
  • 随机变量不一定能用除一一映射以外的方式拟合

几何分布

对于重复n次的伯努利试验,我们可以计算“首次为1是出现在第K次试验”:\({P_k} = p{q^{(k – 1)}}\)
如果一个… Read the rest

问题背景

  1. 我使用OneNote写总结。
  2. 在总结数论相关的算法时,文章会包含数学公式。
  3. 数学公式是MS特有的格式。
  4. 直接将OneNote复制到WordPress会导致几乎所有格式的丢失,数学公式无法显示

解决经历

  1. 尝试从OneNote导出。
    只支持导出doc和pdf
    1. 导出doc
      doc效果很好,但不能直接复制到WordPress中
    2. 导出pdf
      pdf效果很好,但唯一能插入到WordPress的方法是作为附件插入。即使安装了增强插件,也只是能将pdf显示出来。这样带来的问题是,搜索引擎无法抓取,显示效果也不好。

    3. 导出MS公式
      见后文

  2. 从word作为起点
    word可以导出的格式就有很多了,包括.html、.mht。

    1. 导出.html
      和pdf类似,无法作为文章一部分显示。
    2. 导出.mht
      和pdf类似,无法作为文章一部分显示。

    3. 通过Word,调用Server的PRC远程过程调用接口
      见后文

Word的“发布到博客功能”

在比较早的时候,WordPress可以设置启用xml-prc远程发布,现在应该是默认开启这个功能了。

但我在使用Word发布的时候出现了下图的情况:
WprdPress Math 1

经过WireShark抓包,大致原因是一段时间后Client端的… Read the rest