본문 바로가기
728x90
반응형

분류 전체보기249

[CS246] Finding Similar Items (4) - Locality Sensitive Hashing (LSH) Recap: Shingling and Minhashing $k$-shingles document를 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}$ Minhash row의 random permutation을 하나 고르고, 처음으로 1이 나오는 row index를 minhash value로 한다. $h(S_1)=0,\ h(S_2)=2,\ h(S_3)=1$ $\Pr(\text{minhash is same}) = \text{Jaccard Similarit.. 2023. 9. 21.
[CS246] Finding Similar Items (3) - Minhashing Jaccard Similarity 자카드 유사도는 두 집합의 유사도를 구하는 방법 중 하나이다. 두 집합 $A,\ B$의 자카드 유사도를 구하면 다음과 같다. \[ J(A,\ B) = \cfrac{|A \cap B|}{ |A \cup B| } = \cfrac{|A \cap B|}{|A| + |B| - |A \cap B|} \] ※ 자카드 거리(Jaccard distance)는 $d_J(A,\ B) = 1 - J(A,\ B)$ 이다. ※ IoU(Intersection over Union) 과 식이 유사하지만 보통 IoU는 region, bounding box 에서 사용되는 용어이다. 자카드 유사도는 앞서 설명한 characteristic matrix의 column similarity를 계산하는데 사용된다... 2023. 9. 20.
Optuna & LightGBM ※ 원래 velog에 있던 내 글을 티스토리에 옮김 optuna를 이용하면 파라미터 튜닝을 알아서 해준다. 정확히 말하자면 각 파라미터마다 튜닝할 숫자의 범위를 정해주면, 각 trial마다 random하게 숫자를 골라준다. 단순히 random selection이 아니라 grid search도 적용할 수 있어서 효율적으로 파라미터를 튜닝한다. Optuna references 나는 아래 링크에 있는 글에서 도움을 많이 받았다. (특히 첫번째 글) 좀 더 명확한 feature 분석을 위해서는 추가 작업도 해야하지만 이 글에서는 그냥 파라미터튜닝 자체에만 설명한다. https://www.kaggle.com/code/corochann/optuna-tutorial-for-hyperparameter-optimizat.. 2023. 9. 19.
[CS246] Finding Similar Items (2) - Shingling Shinglings $k$-Shinglings document를 길이가 $k$인 문자열 집합으로 표현한다. 예를 들어 "abcdabd"에 대해 $k=2$인 2-shingling 집합은 {ab, bc, cd, da, ab, bd} 이다. 공백과 관련하여 몇까지 옵션이 가능하다. (blank, tab, newline 등) 일반적으로 $k=9,\ 9,\ 10$ 정도로 한다. textually similar한 문서들은 많은 수의 shingling이 겹칠 것이다. 단순히 한단어를 바꾸는 것으로는 $k-1$ 거리만큼만 바뀐다. 예를 들어 "The dog which chased the cat" 과 "The dog that chased the cat"을 비교해보자. 두 문장의 차이점은 오직 "g_which_c"에서만 .. 2023. 9. 19.
[CS246] Finding Similar Items (1) - Introduction Big Picture naive하게 similar item을 찾는다고 하면 이중 루프를 통해 유사도를 계산하는 것을 생각할 수 있다. 해싱(hashing)을 이용하여 제곱의 시간복잡도 없이 유사한 아이템을 빠르게 찾을 수 있다. 대표적인 알고리즘으로 Locality-Sensitive Hashing (LSH)에 대하여 공부할 것이다. LSH의 장점으로 매우 적은 pair만으로도 계산이 가능하다는 것이고, 단점으로 false negative가 존재할 수 있다는 것이다. Applications Finding Similar Documents web, 뉴스 기사 등의 매우 큰 스케일에서 문자 그대로(textually) 유사한 문서를 찾는 것이다. 의미가 비슷한(similar meaning, topic) 것을 찾는.. 2023. 9. 18.
[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.
728x90
반응형