# (4강) Passage Retrieval - Sparse Embedding > * 단어기반 문서 검색 > * 문서 검색이란 어떤 문제인지에 대해 알아보고 문서를 검색하는 방법 > * 검색을 위해 문서를 embedding 형태로 변환해주는 passage embedding 소개 > * sparse embedding, TF-IDF 에 대해 소개 > > **\[Reference + Further Reading]** > > * [Pyserini BM25 MSmarco documnet retrieval 코드](https://github.com/castorini/pyserini/blob/master/docs/experiments-msmarco-doc.md) > * [Sklearn feature extractor](https://scikit-learn.org/stable/modules/feature_extraction.html#text-feature-extraction) ⇒ text feature extractor 부분 참고 ## 1. Introduction to Passage Retrieval ### 1.1. Passage Retrieval 질문(Query)에 맞는 문서(Passage)를 찾는 것. ### 1.2. Passage Retrieval with MRC ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2F4iMxIlUdK1nMhBqrPw02%2Fimage.png?alt=media\&token=5c0c5e2c-1b27-4283-87dd-9e298697de18) * open-domain Question Answering: 대규모의 문서중에서 질문에 대한 답을 찾는 Task * 질문에 대한 문서를 찾는 passage retrieval * 질문에 대한 답을 찾는 MRC ### 1.3. Overview Query와 Passage를 임베딩한 뒤 유사도로 랭킹을 매기고, 유사도가 가장 높은 Passage를 선택 ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2FppXP8V1wpeEG0aKngNrX%2Fimage.png?alt=media\&token=53e31fde-d57e-4f2e-9b87-60b0e467be11) * Passage에 대한 임베딩은 미리 만들어 두게 되고, 실시간으로 Query에 대한 임베딩을 통해 유사도를 측정한다. * [nearest neighbor](https://ko.wikipedia.org/wiki/%EC%B5%9C%EA%B7%BC%EC%A0%91_%EC%9D%B4%EC%9B%83_%ED%83%90%EC%83%89), 내적 곱 같은 탐색법을 사용한다. ## 2. Passage Embedding and Sparse Embedding ### 2.1. passage embedding space * passage embedding의 벡터공간 * 벡터화 된 passage를 이용하여 passage간의 유사도 등을 알고리즘으로 계산할 수 있 ### 2.2. 🌟Sparse Embedding #### BoW (Bag-of-Words) ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2Fr3iKEoQkX0KkXbxPErST%2Fimage.png?alt=media\&token=402a5495-84a7-4985-b9b0-f0b89e0a24cd) * BoW를 구성하는 방법 -> n-gram * unigram(1-gram): It was the best of times => It, was, the, best, of, times * bigram(2-gram): It was the best of times => It was, was the, the best, best of, of times * Term value 를 결정하는 방법 * Term이 document에 등장하는지(binary) * Term이 몇번 등장하는지 (term frequency), 등. (e.g. TF-IDF) ### 2.3. Sparse Embedding 특징 * Dimension of embedding vector -> number of terms * 등장하는 단어가 많아질수록 증가 * N-gram의 n이 커질수록 증가 (최대 n제곱개만큼 커질 수 있음) * Term overlap을 정확하게 잡아 내야 할 때 유용하다. * 실제로 그 단어가 문장에 포함되어있는지를 체크하기에 좋음 * 반면, 의미(semantic)가 비슷하지만 다른 단어인 경우 비교가 불가 ## 3. TF-IDF ### 3.1. TF-IDF (Term Frequency - Inverse Document Frequency) * Term Frequency (TF): 단어의 등장 빈도 * Inverse Document Frequency (IDF): 단어가 제공하는 정보의 양 * ex) It was the best of times * it, was, the, of : 자주 등장하지만 제공하는 정보량이 적음 * best, times: 더 많은 정보를 제공 ### 3.2. TF (Term Frequency) 해당 문서 내 단어의 등장 빈도 * Raw count * Adjusted for doc length: raw count / num words (TF) * Other variants: binary, log normalization ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2FJ3M0lXGbBD7efLJfsCFc%2Fimage.png?alt=media\&token=8feb0747-52fe-427a-815a-f66034479343) ### 3.3. IDF (Inverse Document Frequency) 단어가 제공하는 정보의 양 $$IDF(t) = log(\frac{N}{DF(t)})$$​ * DF(document frequency) = Term t가 등장한 document의 개수 * the 같은 term은 모든 문서에 나타날 것이다. -> log1 = 0 * N: 총 Document의 갯수 ### 3.4. Combine TF & IDF TF-IDF(t, d): TF-IDF for term t in document d $$TF(t, d) \times IDF(t)$$​ * a, the 등의 관사는 위 3.3) 에서 본 것과 같이 DF의 값이 0에 가까워 TF-IDF 값이 작다. * 자주 등장하지 않는 고유명사(사람이름, 지명)는 IDF값이 커지면서 전체적인 TF-IDF의 값이 증가한다. 위 두 가정은 많은 수의 document를 가질 때 일반적으로 나타나는 현상으로 봐야한다. ### 3.5. TF-IDF 계산하기 ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2FxF3Gkn2SfHegWiLMEoc4%2Fimage.png?alt=media\&token=0b8bed67-67ae-485b-9ddb-3113e0789f27) ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2FU7EJselOp384IwwI0GHw%2Fimage.png?alt=media\&token=df8f0318-cc4f-4eb7-b85c-b227fd0a275e) ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2FZxI6bBdxfcIdZy6mMEyo%2Fimage.png?alt=media\&token=d4859072-b41d-4fde-8119-55338539dfcb) ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2FoPKKwBvJeMQTh4kxUxU4%2Fimage.png?alt=media\&token=14341429-b254-4d86-a9ac-4946783b4e63) ### 3.6. BM25란 * TF-IDF 의 개념을 바탕으로, 문서의 길이까지 고려하여 점수를 매김 * TF 값에 한계를 두어 일정한 범위를 유지하도록 둠 * 평균적인 문서의 길이보다 더 은 문서에서 단어가 매칭된 경우 그 문서에 대해 가중치를 부여 * 실제 검색엔진, 추천 시스템 등에서 아직까지도 많이 사용되는 알고리즘 ![](https://3944465397-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MjcKlzGhHYe2bvmxTwS%2Fuploads%2FuNrPjiztEtUYLFJdpOu4%2Fimage.png?alt=media\&token=f5416557-8327-42e3-ac06-ce7ea43d9a69) ## 실습 Link {% embed url="" %}