READING-2017-3

记录一下通读或者大致浏览过的论文,博文,或者书.一者做个备忘,二者督促自己把东西看得差不多再放下.

1. Spatially-sparse convolutional neural networks

link: https://arxiv.org/abs/1409.6070

许多数据拥有稀疏性,比如使用很细的笔在白纸上写的数字.

本文介绍了一种利用数据稀疏性加速神经网络训练的方法.

提到了一种在线文字识别的建模方法(同时考虑笔的位置和运动方向).

where I found it:
http://blog.kaggle.com/2015/01/02/cifar-10-competition-winners-interviews-with-dr-ben-graham-phil-culliton-zygmunt-zajac/

这篇文章包含一些CNN进行图像识别的基本方法.

2. kaggle ensembling guide

link: http://mlwave.com/kaggle-ensembling-guide/

介绍了集成模型在kaggle中的应用,有很多实例和代码.

3. Latent Semantic Analysis

link: http://www.engr.uvic.ca/~seng474/svd.pdf

介绍了特征值分解,奇异值分解,以及LSI的基本原理.

4. RELAXATION METHODS FOR MINIMUM COST FLOW(not finished yet)

link: https://pdfs.semanticscholar.org/a719/4aaa5b1958dee21aad7de1febf3cafaec0d7.pdf

最小费用流松弛算法的论文.

最开始是参考那本神书 network flow, 但是感觉似乎有些细节没说清楚,感觉还是要二者结合一下...

计划把网络流(主要是费用流)的学习成果做成一个开源库.

松弛算法搞定之后肯定就要学网络单纯形了.

5. Viola and Jones face detection algorithm

link: https://www.slideshare.net/wolf/avihu-efrats-viola-and-jones-face-detection-slides

著名的实时人脸检测算法.

6. Mining High-Speed Data Streams

link: http://homes.cs.washington.edu/~pedrod/papers/kdd00.pdf

在线决策树构建算法Hoeffding tree.
基于Hoeffding bound, 在一定的采样数量下,可以保证以一定的概率在某个节点得到与离线算法相同的分裂结果.
VFDT是它的一个实现.

学习笔记

fractional cascading

问题:有k个长度分别为L1, L2, L3 … Lk的数组,每次询问一个数q,求每个数组里大于等于q的最小的数。

如果只有一个数组,那么只需要对数组排序,然后二分即可,复杂度O(L)。

对于k个数组的情况,直接二分k次。设总元素个数是n, 最坏复杂度就是O(k*log(n / k)),此时每个数组元素个数相等。

fractional cascading(以下简称FC)是用来处理这种的询问的算法,单次询问时间复杂度是O(k + log n),空间复杂度O(n)。


FC的本质思想实际上类似线段树(或者排序二叉树),在一个数组中利用线段树查询需要O(L)的空间和O(logL)的时间。线段树的每个节点只要存储子树的中位数即可。将这个思路扩展到多个数组就可以得到FC。


对于如下数据

L1 = 24, 64, 65, 80, 93
L2 = 23, 25, 26
L3 = 13, 44, 62, 66
L4 = 11, 35, 46, 79, 81

FC构造了一个表:

M1 = 24[0, 1], 25[1, 1], 35[1, 3], 64[1, 5], 65[2, 5], 79[3, 5], 80[3, 6], 93[4, 6]
M2 = 23[0, 1], 25[1, 1], 26[2, 1], 35[3, 1], 62[3, 3], 79[3, 5]
M3 = 13[0, 1], 35[1, 1], 44[1, 2], 62[2, 3], 66[3, 3], 79[4, 3]
M4 = 11[0, 0], 35[1, 0], 46[2, 0], 79[3, 0], 81[4, 0] 

Mi包含Li的所有元素,以及所有Mi+1下标为奇数(下标从零开始)的元素。

对于Mi的每个元素,需要存两个值,第一个是在Li查询该元素得到的位置,第二个是在Mi+1中查询该元素得到的位置。

在上表查询40的过程如下:

  1. 首先在M1二分,得到元素64,根据64记录的第一个值得到L1中的位置是1.
  2. 根据64记录的第二个值,在M2的位置是79,在L2的3(表尾的话需要特殊处理一下),同时还需要考虑前一个数(62)的情况,因为查询的数40在L1查询的结果只可能是这两个数在L1查询得到的位置。此时62符合情况。
  3. 到了M3的3,重复上面的过程,找到62。与前一个数44比较,答案是44.
  4. 在M4找到46

