Signal-to-Noise Ratio Information theory에 기반 1948, Claude Shannon information (Shannon의 정의) unexpectedness of a message (의미와는 무관) information content of a choice H(p1,p2,…,pn) n개의 message(event), message i의 발생확률 pi p1+p2+…+pn=1(pi:nonnegative) goal to measure the information content of the choice of a message from this set of messages

Signal-to-Noise Ratio H를 정의하기 위한 3가지 가정 H is a continuous function of the pi 확률이 조금 변하면 H도 조금 변한다 각 확률 pi가 같다면(pi = 1/n), H는 n의 단조 증가 함수이다 후보 메시지의 수가 많으면 H가 크다 하나의 선택을 2개의 연속적인 선택으로 분할할 수 있으면, 분할 후의 H의 합은 원래의 H와 같아야 한다

Signal-to-Noise Ratio 세번째 가정을 설명하는 예 p1=1/2, p2=1/3, p3=1/6 3가지 메시지 중 1개를 직접 선택하는 경우 H(1/2, 1/3, 1/6) 첫번째와 나머지 중 하나를 먼저 선택하는 경우 H(1/2, 1/3 , 1/6 ) = H(1/2, 1/2) + 1/2 H(2/3, 1/3) 두번째와 나머지 중 하나를 먼저 선택하는 경우 H(1/2, 1/3 , 1/6 ) = H(2/3, 1/3) + 2/3 H(3/4, 1/4)

Signal-to-Noise Ratio H의 3가지 가정을 모두 만족하는유일한 함수는 물리학의 entropy 함수이다 H = -K pilog2pi K=1일 때, H =  pilog2(1/pi) average information content

[정리] 2가지 information content 1. 사건(event)의 information content 사건 발생의 unexpectedness log2(1/pi) 2. 사건 선택(choice)의 information content 각 후보 사건의 확률합 = 1 각 후보 사건의 information content들의 평균적인 information content H = pilog2(1/pi) 각 사건의 확률이 비슷할수록 높은 값 선택의 information content가 낮더라도, 확률이 낮은(information content가 큰) 사건의 발생은 높은 unexpectedness

Signal-to-Noise Ratio(continued) Signal-to-noise ratio: sk 정보 이론의 관점에서 index term의 가치를 측정 weight wik=fiksk noise of term k nk=  (fik/tk)log2(tk/fik)= log2[(tk/fik)(fik/tk)] t : the total frequency in the collection f : the frequency of the document signal of term k sk=log2tk - nk (>0, why?)

Term Discrimination Value How well a term distinguish one document from another need to measure the similarity of two documents 같은 key term을 가지고 있는가? Document similarity :  (D1,D2) : 매우 비슷하면 1, 전혀 다르면 0 Average similarity of a document collection 1/(N(N-1))  (D1,D2) (O(N2)의 복잡도) a simpler computation centroid document, D* (O(N)의 복잡도) f*k= fik/N = tk/N, * = c(D*, Di)

Term Discrimination Value discrimination value of term k k= *k- * *k : deleted average similarity for term k * : average similarity containing term k k>0 : term k increases the dissimilarity k<0 : term k decreases the dissimilarity 좋은 식별자일수록 더 큰 양의 k값을 가진다 weight wik=fikk

Other methods of analysis document는 단순한 통계 정보 이상의 것을 담고 있다 e.g. natural language processing Pragmatic factors trigger phrases 특정 유형의 정보가 있음을 알림 figure, table, for example, conclusion, ... source of document 유명한 저자, 저명 학술지, ... 사용자에 대한 정보 high school student or Ph.D.?, well versed or not?

Document Similarity Similarity Lexically based measures are dominant. key concept behind information storage and retrieval. 목적 query에 의해 표현된 정보와 유사한 내용을 가지고 있는 document를 검색하는 것. Lexically based measures are dominant. 문서 길이 등에 의한 편차를 줄이기 위해 정규화된(normalized) similarity measure를 사용

Lexically based measure Basic representation vector form D = <t1, t2, …, tN> ti : ith term in the vocabulary t1, t2, …, tN term frequencies, or indicator of term occurrence

