際際滷

際際滷Share a Scribd company logo

?7? ???? ??

?
?
Chang-yong Jung
Chang-yong Jung

??????? ??????? ??. ???? ??? ???

1 of 46
Downloaded 72 times
???? ?7?. ???? ?? INFORMATION RETRIEVAL ??: ??? (timothy97@gmail.com) http://www.facebook.com/hhuIR Korea Maritime University Navis Control Inc.
Over view ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
???? ?? ? ???? ??? ? ??? ??? ???? ???? ?? ? ???? ? ?? ??? ???? ???? ???(???)? ?? ? ???? ??? ? ??? ??? ??? ??(??, ??)? ???? ??
Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
??? ???(Weight) ? ??? ???(weight) ? ???? ?? ??? ??? ? ?? ??? ?? ?? ? ???? ?? ? ??? ??? ??? ???? ???? ?? ? ???? ?? ? ?? ??? ???? ???? ??? ?? ??? ???? ??? ? ? ? ???? ?? ?? ? ???? ?????(normalization) ? ??? ??? ??? ????? ?? ? ??? ??? ?? ??? ???? ?? ?? ?? ??? ?
tf * idf ? ?? ? TF (Term Frequency) : number of occurred term in a document ? DF (Document Frequency) : number of documents where term occurs ? IDF (Inverse Document Frequency) : Inverse DF ? Weight = TF * IDF ? TF? ??, DF? ???? ???? ???. ? ?????? ????? ???? ???? ???? ??. ?? ???? ???? term? ??? ??? ?? ??? ? ?? term? ??? ??? ??
????? ?? ? ????(Term frequency) ? b(binary) 1(??), 0(???) ? n(natural) tf ? ??? ? a(augmented) ?+ ??? ? ?? ? l(logarithm) 1 + log ?? tf (term frequency): ???? ?? ? ?? t? ?? ??? ??
????? ?? C c o n t ¨d ? ????(Document frequency) ? n(no) 1 ? ? c(cosine) log ? ? ? ?(+0.5) ? p(prob idf ) log ?(+0.5) N : DB? ???(??) ? ? n : DB? ?? t? ???? ?? ?
????? ?? C c o n t ¨d ? ???? ???(Document length normalization) ? n(no) 1 1 ? c(cosine) ?2 ? ?? ? a(?? tf ???) 1 ? ?? + ?? 〜 max ?? ? + 1 〜 ?? ? b(byte?? ???) ?? ? 1 ? ? + ? 〜 ??????? ?? + ?? 1 ? u(?????? ???) 1.0 ? ????? 〜 ????? + ????? 〜 # ?? ?????? ????? dl : ??? ???? ?? ?(????) (average dl? ??????) n : DB? ?? t? ???? ?? ?
????? ?? ???? ? ??(?? ??) ? ?????(tf )? ?? ? bnn 1 ? nnn tf ? lnn log ?? + 1.0
????? ?? ???? C c o n t ¨d ? ??? ???(idf )? ?? ? ? btn log ? ? ? ? + 0.5 ? bpn log ? + 0.5
????? ?? ???? C c o n t ¨d ? ??(?? ??) ? ????? 〜 ??? ??? ?? ? ? ntn ?? 〜 log ? ?? ? ? atn 0.5 + 0.5 〜 max 〜 log ?? ? ?+1 ? dtn 1 + log(1 + log ??) 〜 ?
????? ?? ???? C c o n t ¨d ? ??? log(??)+1.0 ? lnc (log ??+1.0) 2 ? ??〜log ? ntc ? ? 2 ??〜log ? ? (log ??+1.0)〜log( ? ) ? ltc 2 ? log ??+1.0 〜log ? ?? 0.5+0.5〜 ? anc max ?? ?? 2 0.5+0.5〜 max ??
????? ?? ???? C c o n t ¨d ?? ? 0.5+0.5〜 〜log ? atc max ?? ? ?? 2 ? 2 0.5+0.5〜 max ?? 〜 log ? 1.0 + log ?? 1.0 + log(????) ? lnu 1.0 ? ????? 〜 ????? + ????? 〜 # ?? ?????? ????? ? (1.0+log ??)〜 log ? ? ltu 1.0 ? ????? 〜 ????? + ????? 〜 # ?? ?????? ????? 1 + log(1 + log ??) ? dnb ?? (?? ????) 0.8 + 0.2 〜 ???? (?? ????) ?? ? ? ? + 0.5 ? npb ?? 〜 log ? + 0.5 2 〜 0.25 + 0.75 〜 ???? + ??
Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
???? ?? ? ??? ???? ?? ? ???? ??? ????? ??? ??? ??? ???? ?? ? ?? ?? ?? ? ????? ??? ?? ? ??? ???? ???? ??? ??? ? ?? ? ??(binary) ??? : ??(1) or ???(0) ? ???? ?? ? Vector Model = Vector Space Model = Term Vector Model ? ??? ??? ?? ?? ? ?? ??(partial matching) ?? ? ??? ??? ???(similarity)? ???? ??? ?? ? Cosine ???
???? ?? C c o n t ¨d ? ??? ???? ?? ? n ?? ????? ???? ?? ? n-??? ?? ???? ?? ? ??(term)? ?? ????? ? (axe)? ?? ? ??? ?? ???? ? ?? ? ???. ? ? ???(Very high- dimensional) ?? ? ????? ?? ? 1000?- dimension ??? ?? ?? ??, sparse-vector: ??? ? ??? 0(zero)? ? ? = (?1? , ?1? , ? , ? ?? )
???? ?? C c o n t ¨d ? ??? ???? ?? ? Key idea 1: ??? ?? ?? ???? ??? ?? ? Key idea 2: ?? ?? ??? ??? ?? ???? ?? ??? ? ???(proximity) = ??? ???(similarity) ? ??? ??? ?? ?? ? ? ? = (?1? , ?2? , ? , ? ?? ) ? ? = (?1? , ?2? , ? , ? ?? ) ? TF * IDF ???? ?? ??
???? ?? C c o n t ¨d ? ?? ? ???? ???? ?? ??/ 1 2 3 4 5 6 7 ´ n ??? term ?? ?? ???? ?? ??? ?? ??? ???? ??1 1 1 0 1 0 0 1 0 ??2 1 0 1 1 0 0 0 0 ??3 0.8 0 0.5 0.9 0 0 0 0 ??4 0.5 0.3 0.9 0.7 0 0 0 0 ??? 1 1 0 0 1 0 0 0 0 ??? 2 0.9 0 0 0.8 0 0 0 0
Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
??? ??? ??? ? Euclidean distance ? ? ?? d 1 (w 11 , w 12 ), d 2 (w 21 , w 22 ) ??? ?? = (?21 ? ?11 ) 2 +(?22 ? ?12 ) 2 ? ??? ??? ? ??? ???? ?? ? ???? ?? ? ??? ??? ?? ??? ? ??? ???? ?? ? ?) S(q, d 2 ) vs. S(q, d 1 ) ? ??? ?????.
???? ???? ??? ??? ? Length Normalization ? ?? ?? ??? ??? 1? ?? ??? ?? ??? ?? 1 ?? 2 ??? ?? 1 ?? 2 a 5 0 a 5/8.367=0.598 0 b 3 5 b 3/8.367=0.359 5/5.477=0.913 c 6 2 c 6/8.367=0.717 2/5.477=0.365 d 0 1 d 0 1/5.477=0.183 ??? ????? ??? ????? ?? 1? ????? ?? = 52 + 32 + 62 = 8.367 ?? 2? ????? ?? = 52 + 22 + 12 = 5.477 ? ???? ????? ??? ??? ? ??? ? 1 , ? 2 = 0.359 〜 0.913 + 0.717 〜 0.365 = 0.589
???? ??? ??? ?? ? ??? ?? ? ? ?? ??? ?(angle)? ????? ????. ? ? ?, ?? ?? ??? ?? Consine ?? ????. ?1 ??2 ? ???? = ?1 ?2 ? ?=1 (? 1? 〜? 2? ) ? ??? ? 1 , ? 2 = ? ? 1? 〜 ??=1 ? 2? 2 2 ?=1
???? ??? ??? ?? C c o n t ¨d ? ?? ? D 1 = (?????2, ??1, ??1, ??1) ? Q = (?????1, ??????1, ??1, ??1) ?assume, (t 1 , t 2 , t 3 , t 4 , t 5 ) = (??, ??????, ??, ??, ?????) ? D 1 = (1, 0, 1, 1, 2) ? Q = (1, 1, 0, 1, 1) 1〜1+1〜1+2〜1 ? cos ?1 , ? = ??? ?1 , ? = = 0.76 (12 +12 +12 +2 2 )〜(12 +12 +12 +12 ) ? ??? ??????? ???? ????? ?
??? ??? C ?? ? ??? ???? ?? ??? ?? ??: http://mwultong.blogspot.com
Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
????? ?? ??? ??? ? ?? ???(inter val data) ? ????? ??(Euclidean distance) ? ? ?, ? = ? (? ? ? ? ? )2 ? ?? ????? ?? ? ? ?, ? = ? (? ? ? ? ? )2 ? ??(block) ?? ???(Manhattan) ?? ? ? ?, ? = ? ?? ? ?? ? ????? ??(Minkowski metric) 1 ? ? ? ?, ? = ? ?? ? ?? ?
????? ?? ??? ??? C c o n t ¨d ? ?? ???(inter val data) ? ??? ????(Pearson correlation coefficient) ? (? ? ?? )(? ? ?? ) ? ? ?, ? = 2〜 2 ? (? ? ?? ) ? (? ? ?? ) ? ??? ??(Cosine coefficient) ? (? ? ? ?) ? ? ?, ? = ? ? ?2〜 ? ? ?2 ? ?? ??(Vector ?? Inner product) ? ? ?, ? = ? (? ? ? ?)
????? ?? ??? ??? C c o n t ¨d ? ?? ???(binar y data) ??(??)?? ?? t ?? ??? ?? a b ???? ?? t ??? c d ? ????? ?? ? ?, ? = ?+ ? (???) 2 ? ?? ?? ? ?, ? = (?+?+?+?) 2 (?+?) ? ?? ? ?, ? = 4(?+?+?+?) ?+? ? ??/?????? ? ?, ? = 2?+?+?
????? ?? ??? ??? C c o n t ¨d ? ?? ???(binar y data) ?+? ? ???? ?? S ?, ? = ?+?+?+? ? ? ??/?? ?? S X, Y = ?+?+?+? ? ? ??? ?? S X, Y = ?+?+? 2? ? ??? ?? S X, Y = 2?+?+? ?+? ? ???/???? ?? S X, Y = ?+?+2(?+?) ??? ?? ? ?? Y S X, Y = ??+ ?? ?? ??? ? ?? Q S X, Y = ??+?? ? ? ???? ?? S X, Y = (?+?)〜 (?+?)
????? ?? ??? ??? C ?? ? ??? ??? ??? ?? ?? ? ?? D i = (3, 2, 1, 0, 0, 0, 1, 1) ? ?? Q = (1, 1, 1, 0, 0, 1, 0, 0) ? 2 ?=1 (? ?? 〜? ?? ) 2〜6 ? ??? ?? = ? ? = =1 ?=1 ? ?? + ?=1 ? ?? 8+4 (? ?? 〜? ?? ) 6 ? ??? ?? = = =1 ? ?? + ? ?? ? (? ?? 〜? ?? ) 8+4?6 (? ?? 〜? ?? ) 6 6 ? ??? ?? = = = 16〜4 8 (? ?? ) 2 〜 (? ?? ) 2
???? ??? ??? ? ?? ? ???(Similarity) ???? ????? ???? ??? ? ???? ??? ??? ???? ???? ?? ? ?? ? ??? ??? ?? ????? ????? ???? ??? ???? ?? ? ??? ?? ??? ??? ??? ??? ?? ? ?? ??? ?? ?? ? ???? ??(Cluster Model) ?? ? ?????(Inverted index file)? ???? ?? ??? ????? ???? ??? ??? ???? ??
Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
?? ?? ? ????(Probabilistic Retrieval Model) ? ??? ?? ? ??? ??? ??? ???? ??? ?? ? ???(relevant) ?? > ????(non-relevant) ?? ? ???? ? ?? ? ? ??? ??? ??? ?? ?? ????? ? ? ??? ?? ??? ??? ?? ??? ???? ??? ??? ??
?? ?? C c o n t ¨d ? ? ? ?(?) ? ? ?? ?(??) ? ? ? ? = , ? ?? ? = ?(?) ?(?) ? If ? ? ? ?(?) > ? ? ?? ?(??) Then D? ??(relevant)
P(D|R)? P(D|NR) ?? ? D=( d 1 , d 2 , ´, d t ) ? ?, ? ? ? ? ? = ?=1 ?(? ? |?) ? ? ? ? ?? = ?=1 ?(? ? |??) ? ?????? (Binar y Independence Model) ? ?? ?? ??? ?? ??? ? ??? ?? ?? 0(absence) ?? 1(presence)? ??
??? ??? ? ??? ??? ?? ????? ?? ? ??? = ?????? ?? ?(?|?) = ?(?|??) ? ? ? /(1 ? ? ? ) = ? ? 〜 ??? + ? ? ? /(1 ? ? ? ) ?=0
????? ?? ??? ? N?? ??? ??? ?? ???? ???? ???? ??? ?? ? ???? ????? ?? i? ?? r (+c) n-r (+c) N ?? i? ??? R-r (+c) N-n-R+r (+c) N-n ? R (+2c) N-R (+2c) N
????? ?? ??? C c o n t ¨d ? /? ? ?1 = ??? ?/? ? /? ? ?2 = ??? (??? )/(??? ) ? /(??? ) ? ?3 = ??? ?/(???) ? /(??? ) ? (????? +? ) ? ?4 = ??? = ??? (??? )/(????? +? ) (??? )(??? ) ? ? ? (?+ ? )(?????+?? ? +1) ? ?4( ) = ??? ? ? ? (???+ ? )(???+ ? +1) (?+0.5)(?????+?+0.5) ? ?4(.5) = ??? (???+0.5)(???+0.5)
??? ???? ??? ??? ?? ??? ? ??15 = ?4(.5) 〜 〜 ? 1 +?? ? 3 +??? ?? ??? ? ??11 = ?4(.5) 〜 ? 1 〜?? 〜 +?? ? 3 +??? ???? ?? (? 3 +1)??? ? ??25 = ?4(.5) 〜 ?? 〜 ?1 1?? +? ???? +?? ? 3 +??? ? ??25 ?? ?? ( ? 3 + 1 ) ? ?? ? ? ?? ? ?? = ? 4 (. 5 ) 〜 〜 + ?2 〜 ? ? ?? ? 3 + ? ?? ? ? ?? + ?? ?1 1? ? + ? + ?? ? ? ??
??? ???? ??? ??? C c o n t ¨d ? K 1 =1~2, b=0.75, k 3 =1~1000 ?? ?? ? ??? ??? ???+0.5 ? 1 +1 〜?? (? 3 +1)〜??? = 〜 ?? 〜 ?+0.5 ? 1 1?? +? ???? +?? ? 3 +??? ? ????? ?? 1+log (1+log ?? ) ?+1 ? ?? 〜 ??? 〜 ??? 1?? +? ? ????
Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
???? ?? ? ?? ???(language modeling) ? ???? ??, ??, ?? ?? ???? ?? ? ? ????, ????, ????, ???? ???? ?? ? ?? ???? ?? ? ???? ?? ? ????(regular grammar) ? ??????(context-free grammar) ? ????? ?? ??? ???? ??? ? ?? ????? ???? ??(NLP)? ?? ??? ? ?? ?? ? ???(corpus)?? ????? ??? ?? ? ??? ??? ?? ???? ??? ?? ????? ???
???? ?? C c o n t ¨d ? ? ? ? , ? ? , ´ , ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ´ ? ? ? ? ??? ? n-gram ?? ? ? ? ? ? ?1 , ? 2 , ´ , ? ? = ?(? ? |? ???+1 , ´ , ? ??1 ) ? ? ??? (?1 , ? 2 , ? 3 ) = ? ?1 ? ? 2 ?(? 3 ) ? ? ?? (?1 , ? 2 , ? 3 ) = ? ?1 ? ? 2 |?1 ?(? 3 |? 2 ) ☆ ????, ???? : 2 or 3-gram ?? ?? ☆ ???? : uni-gram ?? ??
???? ?? C c o n t ¨d ? Bayse ?? ? ? ? ?(?) ? ? ? ? = ? ? ?1 , ? 2 , ´ , ? ? = ?(?) ? Ponte & Croft (1998) ? ??? ????(multi-variate Bernoulli) ?? ?? ? ?? ?? ??? 1, 0?? ?? ? ? ? ? = ? ?1 , ? 2 , ´ , ? ? D = ?(? ? |?) + (1 ? ? ? ? ? ) ? Hiemstra (1998), Song & Croft (1999) ? ??? ???? ?? ? ? ?? ? ★ ?? ??? ??? ?? ? ? ?? ? ★ ??? ??? ??? ?? ? ? ? ? = ? ?1 , ? 2 , ´ , ? ? D = (?? ? ? ? + (1 ? ?)? ? ? ?
???? ?? - ?? ? ?? ? d1 = Google was better than Yahoo in terms of precision ? d2 = Google ranks pages by the pagerank algorithm ?? ? ?? ? ? ? ???? ? ? ?? ? = ?? ? ? ?? ( ??? ) ???? ? ? ? ???? ? ? ?? ? = ???? ?? 1 2 0 1 17 45 ? ? ? ?1 = 0.5 9 + 16 〜 0.5 9 + 16 = 144 〜 144 = 0.0037 1 2 0 1 15 11.5 ? ? ? ?2 = 0.5 7 + 16 〜 0.5 7 + 16 = 112 〜 112 = 0.0137

More Related Content

?7? ???? ??

  • 1. ???? ?7?. ???? ?? INFORMATION RETRIEVAL ??: ??? (timothy97@gmail.com) http://www.facebook.com/hhuIR Korea Maritime University Navis Control Inc.
  • 2. Over view ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
  • 3. ???? ?? ? ???? ??? ? ??? ??? ???? ???? ?? ? ???? ? ?? ??? ???? ???? ???(???)? ?? ? ???? ??? ? ??? ??? ??? ??(??, ??)? ???? ??
  • 4. Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
  • 5. ??? ???(Weight) ? ??? ???(weight) ? ???? ?? ??? ??? ? ?? ??? ?? ?? ? ???? ?? ? ??? ??? ??? ???? ???? ?? ? ???? ?? ? ?? ??? ???? ???? ??? ?? ??? ???? ??? ? ? ? ???? ?? ?? ? ???? ?????(normalization) ? ??? ??? ??? ????? ?? ? ??? ??? ?? ??? ???? ?? ?? ?? ??? ?
  • 6. tf * idf ? ?? ? TF (Term Frequency) : number of occurred term in a document ? DF (Document Frequency) : number of documents where term occurs ? IDF (Inverse Document Frequency) : Inverse DF ? Weight = TF * IDF ? TF? ??, DF? ???? ???? ???. ? ?????? ????? ???? ???? ???? ??. ?? ???? ???? term? ??? ??? ?? ??? ? ?? term? ??? ??? ??
  • 7. ????? ?? ? ????(Term frequency) ? b(binary) 1(??), 0(???) ? n(natural) tf ? ??? ? a(augmented) ?+ ??? ? ?? ? l(logarithm) 1 + log ?? tf (term frequency): ???? ?? ? ?? t? ?? ??? ??
  • 8. ????? ?? C c o n t ¨d ? ????(Document frequency) ? n(no) 1 ? ? c(cosine) log ? ? ? ?(+0.5) ? p(prob idf ) log ?(+0.5) N : DB? ???(??) ? ? n : DB? ?? t? ???? ?? ?
  • 9. ????? ?? C c o n t ¨d ? ???? ???(Document length normalization) ? n(no) 1 1 ? c(cosine) ?2 ? ?? ? a(?? tf ???) 1 ? ?? + ?? 〜 max ?? ? + 1 〜 ?? ? b(byte?? ???) ?? ? 1 ? ? + ? 〜 ??????? ?? + ?? 1 ? u(?????? ???) 1.0 ? ????? 〜 ????? + ????? 〜 # ?? ?????? ????? dl : ??? ???? ?? ?(????) (average dl? ??????) n : DB? ?? t? ???? ?? ?
  • 10. ????? ?? ???? ? ??(?? ??) ? ?????(tf )? ?? ? bnn 1 ? nnn tf ? lnn log ?? + 1.0
  • 11. ????? ?? ???? C c o n t ¨d ? ??? ???(idf )? ?? ? ? btn log ? ? ? ? + 0.5 ? bpn log ? + 0.5
  • 12. ????? ?? ???? C c o n t ¨d ? ??(?? ??) ? ????? 〜 ??? ??? ?? ? ? ntn ?? 〜 log ? ?? ? ? atn 0.5 + 0.5 〜 max 〜 log ?? ? ?+1 ? dtn 1 + log(1 + log ??) 〜 ?
  • 13. ????? ?? ???? C c o n t ¨d ? ??? log(??)+1.0 ? lnc (log ??+1.0) 2 ? ??〜log ? ntc ? ? 2 ??〜log ? ? (log ??+1.0)〜log( ? ) ? ltc 2 ? log ??+1.0 〜log ? ?? 0.5+0.5〜 ? anc max ?? ?? 2 0.5+0.5〜 max ??
  • 14. ????? ?? ???? C c o n t ¨d ?? ? 0.5+0.5〜 〜log ? atc max ?? ? ?? 2 ? 2 0.5+0.5〜 max ?? 〜 log ? 1.0 + log ?? 1.0 + log(????) ? lnu 1.0 ? ????? 〜 ????? + ????? 〜 # ?? ?????? ????? ? (1.0+log ??)〜 log ? ? ltu 1.0 ? ????? 〜 ????? + ????? 〜 # ?? ?????? ????? 1 + log(1 + log ??) ? dnb ?? (?? ????) 0.8 + 0.2 〜 ???? (?? ????) ?? ? ? ? + 0.5 ? npb ?? 〜 log ? + 0.5 2 〜 0.25 + 0.75 〜 ???? + ??
  • 15. Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
  • 16. ???? ?? ? ??? ???? ?? ? ???? ??? ????? ??? ??? ??? ???? ?? ? ?? ?? ?? ? ????? ??? ?? ? ??? ???? ???? ??? ??? ? ?? ? ??(binary) ??? : ??(1) or ???(0) ? ???? ?? ? Vector Model = Vector Space Model = Term Vector Model ? ??? ??? ?? ?? ? ?? ??(partial matching) ?? ? ??? ??? ???(similarity)? ???? ??? ?? ? Cosine ???
  • 17. ???? ?? C c o n t ¨d ? ??? ???? ?? ? n ?? ????? ???? ?? ? n-??? ?? ???? ?? ? ??(term)? ?? ????? ? (axe)? ?? ? ??? ?? ???? ? ?? ? ???. ? ? ???(Very high- dimensional) ?? ? ????? ?? ? 1000?- dimension ??? ?? ?? ??, sparse-vector: ??? ? ??? 0(zero)? ? ? = (?1? , ?1? , ? , ? ?? )
  • 18. ???? ?? C c o n t ¨d ? ??? ???? ?? ? Key idea 1: ??? ?? ?? ???? ??? ?? ? Key idea 2: ?? ?? ??? ??? ?? ???? ?? ??? ? ???(proximity) = ??? ???(similarity) ? ??? ??? ?? ?? ? ? ? = (?1? , ?2? , ? , ? ?? ) ? ? = (?1? , ?2? , ? , ? ?? ) ? TF * IDF ???? ?? ??
  • 19. ???? ?? C c o n t ¨d ? ?? ? ???? ???? ?? ??/ 1 2 3 4 5 6 7 ´ n ??? term ?? ?? ???? ?? ??? ?? ??? ???? ??1 1 1 0 1 0 0 1 0 ??2 1 0 1 1 0 0 0 0 ??3 0.8 0 0.5 0.9 0 0 0 0 ??4 0.5 0.3 0.9 0.7 0 0 0 0 ??? 1 1 0 0 1 0 0 0 0 ??? 2 0.9 0 0 0.8 0 0 0 0
  • 20. Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
  • 21. ??? ??? ??? ? Euclidean distance ? ? ?? d 1 (w 11 , w 12 ), d 2 (w 21 , w 22 ) ??? ?? = (?21 ? ?11 ) 2 +(?22 ? ?12 ) 2 ? ??? ??? ? ??? ???? ?? ? ???? ?? ? ??? ??? ?? ??? ? ??? ???? ?? ? ?) S(q, d 2 ) vs. S(q, d 1 ) ? ??? ?????.
  • 22. ???? ???? ??? ??? ? Length Normalization ? ?? ?? ??? ??? 1? ?? ??? ?? ??? ?? 1 ?? 2 ??? ?? 1 ?? 2 a 5 0 a 5/8.367=0.598 0 b 3 5 b 3/8.367=0.359 5/5.477=0.913 c 6 2 c 6/8.367=0.717 2/5.477=0.365 d 0 1 d 0 1/5.477=0.183 ??? ????? ??? ????? ?? 1? ????? ?? = 52 + 32 + 62 = 8.367 ?? 2? ????? ?? = 52 + 22 + 12 = 5.477 ? ???? ????? ??? ??? ? ??? ? 1 , ? 2 = 0.359 〜 0.913 + 0.717 〜 0.365 = 0.589
  • 23. ???? ??? ??? ?? ? ??? ?? ? ? ?? ??? ?(angle)? ????? ????. ? ? ?, ?? ?? ??? ?? Consine ?? ????. ?1 ??2 ? ???? = ?1 ?2 ? ?=1 (? 1? 〜? 2? ) ? ??? ? 1 , ? 2 = ? ? 1? 〜 ??=1 ? 2? 2 2 ?=1
  • 24. ???? ??? ??? ?? C c o n t ¨d ? ?? ? D 1 = (?????2, ??1, ??1, ??1) ? Q = (?????1, ??????1, ??1, ??1) ?assume, (t 1 , t 2 , t 3 , t 4 , t 5 ) = (??, ??????, ??, ??, ?????) ? D 1 = (1, 0, 1, 1, 2) ? Q = (1, 1, 0, 1, 1) 1〜1+1〜1+2〜1 ? cos ?1 , ? = ??? ?1 , ? = = 0.76 (12 +12 +12 +2 2 )〜(12 +12 +12 +12 ) ? ??? ??????? ???? ????? ?
  • 25. ??? ??? C ?? ? ??? ???? ?? ??? ?? ??: http://mwultong.blogspot.com
  • 26. Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
  • 27. ????? ?? ??? ??? ? ?? ???(inter val data) ? ????? ??(Euclidean distance) ? ? ?, ? = ? (? ? ? ? ? )2 ? ?? ????? ?? ? ? ?, ? = ? (? ? ? ? ? )2 ? ??(block) ?? ???(Manhattan) ?? ? ? ?, ? = ? ?? ? ?? ? ????? ??(Minkowski metric) 1 ? ? ? ?, ? = ? ?? ? ?? ?
  • 28. ????? ?? ??? ??? C c o n t ¨d ? ?? ???(inter val data) ? ??? ????(Pearson correlation coefficient) ? (? ? ?? )(? ? ?? ) ? ? ?, ? = 2〜 2 ? (? ? ?? ) ? (? ? ?? ) ? ??? ??(Cosine coefficient) ? (? ? ? ?) ? ? ?, ? = ? ? ?2〜 ? ? ?2 ? ?? ??(Vector ?? Inner product) ? ? ?, ? = ? (? ? ? ?)
  • 29. ????? ?? ??? ??? C c o n t ¨d ? ?? ???(binar y data) ??(??)?? ?? t ?? ??? ?? a b ???? ?? t ??? c d ? ????? ?? ? ?, ? = ?+ ? (???) 2 ? ?? ?? ? ?, ? = (?+?+?+?) 2 (?+?) ? ?? ? ?, ? = 4(?+?+?+?) ?+? ? ??/?????? ? ?, ? = 2?+?+?
  • 30. ????? ?? ??? ??? C c o n t ¨d ? ?? ???(binar y data) ?+? ? ???? ?? S ?, ? = ?+?+?+? ? ? ??/?? ?? S X, Y = ?+?+?+? ? ? ??? ?? S X, Y = ?+?+? 2? ? ??? ?? S X, Y = 2?+?+? ?+? ? ???/???? ?? S X, Y = ?+?+2(?+?) ??? ?? ? ?? Y S X, Y = ??+ ?? ?? ??? ? ?? Q S X, Y = ??+?? ? ? ???? ?? S X, Y = (?+?)〜 (?+?)
  • 31. ????? ?? ??? ??? C ?? ? ??? ??? ??? ?? ?? ? ?? D i = (3, 2, 1, 0, 0, 0, 1, 1) ? ?? Q = (1, 1, 1, 0, 0, 1, 0, 0) ? 2 ?=1 (? ?? 〜? ?? ) 2〜6 ? ??? ?? = ? ? = =1 ?=1 ? ?? + ?=1 ? ?? 8+4 (? ?? 〜? ?? ) 6 ? ??? ?? = = =1 ? ?? + ? ?? ? (? ?? 〜? ?? ) 8+4?6 (? ?? 〜? ?? ) 6 6 ? ??? ?? = = = 16〜4 8 (? ?? ) 2 〜 (? ?? ) 2
  • 32. ???? ??? ??? ? ?? ? ???(Similarity) ???? ????? ???? ??? ? ???? ??? ??? ???? ???? ?? ? ?? ? ??? ??? ?? ????? ????? ???? ??? ???? ?? ? ??? ?? ??? ??? ??? ??? ?? ? ?? ??? ?? ?? ? ???? ??(Cluster Model) ?? ? ?????(Inverted index file)? ???? ?? ??? ????? ???? ??? ??? ???? ??
  • 33. Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
  • 34. ?? ?? ? ????(Probabilistic Retrieval Model) ? ??? ?? ? ??? ??? ??? ???? ??? ?? ? ???(relevant) ?? > ????(non-relevant) ?? ? ???? ? ?? ? ? ??? ??? ??? ?? ?? ????? ? ? ??? ?? ??? ??? ?? ??? ???? ??? ??? ??
  • 35. ?? ?? C c o n t ¨d ? ? ? ?(?) ? ? ?? ?(??) ? ? ? ? = , ? ?? ? = ?(?) ?(?) ? If ? ? ? ?(?) > ? ? ?? ?(??) Then D? ??(relevant)
  • 36. P(D|R)? P(D|NR) ?? ? D=( d 1 , d 2 , ´, d t ) ? ?, ? ? ? ? ? = ?=1 ?(? ? |?) ? ? ? ? ?? = ?=1 ?(? ? |??) ? ?????? (Binar y Independence Model) ? ?? ?? ??? ?? ??? ? ??? ?? ?? 0(absence) ?? 1(presence)? ??
  • 37. ??? ??? ? ??? ??? ?? ????? ?? ? ??? = ?????? ?? ?(?|?) = ?(?|??) ? ? ? /(1 ? ? ? ) = ? ? 〜 ??? + ? ? ? /(1 ? ? ? ) ?=0
  • 38. ????? ?? ??? ? N?? ??? ??? ?? ???? ???? ???? ??? ?? ? ???? ????? ?? i? ?? r (+c) n-r (+c) N ?? i? ??? R-r (+c) N-n-R+r (+c) N-n ? R (+2c) N-R (+2c) N
  • 39. ????? ?? ??? C c o n t ¨d ? /? ? ?1 = ??? ?/? ? /? ? ?2 = ??? (??? )/(??? ) ? /(??? ) ? ?3 = ??? ?/(???) ? /(??? ) ? (????? +? ) ? ?4 = ??? = ??? (??? )/(????? +? ) (??? )(??? ) ? ? ? (?+ ? )(?????+?? ? +1) ? ?4( ) = ??? ? ? ? (???+ ? )(???+ ? +1) (?+0.5)(?????+?+0.5) ? ?4(.5) = ??? (???+0.5)(???+0.5)
  • 40. ??? ???? ??? ??? ?? ??? ? ??15 = ?4(.5) 〜 〜 ? 1 +?? ? 3 +??? ?? ??? ? ??11 = ?4(.5) 〜 ? 1 〜?? 〜 +?? ? 3 +??? ???? ?? (? 3 +1)??? ? ??25 = ?4(.5) 〜 ?? 〜 ?1 1?? +? ???? +?? ? 3 +??? ? ??25 ?? ?? ( ? 3 + 1 ) ? ?? ? ? ?? ? ?? = ? 4 (. 5 ) 〜 〜 + ?2 〜 ? ? ?? ? 3 + ? ?? ? ? ?? + ?? ?1 1? ? + ? + ?? ? ? ??
  • 41. ??? ???? ??? ??? C c o n t ¨d ? K 1 =1~2, b=0.75, k 3 =1~1000 ?? ?? ? ??? ??? ???+0.5 ? 1 +1 〜?? (? 3 +1)〜??? = 〜 ?? 〜 ?+0.5 ? 1 1?? +? ???? +?? ? 3 +??? ? ????? ?? 1+log (1+log ?? ) ?+1 ? ?? 〜 ??? 〜 ??? 1?? +? ? ????
  • 42. Outline ? ??? ??? ? ???? ?? ? ???? ??? ??? ?? ? ????? ?? ??? ??? ? ???? ???? ??? ?? ? ?? ?? ? ???? ??
  • 43. ???? ?? ? ?? ???(language modeling) ? ???? ??, ??, ?? ?? ???? ?? ? ? ????, ????, ????, ???? ???? ?? ? ?? ???? ?? ? ???? ?? ? ????(regular grammar) ? ??????(context-free grammar) ? ????? ?? ??? ???? ??? ? ?? ????? ???? ??(NLP)? ?? ??? ? ?? ?? ? ???(corpus)?? ????? ??? ?? ? ??? ??? ?? ???? ??? ?? ????? ???
  • 44. ???? ?? C c o n t ¨d ? ? ? ? , ? ? , ´ , ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ´ ? ? ? ? ??? ? n-gram ?? ? ? ? ? ? ?1 , ? 2 , ´ , ? ? = ?(? ? |? ???+1 , ´ , ? ??1 ) ? ? ??? (?1 , ? 2 , ? 3 ) = ? ?1 ? ? 2 ?(? 3 ) ? ? ?? (?1 , ? 2 , ? 3 ) = ? ?1 ? ? 2 |?1 ?(? 3 |? 2 ) ☆ ????, ???? : 2 or 3-gram ?? ?? ☆ ???? : uni-gram ?? ??
  • 45. ???? ?? C c o n t ¨d ? Bayse ?? ? ? ? ?(?) ? ? ? ? = ? ? ?1 , ? 2 , ´ , ? ? = ?(?) ? Ponte & Croft (1998) ? ??? ????(multi-variate Bernoulli) ?? ?? ? ?? ?? ??? 1, 0?? ?? ? ? ? ? = ? ?1 , ? 2 , ´ , ? ? D = ?(? ? |?) + (1 ? ? ? ? ? ) ? Hiemstra (1998), Song & Croft (1999) ? ??? ???? ?? ? ? ?? ? ★ ?? ??? ??? ?? ? ? ?? ? ★ ??? ??? ??? ?? ? ? ? ? = ? ?1 , ? 2 , ´ , ? ? D = (?? ? ? ? + (1 ? ?)? ? ? ?
  • 46. ???? ?? - ?? ? ?? ? d1 = Google was better than Yahoo in terms of precision ? d2 = Google ranks pages by the pagerank algorithm ?? ? ?? ? ? ? ???? ? ? ?? ? = ?? ? ? ?? ( ??? ) ???? ? ? ? ???? ? ? ?? ? = ???? ?? 1 2 0 1 17 45 ? ? ? ?1 = 0.5 9 + 16 〜 0.5 9 + 16 = 144 〜 144 = 0.0037 1 2 0 1 15 11.5 ? ? ? ?2 = 0.5 7 + 16 〜 0.5 7 + 16 = 112 〜 112 = 0.0137