'TF'에 해당되는 글 5건

  1. 2016.02.26 [Similarity] BM25, TF/IDF 한 줄 정리.
  2. 2015.12.16 [Elasticsearch - The Definitive Guide] Theory Behind Relevance Scoring
  3. 2014.10.30 [ElasticSearch] _score 계산 시 IDF 연산은 어떻게 이루어 지나요?
  4. 2013.10.11 [Lucene] score 계산식 알아보기.
  5. 2013.05.15 [Algorithm] TF (Term Frequency)

[Similarity] BM25, TF/IDF 한 줄 정리.

ITWeb/검색일반 2016.02.26 10:52

TF/IDF: common words can still influence the score! 

BM25: limits influence of term frequency


TF/IDF: short fields (title,...) are automatically scored higher

BM25: Scales field length with average


참 간단하죠.

그냥 둘의 가장 큰 차이점이라고 생각 하시면 될 것 같습니다.


저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
tags : bm25, IDF, Similarity, TF
Trackback 0 : Comment 0

[Elasticsearch - The Definitive Guide] Theory Behind Relevance Scoring

Elastic/TheDefinitiveGuide 2015.12.16 11:21

가장 기본이 되는  TF/IDF Scoring 에 대한 설명 입니다.

복습 차원에서 기록해 봅니다.


원문링크)


원문 Snippet)

Term frequencyedit

How often does the term appear in this document? The more often, the higher the weight. A field containing five mentions of the same term is more likely to be relevant than a field containing just one mention. The term frequency is calculated as follows:

tf(t in d) = √frequency 

The term frequency (tf) for term t in document d is the square root of
the number of times the term appears in the document.

Inverse document frequency

How often does the term appear in all documents in the collection? The more often, the lower the weight.Common terms like and or the contribute little to relevance, as they appear in most documents, while uncommon terms like elastic or hippopotamus help us zoom in on the most interesting documents. The inverse document frequency is calculated as follows:

idf(t) = 1 + log ( numDocs / (docFreq + 1)) 

The inverse document frequency (idf) of term t is the logarithm of the number
of documents in the index, divided by the number of documents that contain the term.

Field-length normedit

How long is the field? The shorter the field, the higher the weight. If a term appears in a short field, such as a title field, it is more likely that the content of that field is about the term than if the same term appears in a much bigger body field. The field length norm is calculated as follows:

norm(d) = 1 / √numTerms 

The field-length norm (norm) is the inverse square root of the number of terms in the field.

가볍게 정리 하면)

- tf는 문서 내 발생한 term 빈도수 : term 빈도수가 클 수록 weight 가 높습니다.

- idf는 전체 문서에서 발생한 term 빈도수 : term 빈도수가 작을 수록 weight 가 높습니다.

- norm은 field내 text의 길이 : 길이가 짧을 수록 weight 가 높습니다.


더불어 mapping 설정도 살짝 살펴 보면)

필요한 정보만 저장할 경우 저장소 낭비를 방지 할 수 도 있으며, score 계산시 조금이나마 성능적 효과도 볼 수 있습니다.

모든 옵션을 다 사용해야 할지 선택적으로 사용해도 문제 없을지 잘 판단 하시면 좋을 것 같습니다.


- index_options

Allows to set the indexing options, possible values are docs (only doc numbers are indexed), freqs (doc numbers and term frequencies), and positions (doc numbers, term frequencies and positions). Defaults to positions for analyzed fields, and to docs for not_analyzed fields. It is also possible to set it to offsets (doc numbers, term frequencies, positions and offsets).


- norms: {enabled: <value>}

Boolean value if norms should be enabled or not. Defaults to true for analyzed fields, and to false for not_analyzed fields. See the section about norms.


저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 : Comment 0

[ElasticSearch] _score 계산 시 IDF 연산은 어떻게 이루어 지나요?

Elastic/Elasticsearch 2014.10.30 11:53