时间复杂度只需要在M1做一次二分,然后在后面的k - 1个表里都是O(1)的。

空间复杂度,由于每个表的元素在上一层至少会减半(相同元素需要合并),所以每个表Li的元素占用的空间是Li + Li / 2 + Li / 4 …..,显然这个求和结果是O(Li)的。查询的过程与线段树非常相似,只是存储方式有所不同。

reference

wiki

算法

Learning gprof

使用gprof进行性能分析非常方便,只需要在编译的时候增加一个-gp选项即可。

编译命令如下

g++ -Wall -pg test_gprof.c -o test_gprof

生成运行信息

gprof -b test_gprof gmon.out

加了-b选项可以去掉自带的说明(非常长。。。)

输出的东西可以重定向到文件里看,比如

gprof -b test_gprof gmon.out > out

为了看懂输出信息我改了一下代码,最后是这样的:

//test_gprof.c
#include<stdio.h>
#include<math.h>
void func3() {
    for(int i = 0; i < 1e8; i++);
    printf("\n Inside func3\n");
    return;
}
void func4() {
    for(int i = 0; i < 1e8; i++);
    func3();
    return;
}
void new_func1(void)
{
    printf("\n Inside new_func1()\n");
    int i = 0;
    func3();
    for(;i<1e8;i++);
    func3();
    func4();
    return;
}
void func1(void)
{
    printf("\n Inside func1 \n");
    int i = 0;

    for(;i<1e8;i++);
    new_func1();

    return;
}
void func5(int x) {
    if(x > 1e4) return;
    for(int i = 0; i < 1e4; i++) 
        int y = sqrt((double)x);
    func5(x + 1);
}
static void func2(void)
{
    printf("\n Inside func2 \n");
    int i = 0;

    for(;i<1e8;i++);
    func3();
    func5(0);
    return;
}

int main(void)
{
    printf("\n Inside main()\n");
    int i = 0;

    for(;i<1e8;i++);
    func1();
    func2();

    return 0;
}

这个里面相比reference增加了一些东西,比如递归调用,一个函数在多处被调用。。。

输出如下:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 38.65      0.90     0.90        4     0.22     0.22  func3()
 12.60      1.19     0.29                             main
 10.86      1.44     0.25        1     0.25     0.25  func5(int)
  9.99      1.67     0.23        1     0.23     1.35  func1()
  9.56      1.89     0.22        1     0.22     0.45  func4()
  9.56      2.12     0.22        1     0.22     0.70  func2()
  9.56      2.34     0.22        1     0.22     1.12  new_func1()


            Call graph


granularity: each sample hit covers 2 byte(s) for 0.43% of 2.34 seconds

index % time    self  children    called     name
                                                 <spontaneous>
[1]    100.0    0.29    2.05                 main [1]
                0.23    1.12       1/1           func1() [2]
                0.22    0.48       1/1           func2() [5]
-----------------------------------------------
                0.23    1.12       1/1           main [1]
[2]     57.7    0.23    1.12       1         func1() [2]
                0.22    0.89       1/1           new_func1() [3]
-----------------------------------------------
                0.22    0.89       1/1           func1() [2]
[3]     47.7    0.22    0.89       1         new_func1() [3]
                0.45    0.00       2/4           func3() [4]
                0.22    0.22       1/1           func4() [6]
-----------------------------------------------
                0.22    0.00       1/4           func4() [6]
                0.22    0.00       1/4           func2() [5]
                0.45    0.00       2/4           new_func1() [3]
[4]     38.4    0.90    0.00       4         func3() [4]
-----------------------------------------------
                0.22    0.48       1/1           main [1]
[5]     29.8    0.22    0.48       1         func2() [5]
                0.25    0.00       1/1           func5(int) [7]
                0.22    0.00       1/4           func3() [4]
-----------------------------------------------
                0.22    0.22       1/1           new_func1() [3]
[6]     19.1    0.22    0.22       1         func4() [6]
                0.22    0.00       1/4           func3() [4]
-----------------------------------------------
                               10001             func5(int) [7]
                0.25    0.00       1/1           func2() [5]
[7]     10.8    0.25    0.00       1+10001   func5(int) [7]
                               10001             func5(int) [7]
