二次规划(Quadratic Programming)问题是最基本的非线性规划问题,目标函数是二次函数,约束条件是线性等式或不等式。目前,已经出现了很多求解二次规划问题的算法,并且仍有很多学者在从事这方面的研究工作。

在机器学习中,我们知道QP可以用来解决SVM算法的最优解问题。二次规划问题的求解证明在此处暂不讨论。

二次规划的问题可以用数学公式(octave)描述:

1
2
3
4
5
6
7
8
 min 0.5 x'*H*x + x'*q
  x

    subject to

      A*x = b
      lb <= x <= ub
      A_lb <= A_in*x <= A_ub

相应的函数为:

  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB, A_LB, A_IN, A_UB)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (…, OPTIONS)

其中,H,q分别是目标函数化成标准形式后得到的实对称矩阵,列向量。求解的目标,x。A,b定义了线性约束。如果没有线性约束,A=[],b=[]。LB,UB分别是变量x的下界和上界,如果上界、下界没有约束,则LB=[],UB=[]。可以通过OPTIONS设置其它参数:比如:

‘MaxIter (default: 200)’

INFO表示算法的运行时信息。相应如下:

  • ‘solveiter’: 解的迭代数
  • ‘info’: 状态码。
  • info=0: 表示该问题是可行的,并且是convex问题。找到全局解。
  • info=1: 该问题是not convex的。找到局部解。
  • info=2: 该问题是not convex的,并且unbounded。
  • info=3: 迭代的最大次数
  • info=6: 该问题无解

示例:

编写程序:

H=[4,-4;-4,8];
Q=[-6;-3];
A=[1,1;4,1];
B=[3;9];
LB=zeros(2,1);
X0=[];
UB=[];
[X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB)

对应的输出为:

X =

   2.0000
   1.0000

OBJ = -11.000
INFO =

  scalar structure containing the fields:

    solveiter =  1
    info = 0

LAMBDA =

  -3.33333
   0.33333
   0.00000
   0.00000
   

这个标题起的有点大.

国内有许多做的还算不错的、各式各样的数据分析公司。如艾瑞,友盟等等之类的。在现在的大数据概念炒得火热的背后,其实它们的运作原理基本都差不多。

一切皆围绕数据去展开。那么数据是怎么来的呢?大致的数据来源基本上有这么几种,将分别说:

第一招:提供数据统计接口,有各种各样的API:各种编程语言的如JS/php/python/java、android/ios等等。当第三方的APP不希望单独花精力去维护一个数据分析平台时,那么很自然的,它们会选择这样的接口。这样数据自然地也被这些数据分析平台公司获取到了。那么有没有可能获取到该APP之外其它的一些信息呢?当然可以,由于android平台的安全性,这些公司一些接供的接口完全可以留下后门,当程序启动时,留下后台进程常驻(非360之类的工具也你真杀不掉)。ok,一个用户的其它移动非加密数据很有可能会被人家拿到了。ios则比较安全,8.0以上的版本基本无解。当然,还有一批越狱用户,这批用户的数据也是能拿到的。(别叫我流氓,这是行情潜规则)

第二招:还可以第三方合作。这一招也可以称为“空手套白狼”。中国的互联网环境竞争激烈,竞品太多。各种各样的公司很自然的会关注对手的情况。只要能和一家公司合作,那么很自然的,围绕对手想看这家公司的数据的问题,很自然地,可以和它相应的对手也开展这样的合作。这样,这个雪球也会越滚越大。

第三招:其它途径呢:花钱呗!付费招募。

第四招:还可以运营商(电信、移动、联通)合作。很自然地可以获取运营商根服务上的相关数据。比较某些特定用户访问某些站点的明文get数据(post无解)。

ok,数据有了。虽然可以拿到许多数据了。不过貌似不全,一家公司如果想让我做个分析研究肿么办。没关系,我们的“大数据”是吹出来的。(数据部分伪造,可以拿一些专业的互联网分析报告展开)

运营商 比例
移动 62.22%
联通 17.78%
电信 14.00%

我们接着看地域数据:

地区 比例
其它 18.00%
广东 13%
浙江 7%
北京 7%
江苏 6%
河南 6%
山东 5%
河北 5%
四川 4%
湖南 4%
湖北 3%
福建 3%
天津 3%
陕西 3%
辽宁 3%
上海 3%
山西 3%

还有操作系统的数据比例:

操作系统 比例
IOS 22%
Android 78%

ok,有了这些数据信息。那么我们就可以按比例去构建这样的大样本集。根据这样的大样本集去推演出真实的大致数据的分析即可。现在,就可以做各种各样的分析了:路径分析、个性化指标分析、转化率分析等等。

当然最重要的,是赚钱。有了一些行业内比较重量级的报告,那么就可以收费啦:一个app一个月就要10几w块钱。商业模式自然滚动起来啦。

由此看,这些数据分析公司中,抽样与统计占着相当重要的作用。

我们知道,在这个ugc的年代里,网络上各种各样支持文本输出的地方(比如:无意义的微博及评论、利用随机生成器注册id等等),经常出现一些无意义的乱语(英文叫:gibberish),比如“asdfqwer”。如何去识别它,是一个有意思的主题。

直觉跳出最简单的一种方式是,收集一本较全的英文字典,然后过滤一次,看看目标是否落在字典中。这是一种方式。准确率会有大幅提升,但是肯定还是会有一些case是难以解决的,比如:两个有意义的词刚好连在一起,却不在字典中。

