코딩펭귄

• 이항 분포

  • X ~ B(n, p)
  • P(X = x) : 사건이 일어날 확률이 p일 때, n번의 독립 시행에서 사건이 x번 일어날 확률

• 포아송 분포

  • X ~ Poi(λ)
  • P(X = x) : 단위 시간당 λ번 발생하는 사건에 대해, 사건이 단위 시간에 x번 발생할 확률
  • 이항 분포에 극한을 취해 구한다.

• 기하 분포

  • X ~ Geo(p)
  • P(X = x) : 사건이 일어날 확률이 p일 때, x번의 시행에서 처음 사건이 일어날 확률

• 지수 분포

  • X ~ Exp(λ)
  • P(X = x) : 처음 발생하기까지 λ 단위 시간이 걸리는 사건에 대해, 사건이 x 단위 시간 후에 처음 발생할 확률
  • 기하 분포에 극한을 취해 구한다.

• 음이항 분포

  • X ~ NB(r, p)
  • P(X = x) : p의 확률로 사건이 발생할 때, r번 성공하기까지 x번 시도해야 할 확률

• 베타 분포

  • X ~ β(a, b) : 동전을 던져서 head가 (a-1), tail이 (b-1)번 나왔을 때, 앞면이 나올 확률 p의 분포 (추정치)
    • β(1, 1) = Uni(0, 1) -> imaginary trial이라고 볼 수 있다.
    • X ~ β(6, 4)일 때, X|(H=2, T=3) ~ β(8, 7)
  • X ~ Uni(0, 1) 이고 (prior) N은 head가 나오는 횟수에 대한 확률 변수일 때, P(X = x | N = n)를 bayesian으로 해석해서 구한다.

출처 : http://timroughgarden.org/notes.html

Similarity Search

• Applications

  • Similar documents, web pages, etc.
  • Collaborative filtering : 비슷한 제품 찾거나 비슷한 구매자 찾아주기
  • Machine learning / classification : 비슷한 두 datapoint -> same label
  • Combining datasets : 천문학에서 사진들 추가/분류

Similarity Metrics

• Jaccard Similarity

  • Given S, T \in U, J(S, T) = |intersection(S, T)| / |union(S, T)|

• L_p Distance

  • ||x - y||_p = ( \sum{1 <= i <= d}(|x_i - y_i|^p) )^(1/p)
  • p=1이면 manhattan distance, p=2면 Euclidean distance, p=\inf면 max_i distance.
  • p=2일 때에만 rotationally invariant.
    • 즉, 각 coordinate가 특별한 무언가를 뜻하는 게 아니라면 p!=2를 사용하는 건 권장되지 않음.

kd-tree

• Algorithm

  • kd-tree는 기본적으로 binary search tree.

  • Insertion

    • 현재 노드 v에 set S가 주어졌다고 하자. x_i \in S는 R^d의 elt.
    • n = 1이면 v에 x_1을 넣고 종료
    • Otherwise, 1 <= i <= d인 i를 하나 고르자. (suggested heuristic이 다양하게 있음.)
    • m = median(x_1(i), x_2(i), ..., x_n(i))으로 잡고, i와 m을 v에 저장한다.
    • i-th coordinate가 m 미만이면 S_<, m 이상이면 S_>= 로 보내서 재귀적으로 알고리즘을 수행한다.

  • Find

    • x가 들어갔을 leaf node를 찾는다.
    • 거기서부터 위로 올라오면서, "closest point to x가 반대쪽 child subtree에 있을 수 있겠는가?"를 생각한다.
      • If yes, 거기도 탐색한다.
      • ex) d=1이면 항상 no.

• 한계

  • high dimensional data에서는 잘 작동하지 않는다.
    • d <= 20 or n >= 2^d 여야지 잘 작동한다.

Fingerprint

• Preserves what?

  • distinctness

• Algorithm

  • hash func h를 고른 다음, f(x) = h(x) / Z_2 로 고르자.
  • 그러면 P[f(x) = f(y)] <= 1/2
  • hash func의 수를 늘려서 원하는 probability까지 낮춘다.

Random Projection

• Preserves what?

  • L_2 distance