-----------------------------------------------


Index by function name

   [2] func1()                 [7] func5(int)              [1] main
   [4] func3()                 [3] new_func1()
   [6] func4()                 [5] func2()

这个东西怎么看呢?

首先是flat profile, 它显示了每个函数运行的时间。

从左到右各列分别是:这个函数所用运行时间的百分比,列表从上到下的累计时间,这个函数自身所用的总时间(不包括它调用的其他函数,但是调用的库函数是算在这个时间里的),这个函数被其他函数调用的次数(递归调用不算在内),单次调用该函数所用时间(不包括调用其他函数),单词调用该函数所用时间(包括调用的其他函数),函数名。

还有call graph

最右边是函数名,开始的若干行有缩进,表示调用该函数的函数(父函数),该函数的函数名顶格写,后面又是若干行带缩进的表示该函数调用的函数(子函数)。

相当于带有向边的一个图。

main函数没有被其他函数调用所以父函数是

每列从左到右表示:函数自身所用时间,子函数所用时间,调用次数。

调用次数

在父函数行表示:对应父函数调用了该函数几次/该函数总的调用次数。
该函数行表示:这个函数一共被调用了几次。
在子函数行表示:该函数调用了这个子函数几次/子函数被调用的总次数。

递归函数的调用次数里是把自身调用和其他函数调用分开算的。

reference

GPROF Tutorial – How to use Linux GNU GCC Profiling Tool

学习笔记

gcj2014r1a

problem A

注意到题目说明每个接头都是不一样的,那么变化之后的接头也是不一样的。

枚举第一个接头对应哪个设备,然后那些列要变化就知道了。

然后变完了看看能不能完全匹配上。这里我直接扔到vector里排序了。

problem B

显然先要枚举根。

然后跑一个dfs,记录每个点的子树至少要删多少个点。

如果一个点只有一个儿子就删了,多个儿子取能留下的点最多的两个。

problem C

这个题比较有趣。

大概意思是有两个随机排列生成器,略有不同,大概如下:

sq = range(0, n)
for i in range(0, n):
    j = random.randint(0, n - 1)
    sq[i], sq[j] = sq[j], sq[i]  #就是swap(sq[i], sq[j])
sq = range(0, n)
for i in range(0, n):
    j = random.randint(i, n - 1)
    sq[i], sq[j] = sq[j], sq[i]  #就是swap(sq[i], sq[j])

其中第一个是bad算法,生成的排列并非完全随机。第二个算法是good算法。

问题是给出120个长度为1000的排列,让你判断给你的排列是用哪个算法生成的。

生成排列的流程是:1.随机选一个算法。2.用1中选择的算法生成一个排列。

显然这并不是一个常见的算法竞赛中会出现的题。

题目中直言:即使是我们的最好的程序仍然有小概率不能通过。

但是这毕竟不是icpc,谷歌说了算咯。。。毕竟这题确实有点意思。。。

首先想到的是构造一个统计量,然后直接比较值(出题人给出的做法就是这样的)。

但是我想的办法虽然能体现出一些差距,但是不够通过的。

第一反应就是大表找找规律啥的。

比如:

逆序对个数,bad算法是少于good算法的,这个good算法的数值很稳定,不过差距不够大,没过去;

偏向性,官方题解就是这个思路,如果打个表(我打的是n=5),看看就很清楚了。

关键是如何构造统计量,我把不同位置的数字做差再乘方啥的类似方差之类的搞一搞之后似乎有门,

但是也过不去,这个正确率比上面那个还要低,比较的标准也比较迷。。。没多试就去看题解了。。。。

题解做法一:

直接统计在位置i的数比i小的个数,然后。。。

题解做法二:

搞一个贝叶斯分类器。

给一个排列s我们要求的东西是P(good|s)给定s求是good生成的概率。

根据贝叶斯公式

P(good|s) = P(s|good) P(good) / (P(s|bad) P(bad) + P(s|good) * P(good))

由于是随机选一个生成器,所以P(good) == P(bad) == 0.5

于是P(good|s) = P(s|good) / (P(s|bad) + P(s|good))

已知P(s|good) = (1 / N)^N

所以只要求P(s|bad)

这里有点类似机器学习里的常用处理方法,如果p[i][j]位置i为数字j的概率和其他数字和位置的概率是相互独立的