어제 저희 회사 행사에서 "오픈소스 검색엔진 구축 사례"로 발표를 했었는데요.

저에게 질문 주셨던 것중에 나름 재밌는 질문을 주셨던 내용이 있어서 공유 드립니다.


(아마도 질문 주신 분은 elasticsearch 를 사용해 보지 않으셨거나 경험 하신지 얼마 안되신 것 같다는 느낌 이였구요. lucene 은 많이 사용해보신 분 같다는 느낌 이였습니다. ㅎㅎ 제 느낌이니 틀릴수도 있구요.)


질문은 이랬던것 같습니다. 

- elasticsearch 에서  색인 시에, IDF 값을 Global 하게 쓰기 어려울 텐데 어떻게 사용되는 지에 대한 질문이었습니다


정답은 아래 링크에 나와 있죠. ^^

(shard 별로 이루어 집니다.)

http://www.elasticsearch.org/guide/en/elasticsearch/guide/current/relevance-intro.html


우선 TF의 경우 뭐 그냥 term frequency 니까 이건 별 문제 없을 거구요.

(기본 per field similarity 입니다.)

IDF의 경우는 그럼 어떻게 할까요 인데요????

IDF는 쉽게말해 index 내 전체 문서에서의 term이 포함된 document frequency 가 되는 건데요.

루씬에서는 뭐 당연히 문제가 안되겠지만 es 에서는 shard 라는 개념이 있죠. 즉 하나의 index를 여러개의 shard 로 나눠서 서로 다른 노드에 가지고 있으니 IDF 를 어떻게 계산 할 수 있을지.... 


제가 보는 관점은 단순 합니다.

- shard 별 document 의 idf 값만 보면 document 의 relevance가 문제일수 있지만, document 의 score 의 경우 tf + idf + field length norm 등 다양한 요소와 함께 계산되기 떄문에 normalized 되었다고 봅니다. 즉 score 값을 신뢰 할 수 있다 입니다.


ㅎㅎ 간만에 검색 질문을 주셔서 재밌었습니다.

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 : Comment 0

[Lucene] score 계산식 알아보기.

Elastic/Elasticsearch 2013.10.11 11:25
필요해서 어제 공부 좀 했습니다.

제가 elasticsearch 로 프로젝트를 진행 하고 있습니다.

랭킹과 문서 스코어링 관련해서 문의가 있어서 정확하게 설명을 해줘야 튜닝에 도움이 될 것 같아 글 좀 남겨 봅니다.


검색해 보시면 많은 문서들이 나오는데요.

아래 문서 참고 하시면 좋을 것 같내요.


[참고링크]

http://www.lucenetutorial.com/advanced-topics/scoring.html

http://devyongsik.tistory.com/364 (여긴 울 회사 재화님도 알고 계신 DEV용식님 사이트인데요. 작성 된지 좀 되었지만 이해 하기에는 좋습니다.)

https://lucene.apache.org/core/3_6_2/scoring.html

http://lucene.apache.org/core/4_5_0/core/org/apache/lucene/search/package-summary.html#package_description

http://lucene.apache.org/core/4_5_0/core/org/apache/lucene/search/similarities/TFIDFSimilarity.html  


[참고용 소스코드]

Similarity.java

DefaultSimilarity.java

TFIDFSimilarity.java


lucene 이나 elasticsearch 나 기본은 바로 위에 있는 넘들 가지고 similarity 계산을 하게 됩니다.

소스를 보시면 아시겠지만 아래 요소를 가지고 score 를 계산 합니다.


tf

idf

lengthNorm

queryNorm

coord


소스코드에서 식을 뽑아 보면 이렇습니다.


 TF

 (float)Math.sqrt(freq)

 IDF

 (float)(Math.log(numDocs/(double)(docFreq+1)) + 1.0)^2

 lengthNorm

 state.getBoost() * ((float) (1.0 / Math.sqrt(numTerms)))

 queryNorm

 (float)(1.0 / Math.sqrt(sumOfSquaredWeights))

 coord

 overlap / (float)maxOverlap


