在做这个ocr项目的时候，首先想到的是用一些开源的项目，通过比较，只有google对中文的支持度算是有好的，通过测试，它的识别度也还是可以。但是会面临到好几个问题,可以察觉到2个主要问题

• 中文字相比英语字符，识别速度低了好几倍
• 中文字符有时候会整行出现大面积的错误，而且非常离谱，甚至有乱码的出现。

通过这篇Adapting the Tesseract Open Source OCR Engine for Multilingual OCR的论文里看，这个项目的框架为了能让各种不同语言的文字进行识别，把中文文字识别以一行句子为切分单位，以文字部首为最基本的识别单位(使用了connected components analysis切分所有不连在一起的部首(也可以用项目的图形debug界面http://code.google.com/p/tesseract-ocr/wiki/ViewerDebugging，能看到中文字是给切分开的)。识别之后，通过best first search对中文字符进行匹配。结果就是，文字识别速度较慢，大部分计算的开销用在了匹配的时候。由于用到了best-first 不能保证全局最优解，往往图像稍微有一些噪音就会会出现大面积的错误的情况，一开始的几个字也许和原本字符相似度还可以，句子后半部的字符就不是了。

这个方法完全是按英语的识别方法，通过以英语单词为基本匹配单位，匹配每个字母成为最有可能的单词。这样的一个方法可以让语言的semantic运用到识别了，大大提高的每个单词的识别度。但是这个方法的本身是特别适合语英语，每个单词的长度不是很大，单词和单词之间有一个明显的空格，可以很好的切分。 但是运用到中文字符识别的时候确出现了以下几个问题:

• 以google那些人的看法，中文字符之间空隙是很小的，甚至很多时候是字和字之间是连在一起。其实印刷体的中文字符之间的空隙还是很明显的。
• 中文句子长度一般都很长，往往匹配的时候需要很多开销
• 中文识别的时候，我试过，就算把文本字符之间的空隙分的很大，还是会把一个字的之间的部首分开，在匹配的时候不会记住字符之间的空隙。

最近在做一个中文ocr，感觉是个不可完成任务。不管怎么样还是得试试。 首先要做的就是获得训练数据。中文的数据不比英文，量大而且没有地方下载，唯一能做的就是自己生成，在网上找了写函数自己改改就成了下面的脚本了

首先是一个中文字符集编码的生成函数:

    def generate_ch():

        #Function which generate all chinese gb2312 characters 
        
        body = random.randint(0xA, 0xA)
        tail = random.randint(0, 0xF)
        chars = []
        
        heads = range(0xB0, 0xF8)
        bodys = range(0xA, 0xF+1)
        tails = range(0, 0xF+1)
        for head in heads:
            for body in bodys:
                for tail in tails:
                    val = ( head << 0x8 ) | (body << 0x4 ) | tail
                    #print "%x"%head,"%x"%body,"%x"%tail,"%x"%val
                    str = "%x" % val
                    if str.endswith("ff") or str.endswith("a0"):
                        continue
                    #special cases no characters with these codecs
                    if str == "d7fa" or str == "d7fb" or str == "d7fc" or str == "d7fd" or str == "d7fe" or str == "d7ff" :
                        continue
                    chars.append(str.decode('hex').decode('gb2312'))
        return chars

如果要生成中文字符图片，有很多办法，这里我用pygame打印每个字符

    # -*- coding: utf-8 -*-
    import pygame
     pygame.init()
    font = pygame.font.Font(os.path.join("fonts", "simfang.ttf"), 64)
    rtext = font.render("".join("b1a1".decode('hex').decode('gb2312')), True, (0, 0, 0), (255, 255, 255))
    pygame.image.save(rtext,"t.jpg" )

然后中文字符图片就出来了

要打印字符，需要至少一个ttf,也就是字体的文件。这里是用的simfang.ttf

中文字ocr是个比较讨厌的事情，主要是因为中文字繁多，光简体字就有6000多个以上，虽然其中大部分简体字是不常用的。对于这么一个这么大的，种类繁多的数据集，在分类的时候真心头疼，看了很多paper后，发现现在的state of the art是基于gabor filters，通过这个过滤器，对一个中文字的不同角度的比划进行过滤，然后在每个subregion里的每个角度的比划进行统计之后生成一个histogram，和bag of words一样，histogram可以用来对每个字进行分类或者用来寻找最近邻。

gabor filters 是个复杂的东西，网上的方程各种各样的，数学不好的小白就很难明白。在网上找了好多现成的函数之后，最后找到一个能用的matlab函数:

function gb=gabor_fn(rows,cols,sigma,theta,lambda,psi,gamma)
     
    sigma_x = sigma;
    sigma_y = sigma/gamma;
     
    % Bounding box
    nstds = 3;
    xmax = max(abs(nstds*sigma_x*cos(theta)),abs(nstds*sigma_y*sin(theta)));
    xmax = ceil(max(1,xmax));
    ymax = max(abs(nstds*sigma_x*sin(theta)),abs(nstds*sigma_y*cos(theta)));
    ymax = ceil(max(1,ymax));
    xmin = -xmax; ymin = -ymax;

    [x,y] = meshgrid(xmin:xmax,ymin:ymax);
    %[x,y] = meshgrid(-rows/2:rows/2-1,-cols/2:cols/2-1);

    % Rotation 
    x_theta=x*cos(theta)+y*sin(theta);
    y_theta=-x*sin(theta)+y*cos(theta);
    gb= exp(-.5*(x_theta.^2/sigma_x^2+y_theta.^2/sigma_y^2)).*cos(2*pi/lambda*x_theta+psi);

rows和cols是图片的大小, sigma是gauss的那个sigma，越大的话周围的pixels影响越大,theta要提取的比划的角度，lambda这个貌似是什么的长度(不明白啊),psi这里没用,gamma生成y_sigma。

通过改变theta这个角度值可以获得不同角度比划的信息。

I = imread('~/Desktop/11.png')
J = rgb2gray(I);
K = imresize(J,[64,64])
gb=gabor_fn(64,64,1.2,theta,5,0,1)

这里的theta分别是pi/2, pi/4, pi和 3*pi/4 这个四个值，他们可以分别抓取中文字比划的那8个方向。 下面就是这个函数能产生的效果

冲上面的图就能看出这个过滤器的威力，过滤图片之后，我们可以对每个图片其中某个的区域的点阵进行统计，这样生成一个histogram，通过histogram可以有效的对每个字进行区分。

在我的试验中，我用了16个1616大小的方格作为第一次层histogram数组，然后在它的上面又叠加了9个1616的数组，总共是一个长(16+9)*4 = 100的数组。这么长的数组以后还的进行pca或者lda什么。实验在进行中。。。

期末的另外一个大作业是对一个数据进行分类和研究。数据集是和保险行业相关的。94%的negative cases和6%的positive cases。 如此不平衡的数据往往你能通过使用最简单的分类器zeroR来获得较高的准确率(94%). 在实际应用中，这样是非常不靠谱的。因为往往那些positive cases的忽略产生的影响是比较大的([FRR]的惩罚)。

同样，直接使用不平衡数据会带来另外一个影响是: 往往分类器模型追求的是高准确率，自然而然的将会给高概率的类影响，结果将会是一个和zeroR一样的分类器。在不同的测试之后，发现这个现象非常明显。

那怎么样可以让分类器”学会一点实在的东西”, 而不是只追求”富贵(高准确率)”，或者两者皆之呢。有一种方法就是通过resampling，人为的让训练数据集的分布更平衡一些，通过这样的方法，训练出来的模型会更靠谱一些。但是同样的，这个模型在实际环境中的预测结果不会是很好的，因为我们改变了分布，不同分布下的同一个模型会导致结果的不同。怎么解决这类问题呢? 通常需要一个calibration，让模型试用于实际环境中的数据分布。在这篇Dealing with Unknown Priors in Supervised Classification作者解释了怎么通过贝叶斯概率来做这个校准。在试验中，这样的校准对我的实验结果没有什么影响，主要的原因是像下面所谈到的，我的模型的结果是一个概率值，我需要选出概率最高的那些，而这个校准是Monotonic的，对概率排序不产生影响。如果是组合不同的分类器的话，这个办法应该还是有用的。另外我还觉得，就算有组合不同的分类器，如果实际环境中数据分布差值在这么大结果也会一样不理想。

期末的这个作业其实是让我们训练出某个模型，并让模型的结果是一个positive cases的概率值，我们需要在测试数据中，选出10%的数据，而这些数据中的positive cases的比重要尽可能的多。这里我介绍两个办法。

Random Forest

比较正规，完全是跟着老师说的也就是上面说的那些办法来做。 碰到这样的数据集，往往分类器倒不是最重要的部分。很多preprocessing将会是一样的重要。数据拿来首先要自己分析一下哪些attributes是不需要的，一般会用information gain来看一些，某些gain特别高的也不一定是好feature，也许这些feature是些”事后”feature，对预测没有任何帮助。然后呢，会用一些dimension reduction的方法比如PCA，LDA，mRMR(这里我用的)对数据进行降维。

降为之后，使用了upsampling 对训练数据集的分布进行更改，upsampling是把少的那部分复制起来，听说结果要比downsampling好。 然后呢，就是不同的测每个模型。最后我的模型是一个cost-sensitive + random forest.

这里是我使用WEKA做分析的流程图:

我的最终结果是在10%的数据里，有12.56%的positive cases。下面是precision-recall的结果:

SVM

在做这个作业的事后在resys发过帖子问过，幸运的是有个浙江大学的牛人和我专门讨论了这个问题，当时他给了我一个方法就是通过SVM来做模型，这里的变化就是，通过soft margin，对每个类的给出不同的惩罚值C，这样的话，多数的那类的C会很小，而烧的那类C值会很大。当时一说就觉得非常靠谱，但是项目已经快deadline 也就没事间测试了。

C的方程:

$$C\sum_{i=1}^l\epsilon_i = C_+\sum_{i\in I_+}\xi_i + C_-\sum_{i\in I_-}\xi_i$$

巧的是，班上有个专门研究SVM牛人用这个方法做了，貌似用的是libsvm，也许libsvm能够对每个c值进行修改吧。结果是16%的positive cases！灰常之高，更证明了soft-margin 的svm对这类问题的好处。 而且用SVM有个好处就是你不用使用什么resampling了，反正对svm的影响不大，因为svm 是基于support vectors做判断的。

音乐分类其实很早就有人做了，这些天在kaggle上有个Million Song Dataset Challenge 非常火，上面有大量的数据可以让选手们通过底层，高层的和基于用户协作推荐的等等手段来对歌曲进行推荐. 这里我做的音乐声音分类是底层的, 而且我觉得一般的音乐文件要处理的东西太多了，节奏，速度什么的，在这里我只对4种乐器的声音进行分类: 钢琴，吉他，口琴，小提琴。

一般底层的声音，语音分类，speech recognition 使用无外乎Mel-frequency cepstrum 和 lpc analysis。 第二是个比较老的方法，而MFCC是我所用到的。可以把MFCCs对于好分类和识别的家伙们来说可以理解为对一段声音文件的descriptor，重点是这个descriptor非常discriminant. 在实验中，使用了matlab的voicebox里的melcepst函数，可以生成长度为12的数组，每个数组一般是一很小段声音的description，由于取样和设置的问题，MFCC所包含的声音长度是不一样的，在我的实验中，差不多连续1000个MFCC差不多是6秒钟的音频。 那4种声音来源分别是verycd上名家solo哈，不过要吐槽的是找了好多title是solo的，但是其实是是几种乐器和音的。每个类里取了6首左右的歌曲(20分钟左右)作为训练数据，提取出500k的MFCCs。

在实验中我使用了两个方法, 一种是在学校里老师讲的”常规”方法, 还有一种是用于图像分类的。总觉得在做底层分类的时候，图像识别和声音识别的步骤是差不多的。

• Binary-split, SVM
• Naive Bayes Nearest Neighbor

Binary-split + SVM

500k+的数据直接用来使用的话那就太夸张了，Binary-split+SVM这方法简单的来说是通过binary-split把500k的MFCC压缩成1000到2000个clusters，通过binary-split类似的数据会在一个小组里面。这种clustering算法里最有名的是k-means，不过k-means 速度实在是太悲剧了，虽然压缩损耗度要比binary-split少一些。

通过binary-split数据给压缩到少许clusters里，这所有的clusters其实就是所谓的codebook。codebook在通讯里面非常用,往往在数据通讯里，特别是声音传输中，需要用到codebook把传输数据进行压缩，在接受点的那一端，通过decode来还原原始数据。像一般的手机通讯就是用到这个概念，所以说很多时候人们发现电话里的声音总不是特别像某个人，原因就是因为声音信息在传输的时候多少给损耗掉了。在实验中，每个声音段(通常是1000个MFCCs也就是6秒左右的声音)用codebook可以生成一个一个histogram: 把每个MFCC在binary-split树里跑一下，找到最相近的cluster，通过统计所有cluster里一个声音段落里不同的MFCCs所出现的次数来生成Histogram。

每个声音段所产生的histrogram就是所要用到用来训练SVM的数据。这里的svm是one-vs-all，所以说将有4个svm会训练出来，每个svm会应对每个类，而每个svm会长生出一个概率值，是只一个声音段是它所对应类的可能性。在测试中往往选取最高的可能性作为音频的class。

在测试中，以上的步骤都差不多，只是，不需要生成codebook，直接使用了就可以。这里要说的是，测试的音频长度不一定需要和训练的音频长度一样，只要每次生成的histogram是归一化的就行了。

测试的时候每个类有20个case，从结果上来看，钢琴和吉他的识别不是很高，而且他们彼此有着很高互指。其实很大的原因是:当我们用codebook的时候，会对数据进行压缩，很多时候这个压缩会让比较discriminant的数据丢失。在这个实验中，钢琴和吉他的声音是比较相似的。

上面这个图是个histogram的分布图，通过随机选取每个类里的某一个训练的音频段生成的分布图，从途中可以看出，实际上通过codebook之后，吉他和钢琴的数据分布是非常耦合和相似的。所以，实验中对钢琴和吉他的分别度不高也有了依据。

Naive Bayes Nearest Neighbor(NBNN)

实际上，在图像识别中，很多时候也是运用到了上面所讲的方法，通过codebook对图像所提取的key-points进行clusterization，之后通过第二层的分类器把codebook产出的histogram数组进行分类。所以我觉得NBNN应该也能运用到声音分类中来。 NBNN是最近以篇叫In Defense of Nearest-Neighbor Based Image Classification的论文中看到的，该论文着重指出，codebook对数据损耗在无训练模型中的影响。 NBNN就是无训练模型(也叫no parametric?)， 优点就是不需要训练。。。还有一个优点是在分类里，NBNN用的是image-class距离，而不是image-image距离，这样的话，intravariance很高的类对它的影响不大。

在论文中如果我们使用的邻近邻居是1的话，算法简化成以下:

1. Compute MFCCs $d_i,...,d_n$ of the query audio
2. $\forall d_i \forall C$ compute the NN of $d_i$ in $C$: $NN_C(d_i)$
3. $C = arg min_c\sum_{i=1}^n$ $\left \|d_i - NN_c(d_i)\right \|^2$

还有一点要说的是，在寻找最近邻居的时候，计算需求是相当高的，在原文里，作者用的是kd-tree,这样的能很快的找到最近的邻居。在这个实验的时候我用的scipy里kd-tree效率非常慢，后来才发现原来原作者是用的approximate kd-tree.

这个算法虽然简单，但是结果是惊人的不错: 使用所有的训练数据里的mfcc，每个测试音频有2000个MFCC，测试过程相当慢(好几个小时,如果使用approximate kd-tree的话应该能快好几个数量级)

从数据集里随机在每个类中获取500个MFCC，每个音频400个MFCC

最后是从每个类的训练数据中随机抽取30个MFCCs，每200个MFCC做音频测试数据的长度,测试数据是每个类40个，总使用的时间几秒而已

结果很显然易见，NBNN在声音分类方面还是很厉害的。更证明了声音分类和图像分类的相似之处。 以后有时间的话，可以试试以下的东西:

• 可以在NBNN里不随机选取MFCC，而是选取更有代表性的
• 使用 approximate kd-tree
• 用图像分类里的 random forest算法试试看

最后，感谢电驴，感谢python，感谢scipy，感谢voicebox 让哥在3天里搞定大作业。感谢尼玛操蛋的htk，要不是因为htk(本来好想做也语音编程系统的的)出不来结果我也不会换做这个来当speech recognition的大作业。

Grammatical evolution 算法是一个遗传算法的分支，主要是通过遗传算法中的operators:crossover(杂交), mutation(变异)来查找最有解，而在grammatical evolution里最优解是以个方程或者一系列的代码块(executable program)。优秀的代码块往往能对目标解有很好的靠近。这个学术界的代表人物就要算是John Koza, 他的Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems也是一本很好的reference。

GE算法主要通过BNF语法对一个search space进行限制，这样的话能很好的对那些破坏语法规则的代码块进行剔除，大大减少了搜索空间的范围。在实际运用中，有两个主要概念: “genotype”和”phenotype。也就是基因和外貌，一个很好的例子就是你的外貌(眼睛颜色)取决语你的基因(DNA)，而通常基因和外貌是两层不一样的东西。 在GE算法里，phenotype就是我们所要的程序，而genotype是一串整数。通过这串整数的数值和他们所在的环境(也就是所有的语法规则)产生出来一系列的rules(代码)，最终这一连串的代码的就结果就是我们所在找的代码块。通过检验代码块的fitness(通常在找一个方程的时候会先行计算要找方程对于某些特定数值的预计结果，然后通过代码块和预定数值的数值结果差的大小来判断相似度, 变相的监督学习？)来决定他的’繁殖’能力，这样我们又回到了GA算法里的crossover和mutation。也就是说，在GE算法里，每个代码块是一个人口，通过不断的对一大群人口不停的结合和转变找到最优质的答案。

有必要讲一下genotype转化到phenotype这一过程，在这篇Neill的文章Grammatical evolution中有很好的解释。

同个这个idea很多GE算法的变种也相继出来了，Attribute Grammar Evolution和Christiansen Grammar Evolution: grammatical evolution with semantics(我老师写的¬¬) 都是对GE的改进，通过对语法上下文和语义的限制和检查加快了搜索的速度和搜索的结果。不过太多的限制也会是算法的效能下降哦。

原文在http://kqueue.org/blog/2012/01/05/hello-world/。通过MathJax, 把latex打在网页上。 首先是在source/_includes/custom/head.html添加以下代码:

<script type="text/javascript"
        src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

在_config.yml 把markdown的引擎从rdiscount换成kramdown, 当然如果没有装的话装一下gem install kramdown。从现在开始就能通过 $$.. $$($$在单独的一行中，代码上下各留一空行)写latex啦 原文作者说好像会出现一些杂乱字符，你可以在source/_includes/custom/head.html添加以下代码来解决:

<script type="text/x-mathjax-config">
MathJax.Hub.Register.StartupHook("TeX Jax Ready",function () {
          MathJax.InputJax.TeX.prefilterHooks.Add(function (data) {
                  data.math = data.math.replace(/^\s*<!\[CDATA\[\s*((?:\n|.)*)\s*\]\]>\s*$/m,"$1");
                    });
          });
</script>

这里是一个例子Multivariate normal distribution:

$$
f_x(x_1,...,x_k)=\frac{1}{(2\pi)^{k\/2}|\Sigma|^{1\/2}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))
$$

要让matlab把数据倒入倒python里很简单, 我试过直接保存倒2进制的文件里，但是通过用scipy.io.loadmat 这个方法读取的时候会报错。结果职能用粗糙的办法了，把文件存放在一个可读文件里:

save -ascii "your.txt" yourMatrix 

在python里读取的时候用genfromtxt:

from numpy import genfromtxt
m = genfromtxt('your.txt') 

想通过python把array寸在一个matlab能读取的文件里的方法也很简单:

from numpy import savetxt
savetxt("your.txt", yourArray)

在matlab里直接load就行了:

load -ascii your.txt newMatrixName

最近在学校的n电脑上跑数据，很多时候一个run要耗费好几个小时，ssh不知道为什么连一会后会自动断开，跑到一半程序就悲剧了。 在网上找了一会 发现一个神器:nohup, 用法超级简单: nohup comand 这样你的程序会后台运行，并且就算你ssh断开后都能继续跑着。nohup还提供给你一个nohup.log 你程序所有的output都会放在那个log里。

另外一个碰到的问题是，很多时候离开ssh后我都不知道程序跑完没，这里我用python搞了一个小程序:基于smtp发电子邮件。首先我用python的subprocess去跑数据程序，然后当数据程序跑完后发送一个邮件到我的邮箱里，这样我就能差不多“实时”的知道程序运行的情况了。

这是我发送邮件的小函数：

#!/usr/bin/env python
# -*- coding: utf8 -*-
import smtplib
from email.mime.text import MIMEText

server = "smtp.gmail.com:587"
user_account="pythonsmtpalert@gmail.com"
password="密码"
mailto_list=["我的目标邮箱.com"]
def send_mail(to_list,sub,content):
        me="python stmp alert " +"<pythonsmtpalert@gmail.com>"
        msg = MIMEText(content)
        msg['Subject'] = sub
        msg['From'] = me
        msg['To'] = ";".join(mailto_list)
        try:
            s = smtplib.SMTP(server)
            s.starttls()  
            s.login(user_account,password)
            s.sendmail(me, to_list, msg.as_string())
            s.close()
            return True
        except Exception, e:
            print str(e)
            return False

if __name__ == '__main__':
    if send_mail(mailto_list,"Process accomplished","t你好ake a look the results!"):
        print "发送成功"
    else:
        print "发送失败"

server: 服务器地址 user_account:你的邮箱帐号 password:邮箱密码 mailto_list:目标邮箱 这里你的邮箱要和你服务器地址是一个牌子的，我这里用的是gmail，换别的邮箱的话得用别得邮箱得smtp服务器

最近看了一篇名叫Categorizing nine visual classes using local appearance descriptors 的论文，相当受启发，该论文以Information retrieval里bag of words(以单词的出现的次数的矩阵来概括某篇文章)为基础,通过对图像所有的interest points用harris affine detector来 产生一个bag of keypoints(用sift descriptor描述每个keypoints) 对图像进行描述。

不过一套训练数据里所有的keypoints的数量是相当大的，这里论文的另外一个看点就是用k-means对所有的keypoints进行归类，每个cluster之中保含类似的keypoints，而这时，每个图像里的keypoints 在每个cluster里的出现次数将会给统计并且生成一个bag of keypoints.

通过naive bayes或svm 进行训练，在论文里分类的结果还不错. 有几个我觉得也许可以改进的地方:

1 在原论文里：每种图像生成的keypoints的数量是不同的，为了避免bias作者在clustering的时候在每类图像里随机选了5000个keypoints，我觉得如果选的时候可以把stop words的概念加进去，每个class都有的keypoint去除掉的话应该能增加discrimination.

2 在测试的时候我觉得如果一个keypoint离2个以上的cluster距离都差不多的话，应该可以把它当作IR里的‘生词’一样忽略掉. 感觉以上这两点应该能对算法有一个改进，以后有空得研究下。

还有在论文里作者在做测试的时候没有使用no-object的图像进行训练和测试，我觉得如果加进去的话，结果应该会差一个档次。

参考: http://en.wikipedia.org/wiki/Bag_of_words_model_in_computer_vision.

这里是作者介绍算法的视频,解释的相当不错，不过好像视频后半部分看不了。