那么就可以很容易的搞出答案了。

这个p数组可以比较简单的O(N^3)处理出来,
还可以优化到O(N^2)但是我没看懂代码(题解给的链接是tourist的代码orz)

不过既然已经相互独立了,其实更简单的办法是直接随机,
由于不同的位置有N * N个,而每个随机排列要在N个位置上加一,

所以大概平均一下,随机T次每个位置的数量级大概是T N / (N N) = T / N
所以我们随机N * N组的复杂度也是O(N ^ 3)同时精度也不算太差,大概有0.001的精度(而且这题也没法卡啊)。

等有时间仔细看一下O(N ^ 2)的代码再补。

代码(贝叶斯方法)

reference

1.官方题解

算法竞赛

python数据处理(一)

使用python进行数据处理(一)

字典

{}括起来的就是字典,大概用法如下:

dic = {}
dic[3] = 4
dic["sfe"] = 2
# 查看变量是否在字典中
if var in dic:
    code
if var not in dic:
    code
# 设定默认值(如果当前已经存在则不会修改值)
dic.setdefault(key, val)

所有key都带默认值的字典:

# 默认值是int类型,就是int() = 0
from collections import defaultdict
dic = defaultdict(int)

有个OrderedDict可以记住插入的顺序。

遍历字典:

for key, value in dic.items():
for key in dic.keys():
for value in dic.values():

计数器

from collections import Counter
words = sentence.split()
cnt = Counter(words)
print cnt[key]

字典套字典:
要用一个lambda函数

dic2 = defaultdict(lambda :defaultdict(int))
dic2[key1][key2] = value

python数组tuple

支持in 和 not in 操作

支持求min(), max()

顺序存储, 不可改变值,可以连接

可以在里面嵌套一个可以改变值的容器,比如list

tup1 = 1, 2, 3
tup2 = (1, 2, 3)
tup3 = tup1 + tup2
# 切片
a[1:]
a[1:3]
a[1:6:2]
a[:-1]
# 逆序输出
a[::-1]

python里负数的下标是有意义的,就是从后往前数的值。

tuple可以作为字典的key

namedtuple如果只存储数据的话类似c的结构体。

set

str = "a b c d"
Set = set(str.split())
num = len(Set)
Seti = Set1.intersection(Set2)
Setu = Set1.union(Set2)
# 比较两个相同长度的数组有多少个一样的值(同一位置)
print jaccard_similarity_score(a,b)
# 对于统计来说,可以这样做
a = [ 1 if w in str1 else 0 for w in unionstr]
# 以上代码相当于排序去重后检验两个数组是否存在对应的值
# 这样就可以直接调用上面那个函数了

list

list的切片和tuple是一样的,区别主要在于list可以改变。

可以当stack和queue用。

range生成的是一个list

a = []
a.append(val)
a.pop()
a.pop(0) # 这就是从前面pop了

from random import shuffle
shuffle(a)
a.sort()
a.reverse()
b = range(2,23)
a.extend(b) # 连接list


# 一些用法
b = [pow(x, 2) for x in a if x < 0]
b = {x:pow(y, 2) for x, y in dic.items()}
# 可以写一个函数代替pow就可以实现数据筛选等功能
b = tuple(process(x) for x in a)

iterator, generator, iterable

iterator实际上就是一个提供迭代方法的类。

需要定义iter() 和 next()两个函数

对于实现了迭代器的方法可以比较方便的遍历

# 文件是可以使用迭代器按行遍历的
f = open("file")
for item in iter(f):
    print item

具体如何先不管了。。。

# 编写一个generator
def mgen(low, high):
    for x in range(low, high):
        yield x**2

for i in mgen(1, 20):
    code

与一般函数的区别就是最后返回用yield

函数

# 函数赋值
def fun(a):
asdf = fun
asdf(a)

可以在一个函数里嵌套定义函数。

函数的参数也可以是函数。

还可以返回函数。

(python的类型还真是随意。。。
但是作为c过来的, 感觉并不会经常用这种东西)

装饰器

装饰器提供了一种代码复用方式,不过需要程序逻辑符合切片处理的模式。

lambda函数
# 匿名函数
# x是参数,冒号后是返回值
lambda x: x**2
# 相当于
def f(x):
    return x**2
