Menu Sidebar
Menu

Integer Break

找规律:

 

Teuvo Kohonen和他的SOM

Teuvo Kohonen是一位芬兰的科学家, 介绍满街都是,可以自行google, 我就贴一个google scholar (https://scholar.google.com/scholar?hl=en&q=Teuvo+Kohonen&btnG=&as_sdt=1%2C16&as_sdtp=)

Kohonen博士为什么那么伟大呢? 让我慢慢道来, 在deep learning中, 无监督学习(unsupervised learning)一直是最受关注的焦点, 其中, 各种算法不计其数, 但是人工神经网络算法中, 最著名的算法, 就当属Kohonen博士开发的Kohonen SOM(Self-Organizing Maps), 这个著名有几个理由:

首先, Kohonen SOM是当今运用最广泛, 最贴近真实的神经激活方式的一种模拟人工神经网络, 这种真实体现在Kohonen博士对神经激活时, 状态的转换方程和激活后, 神经元之间关系的特殊理解. 举个栗子: 当你手指扎刺的时候, 神经传输到大脑, 你会感到疼痛, 但是当你脚趾扎刺的时候, 同样的疼痛, 你大脑反应会和手指不同, 因为神经元之间的固定初始位置,导致了神经冲动的传输有了衰减, 这种衰减可以被看做是learning rate的递减, 也可以想象成是一种regularization, 这种regularization是一种常态的regularization, 也就是说, 他并不是人为干预的衰减, 而是取决于神经元本身的固定属性(比如神经元之间的初始固定位置). 这也就是为什么Kohonen SOM是模仿人类神经冲动传导最好的人工神经网络.

其次, Kohonen SOM的neighborhood function, 在每次调用的时候, 更新当前随机选中的神经元,然后传导至所有的神经元. 这种全局更新的方法, 虽然很浪费时间, 但是保证了传导的准确性,举个栗子: 还是上面的例子, 虽然脚趾扎了个刺没有手指痛, 但是你不能不告诉大脑, 脚趾扎刺了. 当然, 有时候,真的因为这个神经冲动太小了, 脚上干裂了个小口子, 很多时候人自己感觉不到. 但是即使是很小的冲动, 也要更新所有的神经元, 这个思路是没错的.

displaymath1981

这个就是neighborhood function, a(t) 是个递减函数, 没啥大意思, 我就用了一个线性递减, ri和rc是两个神经元, theta(t) 是个衰减参数.

最后, Kohonen network的本质是由两个hidden layer的神经网络组成, 首先是一个Hamming network, input是低维vector的数组(n-tuple), 然后通过全联通网络, 返回互相直接的weight. 然后是一个maxnet network, maxnet的input是一个weight vector, 通过递归的方法, 返回最大weight神经元的index, 并且让其它的神经元同比衰减. 因为有maxnet的存在, 所以Kohonen SOM是Winner Take-All learning.

下面是一个用KNN实现的模拟解决TSP(Travelling Salesman Problem)的demo:

http://www.chenguanghe.com/project/tsp.html

Very Fast Reservoir Sampling by Erik Erlandson

今天正式的把这个抽样算法加到Apache Flink里了, 这个算法是Erik Erlandson在他的博客上公布的大概是迄今为止最快速的抽样算法的. 这个算法采用了流行的gap distribution的方法抽样, 有效的在减少cpu使用的情况下, 减少了内存的占用, 通过生成抽样之间的gap, 进行近似随机抽样.

在他的博客http://erikerlandson.github.io/blog/2015/08/17/the-reservoir-sampling-gap-distribution/中,  证明了抽样可以通过生成gap实现随机抽样, 大大减少了随机数的生成时间和占用的内存, 实际应用下, 可以大大增加整体系统的运行效率. 他的博客中, 有基于Bernoulli Distribution(https://github.com/apache/flink/blob/master/flink-java/src/main/java/org/apache/flink/api/java/sampling/BernoulliSampler.java)和Poisson Distribution(https://github.com/apache/flink/blob/master/flink-java/src/main/java/org/apache/flink/api/java/sampling/PoissonSampler.java)的两种实现, 在Apache Flink中, Bernoulli分布实现了非replacement的抽样, 而Poisson分布实现了replacement的抽样.

这个新的优化算法, 使用了几何分布(https://en.wikipedia.org/wiki/Geometric_distribution)的思想, 对于样品大小远远小于数据大小 (1000000倍以上)的情况下, 样品的抽样率近似于P = R/j, R是样品集合大小, j是当前数据的总数. 这个算法有两部分组成.

  1. 作者定义了一个阈值T, T=4R, R是样品集合的大小. 这里的4是由随机数的好坏确定的. 确定的方法很复杂. 如果数据量小于阈值T, 则使用传统的水塘抽样. 这里使用水塘抽样的原因是,
    1. 如果当前的数据量小, 则生成gap会大大影响抽样结果的分布. 因为这个算法的gap是通过累计分布最后达到均匀分布的, 少量的gap会产生极大的误差. 通过实验表明, KS-test下, 如果样品大小是100,数据量是100000, 那么与随机抽样比较, 误差远远超过了 KS-test的容忍值D.
    2. 在数据量小的情况下, 生成少量随机数并不会对系统产生太大的负担, 这种trade-off是可以接受的.
    3. 水塘抽样的分布和数据量无关, 所以即使抽样大小和数据量很接近, 比如R=100, j=10000, 也可以完美的进行随机抽样.
  2. 当数据超过T, 开始使用几何分布的抽样,我们用如下的方式计算gap:
    1. 首先算出p, 即理想的随机抽样下,  当前样品被抽中的概率, 显而易见, p = R/j
    2. 1-p 就是没有被抽中的概率, 那么生成u, 一个(0,1)的float, 做Math.log(u)/Math.log(1-p) <—这个公式的意义是, 在1-p的周围取gap.
  3. 然后通过省略gap个元素, 取下一个, 就可以实现随机抽样.

 

这个算法非常依赖于抽样大小和数据量之间的关系, 如果前者不是远远小于后者, 那么gap的大小会导致分布极度不均, 这种不均会使样品的误差很大.

下面是code:

https://github.com/gaoyike/flink/blob/81e0622b20d8bc969dec1555bd55d4230d9b38de/flink-java/src/main/java/org/apache/flink/api/java/sampling/VeryFastReservoirSampler.java

Kolmogorov–Smirnov测试

今天看Apache Flink是怎么测试streaming data的random sampling的. 然后看到里面测试代码(https://github.com/apache/flink/blob/master/flink-java/src/test/java/org/apache/flink/api/java/sampling/RandomSamplerTest.java)用的是Kolmogorov–Smirnov测试, 就查了一下相关的文献, 发现这个测试真是好用.

首先, 这个测试有很多的用法, 我使用它的原因主要是用于测试sampling是否是随机的. 在分布式系统下的sampling, 不能紧紧通过观察结果就判断当前抽样函数是否是随机抽样, 这个测试可以快速的测试一个expected result(期待函数的抽样结果)和一个actual result(当前函数的实际抽样结果), 通过勾画两个生成抽样的函数, 找到其中排序后, 每个误差最大值, 然后累计相加, 取生成一个p值, 通过对比p值和d值(d值为一个固定量), 可以直到当前抽样是否接近于随机抽样. p如果小于d,则是类随机抽样, 反之则否.

p的公式很复杂, 但是代码很易懂,这里上下代码:

然后d值是一个固定值, 取决于两个样本集合的大小:

注意, 这里的1.63不是个常数!, 是需要查表: 表在

https://www.webdepot.umontreal.ca/Usagers/angers/MonDepotPublic/STT3500H10/Critical_KS.pdf

其中a是critical value

CommerceHub面试

因为要去Albany, 所以要面那边的公司, 就投了这个公司.

开始扔了一个作业过来, 让我两天就交, 我这边又答辩,又工作, 真是累死人了. 作业很简单, 就是实现一个数据仓库, 需要注意一下多线程同步访问的问题. Code: https://github.com/gaoyike/CommerceHub

交了后三天收到电面, 然后就开始各种不靠谱. 面我的是一个2016的新SDE, 问的题是, 让你设计一个300 room的旅店, 然后就没了, 我从底层开始讲设计, 一直讲到分布式. 对面一直嗯嗯嗯, 结果问我一个问题: 你用什么IDE….  我突然就愣了, 我说我用intellij idea, 他说, 有意思, 你继续…然后我讲怎么rollback, 怎么做memcache, 然后又一阵嗯嗯嗯, 然后问我, 如果系统死机, 或者很慢, 你怎么办, 我说加cache, 然后做冗余, 我越来越觉得我面的不是SDE….最后一个问题彻底击垮了我: 如果用户一直说很慢, 你首先检查什么部分. 我说我先看log服务器, 然后dump内存. 看看是不是哪里有bug. 对面说, 有意思….我操 ‘有意思’…..

结果两天就收到说不fit……我也觉得真不fit..

CAS (Compare-and-Swap) 以及相关问题

CAS (Compare-and-Swap) 是一种硬件上, 实现非锁同步的一种方法. 这种方法比传统的blocked方法在硬件上实现, 效率高而且内存命中率高.

CAS实现的是一种先验的赋值方法, 即: 给出一个当前值v, 当想改变这个当前值的时候, 一个线程需要进行先验操作, 以当前线程为观察者, 查看改变对象是否是当前线程中期待的对象的值. 如果是才去改变它.  整个行为并非通过锁住线程实现的, 而在硬件上, 访问一个内存片段上的速度远远快于在更高层锁住当前线程的速度. 所以CAS被认为是比所要快速的实现原子化操作的方法之一.CAS 和 CAS2 被用在了Java自带的AtomicInteger, AtomicBoolean, AtomicReference上. 这些变量都是可以常常用作判断线程进行状态的flag. 传统的关键字volatile只保证了变量的visibility, 却缺乏了accessibility. 而使用Java自带的原子变量, 可以更有效的, 快速的解决并发的实际问题.

一个CAS的赋值操作, 由一个pair组成: (expectedCurrentValue, newValue). 当赋值实现了CAS的变量一个新值的时候, 先验当前值是否等于expectedCurrentValue, 如果等于, 则赋newValue, 否则返回CAS变量的值, 这样, 通过比较返回的值, 就可以知道是否赋值成功.

通过以上的CAS, 延伸出了ConcurrentStack (Treiber, 1986), Non-blocking Queue (Michael and Scoot, 1996) 等non-blocking的数据结构. 这些数据结构因为更贴近硬件操作并且是线程安全的, 所以在新的JVM中, 很多Concurrent的数据结构都使用了这种CAS的思想.

但是设计一个CAS的数据结构, 需要充分理解数据结构在并发下的state机制, 设置一个或者两个CAS的flag解决对个state之间转换, 来增加运行速度, 当CAS的变量过多, 并发下, 其实与blocked的数据结构比并没有太大优势.

Shortest Word Distance

 

Educational Codeforces Round 1 A. Tricky Sum

原题: http://codeforces.com/contest/598/problem/A


题目大意: 给一个数字n, 求1…n的合, 其中如果遇到2的倍数的数,要当负数处理.


分析: 直接求O(n) 会超时, 所以会想到求和公式.

通过观察可以发现, 给一个n, 我们可以:

  1. 求1到n的合, 用等差数列求和公式.
  2. 找到1到n中,有多少个2的倍数, 用对数公式, 这里注意, 1也是, 所以求完log后要用flooring求包含几个2的倍数后, 要加上1.
  3. 用公式Screen Shot 2016-02-27 at 11.59.02 AM
  4. 减去两杯的上面公式的结果就是答案了.

Apache Flink中实现的两种水塘抽样算法

因为Flink和我毕设有关, 所以这几天一直在看Flink的源码. Flink中实现了两种水塘抽样算法:

  1. Reservoir Sampler With Replacement https://ci.apache.org/projects/flink/flink-docs-master/api/java/org/apache/flink/api/java/sampling/ReservoirSamplerWithReplacement.html
  2. Reservoir Sampler Without Replacement https://ci.apache.org/projects/flink/flink-docs-master/api/java/org/apache/flink/api/java/sampling/ReservoirSamplerWithoutReplacement.html

对应的paper是:

  1. Optimal Random Sampling from Distributed Streams Revisited http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/tw11.pdf
  2. Random Sampling with a Reservoir http://www.cs.umd.edu/~samir/498/vitter.pdf

两种抽样的区别,(假设, k是已知的抽样数量):

  1. With Replacement是先取第一个样品, 然后做k个’复制'(这里的复制是对象是样品的value, 每个复制都有一个weight, 这个weight是随机生成的, 在Flink中, 用的是XOrShift随机数), 装满 大小为k的PriorityQueue中, 然后每次取下一个样品, 都做k个’复制’,然后如果’复制’的样品的weight大于当前PriorityQueue中, 就Remove PriorityQueue中队列顶端元素, 然后把当前’复制’放入PriorityQueue.
  2. Without Replacement是现取k个样品, 存入大小为k的PriorityQueue中, 每次取新的样品时, 算一个随机数, 如果这个随机数比当前PriorityQueue的队列顶端元素的weight值大,就Remove PriorityQueue中队列顶端元素, 然后放入当前元素.

值得一提的是, Flink中, 虽然在partition过程中实现了以上两种算法, 但是在reduce的过程, 并没有区别, 全部都用的是[2]算法, 这里我想,也许是为了保证reduce的速度, 减少随机数的计算时间, 而做的改变. 详情请见: https://github.com/eBay/Flink/blob/master/flink-java/src/main/java/org/apache/flink/api/java/sampling/DistributedRandomSampler.java

Recover Rotated Sorted Array

 

Newer Posts
Older Posts

书脊

倾城与倾国, 佳人难再得