[CS246] Finding Similar Items (4) - Locality Sensitive Hashing (LSH)
Recap: Shingling and Minhashing$k$-shinglesdocument를 set으로 매핑. 아래 표는 $k=3$인 경우의 예시다.Jaccard Similarity두 집합의 유사도를 구하는 방법 중 하나.$J(S, T) = \text{sim}(S, T) = \cfrac{|S \cap T|}{S \cup T}$$\text{sim}(S_1, S_3) = \cfrac{2}{3}$ Minhashrow의 random permutation을 하나 고르고, 처음으로 1이 나오는 row index를 minhash value로 한다.아래 예시에서 random permutation은 $[1, 0, 3, 2]$라 하자.$S_1 = [0, 1, 1, 0]$에서 $1$이 처음 나오는 row는 2번째이고 ra..
2023. 9. 21.
[Bayesian] Linear Modeling Settings (선형 회귀 모델링, MLE, Least Square, MAP, Ridge)
Notation우리가 관측한(얻은) $n$개의 데이터셋을 $\mathcal{D}$이라 하자. 각 데이터 표본(인스턴스)는 $d$차원 변수이고, label은 상수(스칼라) 이다. 이를 수식으로 표현하면 다음과 같다.\[ \mathcal{D} = (X, y), \quad X=[x_1, \dots, x_n]^\top \in \mathbb{R}^{n \times d}, \quad y=[y_1, \dots, y_n]^\top \in \mathbb{R}^{n} \]$X$의 $i$번째 표본은 $X_i = (x_i, y_i)$이고 $x_i$는 $d$차원 벡터이고 $y$는 스칼라이다. ($x_i \in \mathbb{R}^d$)그리고 더 basis function(기저 함수, 혹은 feature map으로도 불린다)을 ..
2023. 9. 17.