f(x)
map函数
# 遍历一遍迭代器,对每个元素作用函数func
# 返回一个list
map(func, iterable)
# 经常与匿名函数一起用
# 可以传多个参数,此时传入的数组长度必须相同
map(pow, a, b)
# 则a, b分别作为函数的第一个和第二个参数
选择器(filter)
# 每个元素用func检验,返回一个都是true的list
Filter(func, iterable)
zip, * 和 ** 操作符
zip(a, b)
# 把两个list成对打包起来
x, y = zip(*c)
# 打包的逆过程, 但是把第一行的结果再用第二行处理后
# 并不能得到原来的a, b.....
# 这个可以用在函数传参数上
a = (2, 3)
pow(*a)
# **可以用来处理字典,得到若干有值的变量
def func(a, b):
return a * b

dic = {'a': 3, 'b': 4}
func(**dic)

# 任意参数的函数
def func(*args):
# 这个args实际上就是一个tuple

zip在打包的时候要算出两个iterable的所有值。
而izip可以在使用值的时候再计算。

reference

1.Gopi Subramanian, Python Data Science Cookbook

学习笔记

bash脚本(一)

bash的一些基本语句

bash最前面的一行一般是

#!/bin/bash

这个指示该脚本通过/bin/bash来运行。

export:用于设置环境变量,最常见的用法就是写在”~/.profile”里,
然后就可以在开机后自动写入环境变量。

export VARNAME="value"

exit:终止脚本并退出。

其返回值储存在主调函数的$?变量里。

读入:

read [options] NAME1 NAME2 ... NAMEN

bash注释:每行前面加#

执行脚本可以用bash/sh filename或者source filename或者直接用文件名。

如果提示权限不够,可以用chmod 755 filename来设置权限。

debug模式运行命令为:
bash -x filename

这个模式可以在运行的同时显示运行结果和代码。

在代码里可以这样写:

code
set -x
debug code
set +x
code

这样只会输出中间部分的代码。

在bash里前面用减号就是开启一个选项,用加号就是取消。

env:输出全局变量.

变量设定:变量名=”value”

取消变量:unset 变量名

输出变量值要用:echo \$变量名

调用脚本的时候传入的参数使用方法:

调用脚本传入三个参数

./script.sh para1 para2 para3
#script.sh
PARA1=$1
PARA2=$2
PARA3=$3

即第n个参数就用$n来引用。

数学计算要用两个圆括号或一个方括号:

A=3
B=4
C=$(($A+$B))
D=$[$A+$B]

为一个命令起别名以及取消命名(方便啊):

alias name='command'
unalias name

正则表达式

grep命令:在给定的文件中按照给出的模式搜寻字符串。

可以这样用

grep ^root /etc/passwd
grep export ~/.bashrc | grep '\<PATH'

由于grep是寻找匹配的行,所以使用|分割的命令可以达到先确定export所在行再在这些行里查找PATH开头的效果。

正则表达式的语法还是比较多的就不记了。。。

gnu sed and awk

这两个东西可以用来批处理文本。

配合正则表达式可以有很不错的功能。

暂时先知道有这么个东西。

听说awk是神器级的文本处理语言!

if语句

这个很重要,在任何语言里都很重要。。。

if TEST-COMMANDS; then CONSEQUENT-COMMANDS; fi

bash的比较和一般语言不太一样。还是需要查reference的。

一定要注意空格。。。

A=3
B=2
if [ "$A" -ne "$B" ]; then
    echo 233;
fi

连续的if else结构

if TEST-COMMANDS; then
CONSEQUENT-COMMANDS;
elif MORE-TEST-COMMANDS; then
MORE-CONSEQUENT-COMMANDS;
else ALTERNATE-CONSEQUENT-COMMANDS;
fi

重定向

#重定向输入
command < input_file
#重定向输出
command > output_file
#连续的命令通过管道重定向
first_command | second_command
#重定向标准错误
command 2>error_file
#标准输出和错误写至不同的文件
command >output_file 2>error_file
#将标准错误发送至标准输出被重定向的任何位置
command 2>&1

1是标准输入输出,2是标准错误,其他数字还可以用来表示不同的文件。

#将n作为输出file的id
exec fdN> file
#将n作为输入file的id
exec fdN< file

重定向还没仔细看完,以后用到再补。

reference

1.Machtelt Garrels, Bash Guide for Beginners

学习笔记