另外我们再进一步思考一下,是否有什么算法进行训练,进而识别直接识别是否是乱语呢?可以考虑使用markov链模型。

对于一句话或短语来说:“hello buddy”,每个字母都与上下两个字母有关,这种关系可以通过2-gram来表示。比如:he, el, ll, lo, o[space], [space]b, …。

我们可以建立这样一个状态转移矩阵:

字母 a b c [space]
a Paa Pab Pac    
b Pba      
c Pca        
         
[space]          

在一个语料库, 我们会统计这些2-gram的频数,并将它们进行归一化。这样每个字母后的下一个字母出现都有一个概率分布(26个字母加空格)。

对于字母a,它的下一个输入为b的组成的2-gram的状态转换概率为:

为什么不是直接概率,而要使用log呢?

  • 由于字典很大,但一些词的出现概率会过小,计算机下溢(undeflow problem)将它们当成0来处理。
  • 我们最后要求的是整个“hello buddy”的概率,即:p = prob(he) * prob(el) * prob(ll) * … prob(dy)的概率,这在英文2gram的语言模型,而使用log可以利用log的性质:log(ab)=log(a)+log(b)
  • 最后,再通过e转换回正常概率即可.

如何判断是否是乱语?

我们可以收集一些乱语(bad),还有一些比较好的短语或语汇(good)。然后分别统计出对应bad以及good的平均转移概率。

平均转移概率=概率/转移次数

阀值的选取?

一般来说,good的平均转移概率,要比bad的大。可以选择平均:

thresh = (min(good_probs)+max(bad_probs))/2

  • 大于thresh,认为是good。
  • 小于等于thresh,认为是bad。

ok,利用这个模型,就可以识别字典之外的乱语了。如果你的训练语料很标准的话,那么相应的效果就会好很多。

参考:

word2vec的源码中,自带着另一个工具word2phrase,之前一直没有关注,可以用来发现短语. 代码写的很精练,不到300行,那么我们可以看一下,这不到300行的代码是如何实现短语发现的。

一、参数

  • train: 训练文件(已经分好词的文件)
  • debug: 是否开启调试模式 (debug=2,在训练时会有更多的输出信息)
  • output: 输出文件
  • min-count: 最小支持度,小于该值的词将不会被采用,缺省为5
  • threshold: 超过该得分,才形成短语,该值越高,形成的短语也会越少。(default:100)

二、词汇表

struct vocab_word {
    long long cn;    //
    char *word;    //
};

每个词汇由vacab_word构成,由这些词汇形成一个大的词汇表:vacab_hash。(最大条目:500M个)

三、模型训练 TrainModel()

内部原理很简单:是一个分词后2-gram的模型,统计出现频次. 本质是利用互信息(mi)计算内聚程度。(内部做了一些内存优化=>牺牲了一点点准确性,如果想更准,不如自己写map-reduce或spark)

公式为:

score = (pab - min_count) / (real)pa / (real)pb * (real)train_words;

可以简化为:

互信息只是简单的多个log2而已.

如果你有做过新词发现等经验,就知道这并不是一个比较优的方法,目前流行的做法是:互信息+min(左右邻字信息熵). 这里的字换成词即是短语发现.

Wang/Jenkins Hash算法在网上提到的也甚多,但是很少有人或有文章能系统地能将该算法的来龙去脉说明白。于是,我就充当了该苦工,幸好还是找到了一些东西,尝试着将该算法简单道来。

最早,Bob Jenkins提出了多个基于字符串通用Hash算法(搜Jenkins Hash就知道了),而Thomas Wang在Jenkins的基础上,针对固定整数输入做了相应的Hash算法。因而,其名字也就成了Wang/Jenkins Hash,其64位版本的 Hash算法如下:

uint64_t hash(uint64_t key) {
    key = (~key) + (key << 21); // key = (key << 21) - key - 1;
    key = key ^ (key >> 24);
    key = (key + (key << 3)) + (key << 8); // key * 265
    key = key ^ (key >> 14);
    key = (key + (key << 2)) + (key << 4); // key * 21
    key = key ^ (key >> 28);
    key = key + (key << 31);
    return key;
}

其关键特性是:

  • 1.雪崩性(更改输入参数的任何一位,就将引起输出有一半以上的位发生变化)
  • 2.可逆性(input ==> hash ==> inverse_hash ==> input)

其逆Hash函数为:

uint64_t inverse_hash(uint64_t key) {
    uint64_t tmp;

    // Invert key = key + (key << 31)
    tmp = key-(key<<31);
    key = key-(tmp<<31);

    // Invert key = key ^ (key >> 28)
    tmp = key^key>>28;
    key = key^tmp>>28;

    // Invert key *= 21
    key *= 14933078535860113213u;

    // Invert key = key ^ (key >> 14)
    tmp = key^key>>14;
    tmp = key^tmp>>14;
    tmp = key^tmp>>14;
    key = key^tmp>>14;

    // Invert key *= 265
    key *= 15244667743933553977u;

    // Invert key = key ^ (key >> 24)
    tmp = key^key>>24;
    key = key^tmp>>24;

    // Invert key = (~key) + (key << 21)
    tmp = ~key;
    tmp = ~(key-(tmp<<21));
    tmp = ~(key-(tmp<<21));
    key = ~(key-(tmp<<21));

    return key;
}

由上述的算法实现可知,原始的hash算法过程是非常快的,而其逆Hash算法则比较慢一些。

参考: