Algorithm

Sort Algorithms of Linear Time Complexity

常用排序算法如归并、快排、堆排序等基于比较的排序方法都是不能突破$O(n log n)$时间复杂度的,本文着重介绍几种线性时间复杂度的排序方法。 基于比较的排序为何不能突破$O(n log n)$时间复杂度?因为$N$个数有$N!$个可能的排列情况,也就是说基于比较的排序算法的判定树有$N!$个叶子结点,比较次数至少为$log(N!)= O(N log N)$ (斯特林公式) 而线性复杂度的排序方法通常来说有计数排序、桶排序和基数排序三种。 计数排序 计数排序(Counting sort)是一种稳定的线性时间排序算法,Θ(n + k)的时间复杂度。n 是待排序数组的大小,k 是辅助数组 count 的大小。 因为它并不是基于比较的的排序算法,所以它没有O(NlogN)的下限。并且在一定的条件下,使用该算法比使用快排能带来更好的效率。例如在基数排序中就运用了计数排序,因为它只需要额外的10个元素大小的辅助数组,线性的效率,并保证了稳定性。 原理 计数排序的主要思想是将待排序元素的值作为下标,利用辅助数组 count 记录所有的元素出现的次数。即 count[i] 的值代表元素 i 在原始数组中出现的次数。这样,原始数组的所有元素就被有有序地记录下来。 当然,只知道某个元素出现的次数是不足以排序的。仔细观察 count 数组,发现对 count 数组进行累加(count[i] += count[i-1])后,count[i] 的含义就变成了原始数组 i 前面有 count[i]个数是不大于它的。最后就可以根据 count 数组中的排名去构造一个已排序的数组了。 下面以原始数组d = {8, 13, 0, 3, 20, 16, 9, 7, 11, 5} 去演示上述的过程: …

Sort Algorithms of Linear Time Complexity Read More »

AliPay RedEnvelope Hacker

