approximate retrieval(相似搜索)这个问题之前实习的时候就经常遇到: 如何快速在大量数据中如何找出相近的数据.

问题描述: 假设有N个数据, 并且对于他们有一个相似度(或距离)的度量函数sim(i,j), 我们的问题就是如何快速找出所有N个点中相似度较大的i和j组合.

乍一看这个问题必须要对所有的(i,j)计算相似度, 但是N^2的复杂度在N太大的情况下是不能够忍受的.

kdtree

之前在algo-note里面遇到过kdtree, 用它可以使得寻找nearest neighbor的复杂度减少到logN. 但是这种情况对于维度低一点(比如二三维)的情况合适, 维度到了成千上万的时候并不是很好的选择, 所以这里不多讨论.

simhash

另一个思路是, 使用某个hash函数, 对于每一个数据计算一个哈希值. 这个hash函数要满足: 当i和j的相似度很高的时候, hash(i)和hash(j)的值(很可能)相同. 这次介绍的minHash就是这样的一种方法.

Jaccard similarity

明确问题含义, 首先需要定义相似度. 这里主要考虑文本相似度的问题, 假设字典D有M个term ...

当年装mint 17.1的时候心想我的电脑有4GB内存怎么可能不够用, 于是果断没有分一个swap分区, 呵呵...

然后就看到chrome这几年来吃内存越来越严重, 导致我开多几个标签页再开eclipse的话电脑就很有可能直接卡死... 郁闷啊 ! 于是决定给系统增加一个swap分区. 之前给thealternative写邮件询问这件事, Sandro Kalbermatter同学热情回复了我告诉我怎么做, 按照他说的果然成功了, 特此一记.

step1. 建立swap分区

首先, 用gparted调整磁盘分区, 缩小一个磁盘的大小, 然后用空出来的空间新建一个swap分区.

关于swap分区应该多大, 根据这个帖子, 大约是内存的2-3倍, 不过我只是分了和内存一样大的4G空间, 感觉这样应该够用了(吧).

我是把存放文件的500G分区缩小, 这个过程会比较慢, 大概二十多分钟以后才结束:

step2. 编辑fstab

建立好了swap分区以后, 打开终端, 输入sudo blkid查看所有的磁盘分区.

$ sudo blkid   
/dev/sda1: LABEL="FILES" UUID="ddefc0a7-30a1-42fb-a71a-0aebb55cb0b3" TYPE="ext2 ...

几乎所有的ml课都是从线性回归讲起, ETH的课也不例外. 不过这次老师用了贝叶斯的视角讲这个问题, 自从高中接触丁老师讲的线性回归以来 第一次听到一个不同于最小二乘的解读, 感觉很有意思. 又想起来刘未鹏那篇非常棒的博客, 于是想记录一下.

notation

首先有n个数据点:

其中y是实数, 每个x有d个维度, 为了方便表示截距, 再给x加入一个始终等于1的维度:

例子: y代表房价, x代表了房子的面积, 使用时间, 距离市中心的距离等因素.

least square viewpoint

在最小二乘的视角里, 线性回归是用一个x的线性函数拟合y:

使得拟合结果和观测结果的误差尽量小.
不过这次不说最小二乘, 所以接下来不讨论这个思路...

assumptions in Bayes viewpoint

在贝叶斯视角里, 我们假设:
假设1. y = 某个x的线性函数 + 观测噪音
即:

其中εi是一个随机变量, 所以y也是一个随机变量.
另外再有一个比较强的假设:
假设2. ε服从centered高斯分布, iid.

(btw, 对一个随机变量建模, 一般来说, 连续随机变量就用高斯 ...







python科学计算包的基础是numpy, 里面的array类型经常遇到. 一开始可能把这个array和python内建的列表(list)混淆, 这里简单总结一下列表(list), 多维数组(np.ndarray)和矩阵(np.matrix)的区别.

list列表

列表属于python的三种基本集合类型之一, 其他两种是元组(tuple)和字典(dict). tuple和list区别主要在于是不是mutable的.

list和java里的数组不同之处在于, python的list可以包含任意类型的对象, 一个list里可以包含int, string或者其他任何对象, 另外list是可变长度的(list有append, extendpop等方法).

所以, python内建的所谓"列表"其实是功能很强大的数组, 类比一下可以说它对应于java里面的ArrayList<Object> .

ndarray多维数组

ndarray是numpy的基石, 其实它更像一个java里面的标准数组: 所有元素有一个相同数据类型(dtype), 不过大小不是固定的.

ndarray对于大计算量的性能非常好, 所以list要做运算的时候一定要先转为array(np.array(_a_list_ ...

Can we do better than BST if we do not need ordered operations ?

(No compare methods, use equals method)

Idea: save items in an array.
Hash function: method for calclulating the array index of a key.

Issues:

  • computing hash function
  • equality tests
  • collision resolution

Classic space-time tradeoff.

1. Hash Functions ...

1. 1d Range Search

Goal: intersections of geometric objects.

Solution: BST

operations required:

  • insert
  • search
  • delete
  • range search: all keys between k1 and k2
  • range count: how many keys are between k1 and k2

→ find points on an interval

implementation by BST

range count
using the rank ...

goal: lgN for insert/search/delete operations (not necessarily binary trees..)
3 algo: 2-3 tree, (left leaning) red-black tree, B-tree

1. 2-3 Search Trees

def. 2-3 tree

  • allow 1 or 2 keys per node, & 2 or 3 children per node:
    • 2-node: one key, 2 children (ordinary BST node)
    • 3-node: 2 ...

(BST是锻炼递归代码的好题目)

1. Binary Search Trees

def. BST
A binary tree where each node has a key:
for every node, the key is larger than all nodes in left subtree, smaller than all nodes in right subtree.

Fields: key, val, left, right

Implementation

An inner class of BST nodes:

private class ...

1. Symbol Table API

key-value pair abstraction

  • insert a value with a key
  • given a key, search for its value

Association array abstraction

Associate a value to a key — generalized array: a[key]=val.

public class ST<Key, Value>{   
    void put(Key k, Value v);//remove key if value=null ...

1. API and elementary implementations

Collection: data struct for inserting and deleting items (ex. stack and queue).
Priority queue: a special kind of collection — remove largest/smallest element.

API:

public class Max<Kye implements Comparable<Key>>{   
    public MaxPQ();    
    public void insert(Key k);   
    public Key delMax();    
    public boolean isEmpty();     
    public ...