課程名稱︰機率 課程性質︰系必修 課程教師︰林守德 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2010.6.24 考試時限（分鐘）：180 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Probability2010 Final (Prof. Shou-de Lin) 6/24/2010 14:30-17:30pm Total Points: 120 You can answer in either Chinese or English. 1.Please briefly describe the following concepts(16pts): (a)cheby shev's inequality (b)Law of large number (c)Noisy Channel Model (d)Prior, Likelihood function, Posterior 2.Given discrete random variables X and Y are independent, is X^2 and Y^2 also independent? Please explain your answer(7 points) 3.(Central Limit Theorem)(12 pts) (a)A fair coin is rossed 50 times. Use the central limit theorem to estimate the probability that fewer than 20 of those tosses come up heads. (b)A fair coin is tossed until it comes up heads for the 20th time. Use central limit theorem to estimate the probability that more than 50 tosses are needed. 4.Prove H(X,Y|Z) = H(Y|X,Z) + H(X|Z) (7 pts) 5.Here is a database of Market-Basket transactions. Assuming min_support = 0.4 and min+confidence = 2/3 ┌──┬─────────────┐ │ TID│ Items │ ├──┼─────────────┤ │1 │Bread, Milk │ ├──┼─────────────┤ │2 │Bread, Diaper, Beer, Eggs │ ├──┼─────────────┤ │3 │Milk, Diaper, Beer, Coke │ ├──┼─────────────┤ │4 │Bread, Milk, Deaper, Beer │ ├──┼─────────────┤ │5 │Bread, Milk, Diaper, Coke │ └──┴─────────────┘ (a)The rule Milk->Bread satisfies both min_support and min_confidence, but it should not be considered as a good association rule. Can you explain why? (6 pts) (b)Please list 2 good association rules and show their corresponding confidence and support.(6 pts) 6.Given a web structure as follows:(Each node denotes a web page, the number corresponds to its initial PageRank(PR). Each link denotes a hyperlink) A -----------> C <-- 0.1 <----------- 0.8 | | | | | | | --> B ----------------- 0.1 (a)Please write down the equation for PR(A), PR(B) and PR(C) (4 pts) (b)Caculate their PageRank values for A, B, C after one step update. (3 pts) 7.If X1...Xn are iid and uniformly distributed between [θ1, θu], please find the maximum likelihood estination ofθ1 and θu (8 pts) 8.If X1...Xn are iid and Possion(λ),use MLE to find the estimator of λ(5 pts) 9.A dog walks on the integers, pssibly reversing direction at each step with probability p = 0.1 . Let Xi be the ith porition of the dog, and X0 = 0 (starts at origin). The first step is equally likely to be positive or negative. For example, a walk might look like this: (X0, X1, X2, ...) = (0, -1, -2, -3, -4, -3, -2, -1, 0, 1) Here the dog reverses its direction after X4. (a)Find H(X0, X1, X2, ... Hn) (9 pts) (b)What is the expected number of steps the dog takes before reversing direction? (5 pts) 10.A playoff consists of a three-game series that terminates as soon as either team wins two games. Let X be the random variable that represents the outcome of a playoff between teams A and B; examples of possible values of X are AA and BAB. Let Y be the number of games played before the winner can be decided, which ranges from 2 to 3. (a)Assuming that A and B gave equal chance to win and that the games are independent, calculate H(X), H(Y), H(Y|X), H(X|Y). (8 pts) (b)Let Z denote the winning team. Find H(Z), H(X|Z), H(Z|X). (6 pts) 11.You are given four documents of unknown language as below. D1:homme(K1), cuisinier(K2), le(K3), beefsteak(K4), cuisine(K8) D2:le(K3), poele(K6), le(K3), cuisine(K8) D3:homme(K1), examen(K5), professeur(K7) D4:gagnant(K9), examen(K5), le(K3), examen(K5) (log2 1.333 = 0.415, log2 2.333 = 1.222, log2 3 = 1.585, log2 3.333 = 1.737, log2 5 = 2.322, log2 6 = 2.585) (a)Find the top 2 step word using IDF measure (2 pts) (b)Represent D1 and D4 using a TF-IDF vector. Each dimension corresponds to one indexed term(normalize TF by maximum TF) (4 pts) (c)Please calculate the similarity between D1 and D4 using dot-product and cosine distance, you only need write the equaton and no need to calculate the final output (4 pts) 12.In a Lottery, each weekday a three-digit integer is generated one digit at a time. Let pi denote the probability of generation digit i, i = 0,1,...,9. Let α = 0.05, and use the following 50 digits to test whether p0 = p1 = ... = p9 = 1/10 (H0: p0 = p1 = ... = p9 = 1/10) (8 pts) ┌───┬─────┐ │digit │frequency │ ├───┼─────┤ │0 │2 │ ├───┼─────┤ │1 │6 │ ├───┼─────┤ │2 │3 │ ├───┼─────┤ │3 │4 │ ├───┼─────┤ │4 │9 │ ├───┼─────┤ │5 │5 │ ├───┼─────┤ │6 │7 │ ├───┼─────┤ │7 │4 │ ├───┼─────┤ │8 │6 │ ├───┼─────┤ │9 │4 │ └───┴─────┘ Normal Distribution Chi Square Distribution Table --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.89