• Algorithm

  • R^k를 R^d로 project한다고 가정하자.
  • 각 coord.를 N(0, 1)에서 뽑은 random vector r \in R^k를 만들자.
  • E[ (<r, x> - <r, y>)^2 ] = d(x, y)^2
  • R^k의 n points의 nC2개의 interpoint L_2 distance를 1±ε factor로 유지하고 싶다면, d = Θ(ε^(-2) log n) 으로 잡으면 된다.
    • Θ의 factor는 2 미만이라 보면 된다.

Johnson-Lindenstrauss Transform

• Preserves what?
  • L_2 distance
• Algorithm
  • d x k matrix A의 각 coord.를 N(0, 1)에서 뽑은 다음에, JL(A, x) = (1/sqrt(d))Ax 로 transform하자.
  • 그러면 ||JL(A, x)||^2 은 d개의 random projection에서 나온 'squared L_2 distance estimation'의 mean이 된다.
• 개선점
  • A의 각 coord.를 {-1, +1}에서 random하게 뽑아도 된다. (경험적/이론적으로 모두 증명됨.)
  • Ax를 계산할 때 FFT를 쓰면 빨라진다.
  • d는 수 백 정도가 된다. 더 줄이고 싶으면 locality sensitive hashing을 사용할 수 있다.
    • x와 x'가 비슷하면 h(x)와 h(x')가 같은 bucket에 들어갈 가능성이 높은 hashing이다.

MinHash

• Preserves what?

  • Jaccard similarity

• Algorithm

  • Permutation π : U -> U 를 random하게 고른다.
  • S \in U에 대해, MinHash(S) = argmin{x in \S} π(x) 라고 하자.
  • 그러면 A, B \in U에 대해 P[ MinHash(A) = MinHash(B) ] = J(A, B)
    • 왜? π가 random하게 골라지기 때문에, MinHash(A) = MinHash(B) iff union(A, B)의 min elt가 intersection(A, B)의 elt.

출처 : https://www.coursera.org/learn/algorithms-on-graphs

A* Algorithm

Potential Function

• π : V -> R
• l_π(u, v) = l(u, v) - π(u) + π(v)
• 모든 (u, v)에 대해 l_π(u, v) >= 0이면 π는 feasible.

A*

• Feasible인 potential function π를 고른 다음에, l_π(u, v)에 대해 Dijkstra를 돌리자.
  • 또는, heap에서 매번 dist[v] - π(s) + π(v) (or dist[v] + π(v)) 가 최소인 v를 뽑아 Dijkstra를 돌리자.

Bidirectional A*

• π_f, π_b가 주어졌다고 치자.
• p_f(v) = (π_f(v) + π_b(v)) / 2, p_b(v) = - p_f(v) 를 사용하여 BiDijkstra를 돌리자.

Lemmas

• π가 feasible이면 A*는 OPT.
• π_f, π_b가 feasible이면 p_f, p_b도 feasible.

Potential Functions

제안

1. Euclidean distance
2. Landmark set L에 대해, A \in L 중 하나를 잘 골라서 π(v) = d(A, v) - d(A, t) or d(v, A) - d(t, A)로 하자.
   • 즉, A가 s와 t보다 동시에 '앞'에 있거나 '뒤'에 있어야 한다.

Lemmas

• Lower bound lemma
  • π가 feasible이고 π(t) <= 0이면 π(v) <= d(v, t) for all v
  • Euclidean distance d는 feasible (따라서 lower bound)
• π(v) = d(A, v) - d(A, t) 는 feasible하며 π(v) = 0.
  • π(v) = d(v, A) - d(t, A)도 마찬가지.

출처 : https://www.coursera.org/learn/algorithms-on-graphs

Bidirectional Dijkstra

Dijkstra Revisited

• Invariant
  • Process한 (heap에서 꺼낸) v까지의 dist는 shortest path의 dist.
• Work toward
  • 모든 v를 방문

Bidirectional Dijkstra Algorithm

• s에서 정방향으로, t에서 역방향으로 탐색하다가 공통으로 process한 m을 만나면 중단.
• 양쪽 다 dist 계산을 한 vertices를 보면서 dist_F(v) + dist_B(v)가 min인 값이 OPT.

Lemma