이런건 그냥 위에 나온거 보면 다 나오구요.

검색 질의 시 스코어 계산 유형을 살펴 보겠습니다.

(계산 할 때 위에 식에 넣어서 계산 하기 번거로우니 explain 떠서 나온 값들을 사용해서 계산 하도록 하세요.)


1. 검색어 하나 질의

쉽게는 explain 에서 나온 queryWeight * fieldWeight 를 곱하시면 score 가 나옵니다.

score = (queryWeight * fieldWeight)^2


TFIDFSimilarity.html 에 잘 나와 있죠.

score(q,d)   =   coord(q,d)  ·  queryNorm(q)  · ( tf(t in d)  ·  idf(t)2  ·  t.getBoost() ·  norm(t,d) )
t in q
Lucene Practical Scoring Function

이걸 엑셀 같은 데 식을 넣어서 계산 해 보면 값이 나오게 됩니다.

아래 2번에서 풀어 놓은 식을 참고하세요.


2. 검색어 여러개 질의

score = (queryNorm * SUM( tf * idf^2 * fieldBoost * fieldNorm) )^2


3. 필드 부스팅을 포함한 검색어 질의

쉽게는 아래 처럼 풀어서 이해 하시면 됩니다.

score = ((queryWeight * fieldWeight) + (queryWeight * fieldWeight))^2

-> 필드 부스팅 된 필드의 queryWeight 값은 기본 계산이 되어서 나오지만 같은 필드에 같은 term 으로 했을 경우 기본 queryWeight 에 곱하기 boostScore 만큼 해준다고 보면 됩니다.


여기서 필드 부스팅을 한개가 아닌 여러개를 했다면 (queryWeight * fieldWeight) 이넘을 여러번 계산 해서 더하시면 됩니다.


근데 여기서 궁금한거 하나.... 

- fieldNorm 과 sumOfSquaredWeights 는 어떻게 구하나요???

소스 코드를 보시면 됩니다.


[fieldNorm]

computeNorm(), encodeNormValue(), decodeNormValue(), NORM_TABLE 을 참고하세요.

풀면 결국 아래와 같이 됩니다.


fieldNorm = NORM_TABLE[(floatToByte315(1/SQRT(fieldTotalTermsNum)) & 0xFF)];


[sumOfSquaredWeights]

말 처럼 이건 각각의 term 에 대해서 더하셔야 합니다.

1번에서 처럼  sigma 가 붙어 있는 걸 잊으시면 안됩니다.

이해를 돕고자 풀면 아래와 같이 됩니다.

queryBoost^2 * SUM( (idf * fieldBoost)^2 )


가볍게 이해 하는 수준으로만 사용하시고 깊이 있게 이해를 하고 싶으신 분들은 소스 코드를 꼭 드려야 보세요. :)


신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 : Comment 0

[Algorithm] TF (Term Frequency)

Elastic/Elasticsearch 2013.05.15 14:12

참고 URL : http://kaistwebst.blog.me/130165776517


위 문서에 있는 것 처럼 하나의 문서에서 출현한 하나의 단어 출현 빈도수 입니다.

수식으로 표현 하면

Di : 문서

Wj : 단어(Term)

fij : 출현 단어 빈도 수

log2(1+fij)



예) 

Di : "안녕하세요 검색 관련 색인 빈도 중 Term 빈도, Document 빈도"

Wj : "빈도"

fij : 2

log2(1+2)


DF 설명 : 색인어당 문서의 빈도 수 (색인어 A 가 들어 있는 문서 들 이라고 보면 됨)

신고
크리에이티브 커먼즈 라이선스
Creative Commons License
tags : df, IDF, TF
Trackback 0 : Comment 0

티스토리 툴바