Occurrence-oriented(0-1 vector) Basic comparison unit (D1, D2) = w - (n1n2/N) 0보다 클수도 있고 작을수도 있다 (클수록 비슷) 0인 경우: independence value of w (w = n1n2/N) n1 = w+x n2 = w+y N = w+x+y+z w = the number of terms for which t1i = t2i = 1 x = the number of terms for which t1i = 1, t2i = 0 y = the number of terms for which t1i = 0, t2i = 1 z = the number of terms for which t1i = 0, t2i = 0

Occurrence-oriented(0-1 vector)

Occurrence-oriented(0-1 vector) Coefficient of association 상관 계수 C(D1,D2) =  (D1, D2) /  만 단독으로 사용하면 너무 큰 값이 될 수 있으므로 계수 로 나눈 값을 최종 상관(유사) 계수로 사용 N=10,000, w=1000, n1=1000, n2=1000이면, 는 900 Separation Coefficient 두 문서가 분리된 정도(유사도의 반대 개념) (>0, <1) 유사도 = 평균적 분리도 – 두 문서 간 분리도 (S)=N/2

Occurrence-oriented(0-1 vector)

Occurrence-oriented(0-1 vector) Other coefficients

Occurrence-oriented(0-1 vector) 를 사용하지 않는 coefficient(상관계수) Dice’s Coefficient independant value를 사용하지 않음 w항만을 사용 (산술 평균으로 나눈값) Cosine Coefficient

frequency-oriented 빈도수 기반 유사도 based on metric or distance measure 3가지 가정 nonnegative, 동일 문서간 거리=0 symmetric triangle inequality: d(A, B)+d(B, C) > d(A, C) similarity는 distance에 반비례 pseudo-metric 실제로는 다른 문서간 거리가 0이 되는 것을 허용 list of key terms를 사용하는 경우: full text 검색에 적합

frequency-oriented 유사도(similarity)는 distance의 반비례 함수 Lp metrics ex) if d is distance, e-d can be the similarity function Lp metrics 일반적으로 p는, 1:city block(or Manhatan) distance 2:Euclidean distance :maximal direction distance

frequency-oriented 예제: D1=<2, 0, 3, 5>, D2=<0, 4, 0, 1>,

7. Problems of using a uncontrolled vocabulary The impact of very common terms stop list variants of a given term stemming the use of different terms with similar meanings thesaurus

Stop list (Negative dictionary) most common words(the,of,and,…) in English account for 50% or more of any given text. maintaining stop list can increase performance But, the use of stop words should be carefully considered. ex) “To be, or not to be” Adding subject dependent stop list to general one can solve this problem more or less.

Stemming a given word may occur in many different forms. for example, computer, computers, computing, compute, computes, computation, computational, computationally stemming algorithm can increase performance 주로 접미사(suffix)를 반복적으로 제거 맨끝으로부터 가장 긴 접미사를 찾는 것이 목적

Stemming 접두사(prefix)를 활용하지 않는 이유 problems 접두사인지 단어의 일부인지를 구별하기 힘들다 inner, interior, into 접두사의 제거가 단어의 뜻을 크게 변화시킬 수도 있다 negative prefixes (unfortunate vs. fortunate) problems Result of stemming can make the meaning of words change. ex) breed = bre + ed Stem changes in plural of noun in English. ex) knives = knive + s full text의 stemming에는 매우 큰 비용 대안: query에 대해서만 stemming하고 *를 사용한다 computers -> comput*

Thesaurus different terms can assume similar meanings. ex) post a letter = mail a letter Thesaurus contains synonyms and antonyms broader and narrower terms closely related terms during stroage process, control the vocabulary replace each term variant with a standard term chosen on the basis of the thesaurus

Thesaurus During query process, problems broaden a query and ensures that relevant documents are not missed. problems Homographs two words with distinct meanings but identical spellings 구분을 위해서는 syntactic, semantic, pragmatic analysis가 모두 필요하다 ex) I can can a can. Homonyms (multimedia document의 경우) words that sound alike but have distinct meanings ex) bore vs boar