数学之美 * October 2, 2010 * 1
数学 数学 数学之美 Google 数学 Google 1 (Statistical Language Models) Google 学 - 学 Noam Chomsky 学 数学 (Claude Shannon) 数学 数学 (Fred Jelinek) IBM 学 (Sabbatical Leave) 学 S w 1, w 2,, w n S S 数学 S P(S) S P (S) P (S) = P (w 1 )P (w 2 w 1 )P (w 3 w 1, w 2 ) P (w n w 1, w 2 w n 1 ). P (w 1 ) w 1 P (w 2 w 1 ) w n wi w i 1 ( S P (S) = P (w 1 )P (w 2 w 1 )P (w 3 w 2 ) P (w i w i 1 ), ( N-1 2
P (w i w i 1 ) 数 数 (w i 1, w i ) w i 1 数 P (w i w i 1 ) = P (w i 1, w i )/P (w i 1 ) 数学 学 Google 美 (NIST) Google 数学 美 之 997 20 学 数学 学 Google 2 美 / / / / / 美 / / / / / 学 学 数 数 - - - - 学 - 学 - 学 - - 学 90 学 数 数学 3
S A 1, A 2, A 3,, A k, B 1, B 2, B 3,, B m, C 1, C 2, C 3,, C n, A 1, A 2, B 1, B 2, C 1, C 2 A 1, A 2,, A k P P (A 1, A 2, A 3,, A k ) > P (B 1, B 2, B 3,, B m ), P (A 1, A 2, A 3,, A k ) > P (C 1, C 2, C 3,, C n ). Dynamic Programming Viterbi 学 学 学 学 学 学 学 学 Computational Linguistics 学 学 学 Google 之 数学 Google 1. 2. 3. Critical Tokenization and its Properties 4. Chinese word segmentation without using lexicon and hand-crafted training data 4
3 数学 之 数学 之 s 1, s 2, s 3, o 1, o 2, o 3 o 1, o 2, o 3, s 1, s 2, s 3, 学 Hidden Markov Model o 1, o 2, o 3 s 1, s 2, s 3 数学 o 1, o 2, o 3, P (s 1, s 2, s 3, o 1, o 2, o 3, ) s 1, s 2, s 3, 数 P (o 1, o 2, o 3, s 1, s 2, s 3, ) P (s 1, s 2, s 3, ). P (o 1, o 2, o 3, s 1, s 2, s 3, ) s 1, s 2, s 3, o 1, o 2, o 3,, P (s 1, s 2, s 3, ) s 1, s 2, s 3, s 1, s 2, s 3, 数 s 1, s 2, s 3, 1. s 1, s 2, s 3, s i s i 1 2. i o i s i, P (o 1, o 2, o 3, s 1, s 2, s 3, ) = P (o 1 s 1 ) P (o 2 s 2 ) P (o 3 s 3 ) 5
Viterbi s1, s2, s3, 之 s 1, s 2, s 3, s 1, s 2, s 3, o 1, o 2, o 3, o 1, o 2, o 3, P (o 1, o 2, o 3, s 1, s 2, s 3, ) 学 (Acoustic Model) (Translation Model) (Correction Model) P (s 1, s 2, s 3, ) Baum 60 IBM Fred Jelinek ( ) 学 Jim and Janet Baker ( ) ( 30% 10%) Sphinx 学 学 数学 之 4? :Google 1948 (shāng)? 1 32 1-16? 1-8? 9-16 6
bit 数, 数 数 数 log log 32 = 5, log 64 = 6 美 32 数 (p 1 log p 1 + p 2 log p 2 + + p 32 log p 32 ). p 1 p 2,, p 32 32 (Entropy) H 32 数学 X H(X) = x P (x) log 2 [P (x)]. 7000 13 13 数 10% 95% 8-9 5 250 320KB 1MB 数 redundancy) 250 数 学 7
5 之美 数 [ Google Page Rank ( ) 数 George Boole) 学数学 数学 之 数学 数学 1854 An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities 数学 数 1 TRUE ) 0 FALSE ) AND) (OR) NOT) AND-NOT AND 1 0 1 1 0 0 0 0 AND 0 0 1 1 (0), 1 0 OR 1 0 1 1 1 0 1 0 OR 1 1 0 0 0 1 1 NOT 1 0 0 1 NOT 1 0 0 1 1 0 数学 数 80 1938 数 数 数 数学 8
TRUE, 1 FALSE, 0 AND AND (NOT ) - - - True False 数 之 数 数 1 0 数 0100100001100001 数 之 数 0010100110000001 数 AND 0000100000000001 数 数 1 数 数 数 Alta Vista 学 3-5 数 之 Shards) 数学 9
6 (Web Crawlers) [ 数学 数学 学 数学 数 数 数 (Web Crawlers) 之 Google Trends 数学 数学 ] Traverse) 数学 Leonhard Euler 1736 Konigsberg 学 BFS) DFS) Hyperlinks) Robot) 学 (MIT) 学. Matthew Gray) 1993 10
( www wanderer ) (Hash Table) Google 数 200 200 634 7 (Fred Jelinek) (Perplexity) Sphinx 997 997 60 20 Mutual Information) Kullback-Leibler Divergence) Bush 美 美 Kerry Kerry 11
美 Bush (Gale) (Church) (Yarowsky) 学 (Mitch Marcus) Kullback-Leibler Divergence 数 数 - TF/IDF) TF/IDF TF/IDF 数学 学. (Thomas Cover) (Elements of Information Theory) 1 2 8. (Fred Jelinek) 学 学 学 学 D 学 学 A 1949 美 美 学 学 学 8 学 学 学 12
学 学 Roman Jakobson ( [ ] 学 (Noam Chomsky) 学 学 学 之 学 学 学 学 IBM 学 学 学 1972 IBM IBM T.G. Watson Labs 学 IBM 之 IBM Bahl Dragon (Della Pietra) BCJR (Cocke) (Raviv) IBM Google, 学 学 学 美 BCJR 数 之 IBM IBM 之 Amaden BCJR IBM IBM 学 IBM IBM 学 IBM 数 学 CLSP 20-30 学 学 CLSP CLSP 之 学 学 学 学 学 学 学 学 学 学 学 IBM, AT&T Google 13
学 学 学 学 学 美 学 学 Pascale 学 学 学 1 2 3 4 5 6 9 [ (Page Rank) 学 ] 数 数 数 Term Frequency) 14
2 35 5 0.002 0.035 0.005 数 0.042 w 1, w 2,, w N :T F 1, T F 2,, T F N TF: term frequency) :T F 1 + T F 2 + + T F N 10 83 数 Google 15
学 学 学 AT&T 学 Mohri, Pereira Riley C AT&T 学 AT&T AT&T 学 学 Google AT&T C 学 学 AT&T 11 Google 47.. Nicolas Cage) 之 Lord of War) 47( AK47) ( 47 ( Google. (Amit Singhal) Google 47 Google Google Matt Cutts Spam) 学 学 美 数 40% Google 16
1 2 3 4... 789... 64000 47 debug) 之 (Salton) AT&T 数 AT&T Google Google Google AT&T 学 Google Google 学 2005 学 40 美 RAID) (Randy Katz) 12 Google 数 数 TF/IDF / TF/IDF) TF/IDF TF/IDF 64,000 TF/IDF 17
TF/IDF 1 0 2 0.0034 3 0 4 0.00052 5 0... 789 0.034... 64000 0.075 64,000 数 64,000 之 学 数 a, b c A, B C A cos A = b2 + c 2 a 2 2bc b c cos A = a b a b b c X Y x 1, x 2,, x 64000 y 1, y 2,, y 64000 cos θ = x 1 y 1 + x 2 y 2 + + x 64000 y 64000 x 2 1 + x 2 2 + + x 2 64000 y. 1 2 + y2 2 + + y64000 2 学学 数学 18
13 数 Fingerprint) URL) Google 数学之美 http://www.baidu.com/s?ie=gb2312&bs=%ca%fd%d1% A7%D6%AE%C3%C0&sr=&z=&cl=3&f=8&wd=%CE%E2%BE%FC+%CA%FD%D1%A7%D6%AE% C3%C0&ct=0 200 2 TB GB 50% 4TB 数 200 128 16 数 数 893249432984398432980545454543 16 1/6 16 数 Fingerprint) 数 128 数 数, 数 prng) prng 之 数 数 数 1001 9 01010001 ( 81 0100 数 MersenneTwister,, Cookie cookie cookie MersenneTwister 数 数 csprng) MD5 SHA1 128 160 数 SHA1 19
14 数学 [ 数学之美 数学 Google 学 学 学 之 美 之 学 20
8-10 学 学 数 数 学 学 学 Verrier Google 1. 数学 2. 3. 数 4. / 数 TF/IDF) page rank) 15 数学之美 学 美 学 (Michael Collins) 21
15.1 美 (Mitch Marcus) 学 学 学 (MIT) 数 数 (sentence parser) (Eric Brill) Ratnaparkhi Eisnar 数学 美 AT&T AT&T MIT MIT 学 15.2 美 (Eric Brill) 学 学 学 (transformation rule based machine learning) chang 学 美 (part of speech tagging) Google 学 学 Google Google 之 22
16 [ 数学 (the maximum entropy principle) ] Google 学 wang-xiao-bo ( ) 学 学 数学 (maximum entropy) AT&T 1/6 之 1/3 2/15 1/3 之 23
wang-xiao-bo 学 数学 Csiszar 数 数 w 3 w 1 w 2 subject P (w 3 w 1, w 2, subject) = e{λ 1(w 1,w 2,w 3 )+λ 2 (subject,w 3 )} Z(w 1, w 2, subject) 数 lambda Z 数 之 数 数 数 数 数 数 GIS(generalized iterative scaling) GIS 1. 2. N 数 数 3. 2 GIS Darroch Ratcliff 数学 Csiszar) Darroch Ratcliff GIS 64 GIS (Della Pietra) IBM GIS IIS improved iterative scaling 数 IBM 24
数学 美 学 美 学 IBM (Adwait Ratnaparkhi) 之 学 学 数学 IIS 数 (language model) 20 SUN Google IBM 学 IBM (hedge fund) - (Renaissance Technologies) 学 数学 1988 34% 1988 200 Berkshire Hathaway) 16 数学 数学 17 (Search Engine Anti-SPAM) (SPAM) 25
数 数 (page rank) Google Google Matt Cutts Google ( Google 数 学 数学 26
Google ( 18 学学 数 数 学 学 学 学 数学 数 Singular Value Decomposition SVD) A A = a 11 a 1j a 1N a i1 a ij a in a M1 a Mj a MN M=1,000,000 N=500,000 i j j i TF/IDF) X B Y 数 1.5 之 数 X 数 Y 27
之 A w 数 数 Google MapReduce Google Google Google 19 (Bayesian Networks) (Markov Chain) 之 之 之 28
(belief) (belief networks) 之 之 数 数 NP-complete IBM Watson (Geoffrey Zweig) 学 (Jeff Bilmes) 之 Google Google 20 学 (Mitch Marcus) 学 AT&T 学 学 LDC 学 数 数 数 (corpus) 数 学 美 学 DARPA 学 数 PennTree Bank PennTree Bank 29
LDC 学 数 LDC 之 学 try-and-error 学 学 学 bioinformatics ( 学 学 学 学 学 学 学 学 学 21 Bloom Filter FBI hash table Yahoo,Hotmail Gmai email spamer email email 1.6GB email googlechinablog.com/2006/08/blog-post.html 50 数学 1/8 1/4. 数 X 数 F 1, F 2,, F 8 f 1, f 2,, f 8 数 G 1 30
数 g 1, g 2,, g 8 email email Y 数 F 1, F 2,, F 8 s 1, s 2,, s 8 t 1, t 2,, t 8 Y t 1, t 2,, t 8 之 之 22 学 数学 学 学 数学 http://ent.sina.com.cn/v/2005-10-17/ba866985.shtml 学 EBKTBP CAESAR 学 31
A B C E B A D F E K R P S T 0543 0543 0543 3737 2947 数 学 美 美 AF 美 美 美 AF 美 AF 美 学 美 学 学 之 数学 Caesar 数 Ascii X=099097101115097114 1. 数 数 P Q 100, N = P Q, M = (P 1) (Q 1) 2. M 数 E M E 1 数 3. 数 D E D M 1 E D mod M = 1 4. E 32
D N X Y X K mod N = Y D Y X D Y X Y D mod N = X 1. 2. N,E D, 3. E D N 数 N P Q P Q 数 P Q 50 RSA-158 数 39505874583265144526419767800614481996020776460304936454139376051579355 62652945068360972784246821953509354430587049025199565533571020979922648 4977949442955603 = 3388495837466721394368393204672181522815830368604993 048084925840555281177 116588234066712599031483765583832708181310122581 46392600439520994131344334162924536139 数 N N=P Q 33
P Q 之 数?? 学?? game theory 数学 数 23 6700 26 676 6700 p 1, p 2, p 3,, p 6700 L 1, L 2, L 3,, L 6700 p 1 L 1 + p 2 L 2 + + p 6700 L 6700 GBK http://www. googlechinablog.com/2006/04/4.html H = p 1 log p 1 p 6700 log p 6700 26 log 26 = 4.7 10/4.7 = 2.1 8 8/4.7=1.7 http://www.googlechinablog.com/2006/04/blog-post.html 6 6/4.7 = 1.3 学 学 34
之 数 2.98 数 100 http : //tools.google.com/pinyin/ 24 Google T-Mobile HTC Android 3G 学 Dynamic Programming 之 shortest path 数 数 数 数 数 数 数 35
数 Dynamic Programming programming 数学 -> -> -> -> -> -> 10 10 15 10 15 Y 1, Y 2, Y 3,, Y N W 11, W 12, W 13 Y1 W 21, W 22, W 23, W 24 Y2 36
数学 数学 37
38