最近支付宝继续其逆天改命的追赶超越微信的社交梦之路,上线了狂拽酷炫吊炸天的AR红包玩法,顿时刷爆了一波朋友圈,但是这热闹后面也隐藏着一些问题甚至是致命Bug或者危机。 AR红包一上线,毁誉参半,有媒体人产品方面人士表示“这是支付宝在对抗微信的战场上,难得的漂亮反击”,但是。。。同时很快有天才找到了作弊的方法,所谓实现了“早上试了一下,现在已经实现在家收红包的局面了”,方法其实类似我之后提到的,只是他用的是PS。。。方法是: 截图放到ps里,建立和黑色条纹等宽的长条若干; 黑色条纹然后往上移动一点,覆盖住显示图片的区域,再复制一张截图置于顶层建立剪贴蒙板,把位置错来来看; 扫一下就可以领取红包了 以上来自知乎用户@Chain 很快我又找到了代码版本,是用php实现的,数行代码即可搞定(为了跑成功花了半小时学习如何安装并跑出php的Hello World,囧~): 12345678910111213141516171819202122232425262728293031323334353637 <?phpfunction imagecropper($source_path){$source_info = getimagesize($source_path);$source_width = $source_info[0];$source_height = $source_info[1];$source_mime = $source_info['mime'];$oldimg = imagecreatefrompng($source_path);$base_width=340;$base_height=6;$baseimage = imagecreatetruecolor($base_width, $base_width);// 苹果图啊$beginx = 150;$beginy = 444;$thisimage = imagecreatetruecolor($base_width, $base_height);imagecopy($baseimage, $oldimg, 0, 0, $beginx, $beginy, $base_width, $base_height);for ($i=0;$i<30;$i++){imagecopy($baseimage, $oldimg, 0, $i*($base_height*2)-$base_height, $beginx, ($beginy+($i*($base_height*2))), $base_width, $base_height);imagecopy($baseimage, $oldimg, 0, $i*($base_height*2), $beginx, ($beginy+($i*($base_height*2))), $base_width, $base_height);}header('Content-Type: image/png');imagepng($baseimage);}imagecropper("http://127.0.0.1/frank/img/IMG_0734.png")?> …

AliPay RedEnvelope Hacker Read More »

Devide and Conquer Counting Inversions with Python

本文主要内容关于python归并排序求逆序数的算法。 解决问题:给定有限长度的无重复乱序数组,求其逆序数个数。简单来说我们可以用两个循环来解决,但是复杂度为$O(N^2)$,若利用归并排序,复杂度就降为了$O(N log(N))$。以下给出一个实现, 123456789101112131415161718192021222324252627282930313233343536373839404142 class Ivrs_num(object): def __init__(self, filename): self.count = 0 self.filename = filename def load_txt(self): '''载入txt文件保存为list''' int_list = [] with open(self.filename) as f: for line in f: int_list.append(int(line)) return int_list def merge(self, ListA, ListB): '''将两个已经排序好的数组合并成新的排序好的数组 顺便计算逆序数''' newList = [] while ListA and ListB: if int(ListA[0]) > int(ListB[0]): self.count += len(ListA) newList.append(ListB.pop(0)) else: newList.append(ListA.pop(0)) …

Devide and Conquer Counting Inversions with Python Read More »

神经网络术语大百科:优化函数、激活函数、损失函数、正则方法的简介

简述关于神经网络的各种优化函数(SGD,Adagrad,Adadelta,Adam,Adamax,Nadam)、各种激活函数(Sigmoid,Tanh、Hard Sigmoid、Softplus、ReLU、ElU、PReLU、RReLU)、各种损失函数以及正则方法的简述,并附带代码实现例子。 优化函数 先上两张图 激活函数 没有激活函数,神经元就只是一个线性函数,那么无论多少层的神经元叠加是没有意义的。而主流激活函数也随着神经网络、深度学习的发展迭代进化了许多次代。 Sigmoid Sigmoid是S形状的意思,又因为它是逻辑回归的激活函数又叫logistic函数,函数式为$y = 1 / (1 + exp(-x))$是很早以前最常用的激活函数,其实也是有一些优点的,比如, 值域位于0-1,那么对于逻辑回归,这是对于二分类的一个很自然的表达,也就是概率 处处连续可导 不过呢,我们观察它的形状,可以得出,Sigmoid函数在两端(靠近0和1的部分)梯度很小,这也意味着,如果神经元的输出落到了这个地方,那么它几乎没什么梯度可以传到后面,而随着神经网络的层层削弱,后面的层(靠近输入的层)没有多少梯度能传过来,几乎就“学不到什么”了。这叫做梯度消失问题,一度是阻碍神经网络往更深的层进化的主要困难,导致深度学习专家们绞尽脑汁想了许多方法来对抗这个问题,比如“Xavier and He Initialization”,比如我们要把weight随机初始化为如下的范围, sigmoid的另一个问题是它不是0均值的,Sigmoid函数的输出值恒大于0,这会导致模型训练的收敛速度变慢。举例来讲,对,如果所有均为正数或负数,那么其对的导数总是正数或负数,这会导致如下图红色箭头所示的阶梯式更新,这显然并非一个好的优化路径。深度学习往往需要大量时间来处理大量数据,模型的收敛速度是尤为重要的。所以,总体上来讲,训练深度学习网络尽量使用zero-centered数据 (可以经过数据预处理实现) 和zero-centered输出。 如今,sigmoid函数应用最广泛的在于其变种softmax在多元分类中,比如手写数字识别,经过卷积神经网络的处理,最后我们需要网络输出每个预测的概率值,最后预测为某一个数字,这里就需要用到softmax,以下是softmax的Keras代码,注意其中一个trick,e = K.exp(x – K.max(x, axis=axis, keepdims=True))这里每个分量减去最大值是为了减少计算量。 1234567891011121314151617181920212223 def softmax(x, axis=-1): """Softmax activation function. # Arguments x : Tensor. axis: Integer, axis along which the softmax normalization is applied. # Returns Tensor, …

神经网络术语大百科:优化函数、激活函数、损失函数、正则方法的简介 Read More »

理解TSNE算法

结合论文公式与几个python实现理解t-SNE算法。 t-SNE 是一种数据可视化工具,它可以将高维数据降维到2-3维以用于画图,局部相似性被这种embedding所保留。 t-SNE把原空间的数据点之间的距离转换为高斯分布概率,如果两点在高维空间距离越近,那么这个概率值越大。注意到高斯分布的这个标准差$sigma_i$ 对每个点都是不同的,这也是算法的创新点之一,因为理论上空间不同位置的点的密度是不同的,条件概率如此计算, $$p_{j|i} = frac{exp{(-d(boldsymbol{x}_i, boldsymbol{x}j) / (2 sigma_i^2)})}{sum{i neq k} exp{(-d(boldsymbol{x}_i, boldsymbol{x}k) / (2 sigma_i^2)})}, quad p{i|i} = 0,$$ 图中公式是理论方式,实际是先计算条件概率再用下面公式来产生联合分布, $$p_{ij} = frac{p_{j|i} + p_{i|j}}{2N}.$$ 其中 $sigma_i$ 将自动确定。这个过程可以通过设置算法的困惑性来影响。 用一个长尾分布(Student-t Distribution,简称为t分布)来表示 embed空间的相似性$$q_{ij} = frac{(1 + ||boldsymbol{y}_i – boldsymbol{y}j)||^2)^{-1}}{sum{k neq l} (1 + ||boldsymbol{y}_k – boldsymbol{y}_l)||^2)^{-1}},$$ 损失函数是两个分布之间的 Kullback-Leibler divergence(KL散度) $$KL(P|Q) = sum_{i neq …

理解TSNE算法 Read More »

logistic regression的公式手推相关

本文有关logistic regression的公式相关的手推,包括假说函数、极大似然估计以及梯度下降算法。 Hypothesis 首选我们要明确,logistic regression虽然叫“回归”,但是它却是用来做分类的,也是最最常用的分类机器学习算法。其假说模型为: $$h_{theta}(x) = g(theta ^T x)$$ 其中$g(z) = frac{1}{1+e^{-z}}$,so $$h_{theta}(x) = frac{1}{1+e^{-theta ^T x}}$$ 可以看到,函数主体和线性回归一样,都是样本与参数的内积,但是逻辑回归是用来打分的,也就是判断样本是正负例的概率,需要$g(z)$也就是sigmoid或者logistics函数来将这个内积映射到一个区间(0,1),所以实际上 $$h_{theta}(x) = p(y=1 | x;theta)$$ 以上只是得出了样本点是正例的概率,到底预测它是正例还是负例,我们还需要一个decision boundary,例如 $$h_{theta}(x) ge 0.5 rightarrow y=1 h_{theta}(x) lt 0.5 rightarrow y=0$$ 由于sigmoid函数的形状我们容易得到 $$theta ^T x ge 0 rightarrow y=1 theta ^T x lt 0 rightarrow y=0$$ 当然,decision boundary属于假说函数的一部分,不一定就是0.5. 极大似然估计 二元分类可以看做是一个伯努利分布,又叫做0-1分布,上面提到$$p(y=1 …

logistic regression的公式手推相关 Read More »

linear regression 的公式手推相关

本文有关多元linear Regression的损失函数从极大似然估计的角度的推导以及梯度下降算法。纯手打,^^ 损失函数 我们的模型为 $$h_{theta}(x) = theta_0 + theta_1x + theta_2 x^2 … = theta ^ TX$$ 似然函数为: $$y^i = theta ^ T x^i + epsilon ^ i$$ ,残差用$epsilon$表示,对于每一个样本点的残差$epsilon^i$,(注意以下标号中上标i表示第i个样本点),有: $$epsilon^i = y^i – h_{theta}(x^i) = y^i – theta ^ T x^i$$ 那么我们有假设所有的残差根据中心极限定理,其密度函数$p(epsilon^i)$符合均值为0,方差为$sigma^2$的高斯分布,即 $$p(epsilon^i) = frac{1}{sqrt {2pi} sigma} exp (-frac{(epsilon^i)^2}{2 sigma ^2}) = frac{1}{sqrt {2pi} sigma} …

linear regression 的公式手推相关 Read More »