• BiDijkstra가 m에서 만나면, BiDijkstra가 방문한 vertices로만 구성된 shortest path가 존재한다.
• BiDijkstra가 만났을 때, shortest path s->v->w->t가 {s, v} \in F, {w, t} \in B 이면 dist_B(v)는 v->t의 최단거리이다.

응용

• Road network에서는 around 2x faster.
  • v가 촘촘하기 때문.
• Social network에서는 훨씬 더 빠름.
  • v당 e가 100개가 넘고, "6 handshakes"가 적용되기 때문.

출처 : http://timroughgarden.org/notes.html

Heavy Hitters

• Problem

  • Given an array A of length n and a parameter k (n >> 1, k > 1), find all a \in A s.t. a is repeated at least n/k times.

• Applications

  • Computing popular products
  • Computing frequent search queries
  • Identifying heavy TCP flows
  • ... top-k와 비슷하지만, 일정 ratio 이상을 모두 잡아내는 문제.

• Theorems

  • There does not exist an one-pass algorithm that solves HH w/ a sublinear amount of auxiliary space.
  • Pf) y \in {x_1 .. x_n/k-1} 문제가 되는데, 이걸 memorization 없이 풀 수가 없다.

Count-Min Sketch

• Goal

  • single-pass와 적은 space로 각 elt가 최소 몇 개 이상 등장했는지 tracking해주는 알고리즘.

• Algorithm

  • # of buckets b, # of hash funcs l을 정하고 (lxb) int array CMS를 만든다.
  • Inc(x) = ++CMS[i][h_i(x)] for all 1 <= i <= l
  • Count(x) = min{1 <= i <= l}(CMS[i][h_i(x)])

• Bloom Filter와의 관계

  • CMS를 int array 대신 bit array를 만들고 Inc(x) = CMS[i][h_i(x)] OR 0x1 로 세팅하면 Bloom Filter가 된다.

• Theorems

  • Z_i = CMS[i][h_i(x)]라 하면, E[Z_i] <= f_x + n/b
  • Y = Z_i - f_x, c > 1이라 하면, Markov's inequality에 의해, P[Y > cn/b] <= 1/c.
    • 이게 독립적으로 l개 있으니 P[Count(x) - f_x > c/nb] <= (1/c) ^ l.

• 성질 (중요!)

  • Count(x) >= m인 elt들을 고르면 f_x >= m인 elt는 모두 골라진다. 하지만 f_x < m인 elt들도 걸린다.
  • f_ys = Count(x) - f_x 라 하면, f_ys의 기대값은?
    • E[f_ys] <= n/b
  • 그러면 f_ys가 기대값보다 커질 확률은?
    • P[f_ys > cn/b] <= 1/c
  • 따라서 아래에 나올 ε-HH에 응용하기 위해서는 cn/b = εn가 되고 c가 적당히 크도록 b와 c를 잡으면 된다.
    • 대강 n/b를 εn의 1/2 or 1/e로 (b를 2/ε or e/ε로) 잡으면 된다.

Approximate Heavy Hitters (ε-HH)

• Problem

  • Given n, k, ε, output a list s.t.
    • n/k번 이상 나오는 elt는 모두 포함.
    • list의 모든 elt는 array에 n/k - εn번 등장해야 함.
    • auxiliary space는 O(1/ε).

• n을 아는 경우

  • b = e/ε, l = ln(1/δ)으로 놓으면,
    • space는 O(k ln(1/δ))
    • n/k번 이상 나오는 elt는 모두 포함.
    • list의 각 elt가 array에서 n/k - εn번 미만으로 등장할 확률은 δ.

• n을 모르는 경우

  • b = e/ε, l = ln(1/δ)으로 놓고, Count(x)가 key, x가 elt인 heap을 하나 유지하자.
  • single pass로 작동하면서, 매 array elt가 들어올 때마다 Inc(x) >= m/k이면 heap에 넣고, heap에서 Count(x) < m/k인 애들을 다 쳐내자.
  • 분석
    • space는 O(k ln(δ)) (heap size는 2k + α면 충분하니까)
    • n/k번 이상 나오는 elt는 모두 포함.
    • list 전체에 대해 확률을 묻는 게 아니라 list의 각 elt의 false positive 확률을 묻는 것이기 때문에, 각 elt가 array에서 n/k - εn번 미만으로 등장할 확률은 δ.