課程名稱︰多變量統計分析 課程性質︰應數所數統組必修 課程教師︰陳宏 開課學院：理學院 開課系所︰數學系 考試日期（年月日）︰2016/6/15 考試時限（分鐘）：15:30~17:50 試題 : 1. (40%) Kernel funcitons implicitly define some mapping function ψ(‧) that p transforms an input instance x∈R to high dimensional space Q by giving the form of inner product in Q : K(x ,x )=<ψ(x ),ψ(x )>. i j i j 1 2 Assume we use radial basis kernel function K(x ,x )=exp(-——||x -x || ). i j 2 i j Prove that for any two input instances x and x , the squared Euclidean i j distance of their corresponding points in the feature space Q is less than 2 2, i.e. prove that ||ψ(x )-ψ(x )|| ≦ 2. i j 2. (30%) Given n training examples (x ,x ), i,j-1,...,n, the kernel matrix A i j is an n ×n square matrix, where A(i,j)=K(x ,x ). Prove that the kernel i j matrix A is semi-positive definite. (Hint: Recall that K(x ,x )=<ψ(x ) i j i ,ψ(x )> as stated in Question 1.) j Questions 1 and 2 are used to examine whether you know What is the kernel trick? p 3. (40%) Consider the set of all closed balls in R , that is sets of the form p 2 2 p {x∈R : ||x-x || ≦r } for some x ∈R and r≧0 is less than or equal to 0 0 p+2. Hint: Convert it into the form of hyperplane in terms of x ,x ,...,x 1 2 p 2 and Σx . i i 4. (30%) When p=2, a square that assigns points within as one class and points outside as another class. Draw a scenario where this classifier shatters all points for the VC dimension you have proposed. Questions 3 and 4 are used to examine whether you know How to find out the complexity of your learner? 5. (50%) (Chernoff Bound) Let X ,X ,...,X be independent random variables, 1 2 n n each receiving the values {-1,1} with probability 1/2. Define S =Σ X . n i=1 i Show that, for any real number t>0, 2 P(S ≧t)≦exp(-t /2n). n 2 6. (40%) Consider logistic regression with (x ,y )∈R , 1≦i≦n, in which i j log p(x)/[1-p(x)] = β+βx. Note that both |β| and |β| are bounded above 0 1 0 1 by 1. For simplicity, consider x =i/n. Prove that the mle of (β,β) is i 0 1 consistent under the setting x =i/n as n goes to the infinity. in Questions 5 and 6 are designed to examine whether you know trick to find probability error bound on your learner? and derive its theoretical property. T 7. (60%) Suppose that X follows a bivariate distribution with E [X]=μ=(1,1) 1 1 T in group 1, E [X]=μ=(0,0) in group 2, and common covariance matrix Ψ 2 2 1 which is ( 1 ρ) ( ), -1 < ρ < 1. ( ρ 1 ) (a)(40%) Find a which maximizes the following ratio T 2 [a (μ-μ)] 1 2 —————————. T a Ψa 1 (b)(20%) Find the total probability of misclassification using Fisher's linear discriminant function with equal prior probability on group 1 and group 2. P 8. (50%) Consider a two-class classification on R problem with densities f 1 = N(μ,Σ), f = N(μ,Σ), and class membership probabilities π=P(class 1) 1 2 2 = 1 - P(class 2). This model can be constructed hierarchically: 1. generate L~Bernoulli(π) 2. if L=1: then generate X~N(μ,Σ) 1 3. else: generate X~N(μ,Σ). 2 (a) Compute P(L=1|X) and show that P(L=1|X)/P(L=0|X) has a logistic form. (b) Suppose now that the covariance matrix was not the same in each group (Σ). Does the probability P(L=1|X) still have a logistic form? (You can i answer this question with p=2.) 9. (50%) I have three coins in my pocket, Coin 0 has probability λ of heads; Coin 1 has probability p of heads; Coin 2 has probability p of heads. For 1 2 each trial I do the following: First I toss Coin 0 If Coin 0 turns up heads, I toss coin 1 three times If Coin 0 turns up tails, I toss coin 2 three times I do not tell you whether Coin 0 came up heads or tails, or whether Coin 1 or 2 was tossed three times, but I do tell you how many heads/tails are seen at each trial. You see the following sequence (H,H,H),(T,T,T),(H,H,H), (T,T,T),(H,H,H). (a) How do we find the maximum likelihood parameters of λ,p , and p ? 1 2 (b) How do you use EM to find the solution? --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.184.137.15 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1487599612.A.9EE.html