哈工大机器学习历年考试

1、-作者xxxx-日期xxxx哈工大机器学习历年考试【精品文档】1 Give the definitions or your comprehensions of the following terms.(12)1.1 The inductive learning hypothesisP171.2 OverfittingP491.4 Consistent learner P1482 Give brief answers to the following questions.(15)2.2 If the size of a version space is , In general what is

2、the smallest number of queries may be required by a concept learner using optimal query strategy to perfectly learn the target concept?P272.3 In genaral, decision trees represent a disjunction of conjunctions of constrains on the attribute values of instanse,then what expression does the following d

3、ecision tree corresponds to ?OutLookHumidityWindSunnyOvercastRainYesHighNormalYesNoStrongYesWeakNo3 Give the explaination to inductive bias, and list inductive bias of CANDIDATE-ELIMINATION algorithm, decision tree learning(ID3), BACKPROPAGATION algorithm.(10)4 How to solve overfitting in decision t

4、ree and neural network?(10)Solution:l Decision tree:u 及早停止树增长(stop growing earlier)u 后修剪法(post-pruning)l Neural Networku 权值衰减(weight decay)u 验证数据集(validation set)5 Prove that the LMS weight update rule performs a gradient descent to minimize the squared error. In particular, define the squared error

5、 E as in the text. Now calculate the derivative of E with respect to the weight , assuming that is a linear function as defined in the text. Gradient descent is achieved by updating each weight in proportion to . Therefore, you must show that the LMS training rule alters weights in this proportion f

6、or each training example it encounters. ( ) (8)Solution：As Vtrain(b)(Successor(b) we can get E= =As mentioned in LMS: We can get Therefore, gradient descent is achievement by updating each weight in proportion to ;LMS rules alters weights in this proportion for each training example it encounters.6

7、True or false: if decision tree D2 is an elaboration of tree D1, then D1 is more-general-than D2. Assume D1 and D2 are decision trees representing arbitrary boolean funcions, and that D2 is an elaboration of D1 if ID3 could extend D1 to D2. If true give a proof; if false, a counter example.(Definiti

8、on: Let and be boolean-valued functions defined over .then is more_general_than_or_equal_to(written ) If and only if then ) (10)The hypothesis is false. One counter example is A XOR Bwhile if A!=B, training examples are all positive, while if A=B, training examples are all negative,then, using ID3 t

9、o extend D1, the new tree D2 will be equivalent to D1, i.e., D2 is equal to D1.7 Design a two-input perceptron that implements the boolean function .Design a two-layer network of perceptrons that implements . (10)8 Suppose that a hypothesis space containing three hypotheses, , and the posterior prob

10、abilities of these typotheses given the training data are 0.4, 0.3 and 0.3 respectively. And if a new instance is encountered, which is classified positive by , but negative by and ,then give the result and detail classification course of Bayes optimal classifier.(10)P1259 Suppose S is a collection

11、of training-example days described by attributes including Humidity, which can have the values High or Normal. Assume S is a collection containing 10 examples, 7+,3-. Of these 10 examples, suppose 3 of the positive and 2 of the negative examples have Humidity = High, and the remainder have Humidity

12、= Normal. Please calculate the information gain due to sorting the original 10 examples by the attribute Humidity.( log21=0, log22=1, log23=1.58, log24=2, log25=2.32, log26=2.58, log27=2.8, log28=3, log29=3.16, log210=3.32, ) (5)Solution： (a)Here we denote S=7+,3-,then Entropy(7+,3-)= =0.886;(b)Gain

13、(S,a2) Values()=High, Normal ,=4 ,=5Thus Gain10 Finish the following algorithm. (10)(1) GRADIENT-DESCENT(training examples, )Each training example is a pair of the form , where is the vector of input values, and t is the target output value. is the learning rate (e.g., ).l Initialize each to some sm

14、all random valuel Until the termination condition is met, Dol Initialize each to zero.l For each in training_examples, Dol Input the instance to the unit and compute the output ol For each linear unit weight , Do l For each linear unit weight , Do (2) FIND-S Algorithml Initialize h to the most speci

15、fic hypothesis in Hl For each positive training instance xl For each attribute constraint ai in h If Then do nothing Else replace ai in h by the next more general constraint that is satisfied by xl Output hypothesis h1. What is the definition of learning problem?(5)Use “a checkers learning problem”

16、as an example to state how to design a learning system. (15)Answer: A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience. (5)Example: A checkers learning pro

17、blem: T: play checkers (1)P: percentage of games won in a tournament (1)E: opportunity to play against itself (1)To design a learning system:Step 1: Choosing the Training Experience (4)A checkers learning problem:Task T: playing checkersPerformance measure P: percent of games won in the world tourna

18、mentTraining experience E: games played against itselfIn order to complete the design of the learning system, we must now choose1. the exact type of knowledge to be learned2. a representation for this target knowledge3. a learning mechanism Step 2: Choosing the Target Function (4) 1. if b is a final

19、 board state that is won, then V(b)=1002. if b is a final board state that is lost, then V (b)=-1003. if b is a final board state that is drawn, then V (b)=04. if b is a not a final state in the game, then V(b)=V (b), where b is the best final board state that can be achieved starting from b and pla

20、ying optimally until the end of the game (assuming the opponent plays optimally, as well). Step 3: Choosing a Representation for the Target Function (4) x1: the number of black pieces on the boardx2: the number of red pieces on the boardx3: the number of black kings on the boardx4: the number of red

21、 kings on the boardx5: the number of black pieces threatened by red (i.e., which can be captured on reds ext turn)x6: the number of red pieces threatened by black.Thus, our learning program will represent V (b) as a linear function of the formV (b)=wo+wlxl+w2x2+w3x3+w4x4+w5x5+w6x6where wo through w6

22、 are numerical coefficients, or weights, to be chosen by thelearning algorithm. Learned values for the weights w1 through w6 will determinethe relative importance of the various board features in determining the value ofthe board, whereas the weight wo will provide an additive constant to the boardv

23、alue.2. Answer:Find-S & Find-G:Step 1: Initialize S to the most specific hypothesis in H. (1)S0:, , , , , Initialize G to the most general hypothesis in H.G0:?, ?, ?, ?, ?, ?.Step 2: The first example is (3) S1:Sunny, Warm, Normal, Strong, Warm, Same G1:?, ?, ?, ?, ?, ?.Step 3: The second example is

24、 (3) S2:Sunny, Warm, ?, Strong, Warm, Same G2:?, ?, ?, ?, ?, ?.Step 4: The third example is (3) S3: Sunny, Warm, ?, Strong, Warm, Same G3:, , Step 5: The fourth example is (3)S4:Sunny, Warm, ?, Strong, ?, ?G4:, Finally, all the hypotheses are:(2) , , , , , 3. Answer:Flog(X) = -X*log(X)-(1-X)*log(1-X

25、);STEP1 choose the root node: entropy_all = flog(4/10); (2)gain_outlook = entropy_all - 0.3*flog(1/3) - 0.3*flog(1) - 0.4*flog(1/2); (1)gain_templture = entropy_all - 0.3*flog(1/3) - 0.3*flog(1/3) - 0.4*flog(1/2); (1)gain_humidity = entropy_all - 0.5*flog(2/5) - 0.5*flog(1/5); (1)gain_wind = entropy

26、_all - 0.6*flog(5/6) - 0.4*flog(1/4); (1)Root Node is “outlook”: (2)overcastSunnyoutlook+1 -2+4Rainy+2 -1step 2 choose the second NODE: for sunny (humidity OR temperature):entropy_sunny = flog(1/3); (1)sunny_gain_wind = entropy_sunny - (2/3)*flog(0.5) - (1/3)*flog(1)=0.252; (1)sunny_gain_humidity =

27、entropy_sunny - (2/3)*flog(1) - (1/3)*flog(1); (1)sunny_gain_temperature = entropy_sunny - (2/3)*flog(1) - (1/3)*flog(1); (1)choose humidity or temperature. (1) for rain (wind): entropy_rain = flog(1/2)=1; (1)rain_gain_wind = entropy_rain - (1/2)*flog(1) - (1/2)*flog(1)=1; (1)rain_gain_humidity = en

28、tropy_rain - (1/2)*flog(1/2)-(1/2)*flog(1/2)=0; (1)rain_gain_temperature = entropy_rain - (1/4)*flog(1)- (3/4)*flog(1/3); (1)choose wind. (1) (2)overcastSunnyoutlookhumidityyesRainywindHighnoyesNormalStrongnoyesWeakorovercastSunnyoutlooktemperatureyesRainywindHotnoyesCoolStrongnoyesWeak4. Answer:A:

29、The primitive neural units are: perceptron, linear unit and sigmoid unit.(3)Perceptron: (2)A perceptron takes a vector of real-valued inputs, calculates a linear combination of these inputs, then output a 1 if the result is greater than some threshold and -1 otherwise. More precisely, given input x1

30、 through xn, the output o(x1,.xi,. xn) computed by the perceptron is N Sometimes write the perceptron function as Linear units: (2)a linear unit for which the output o is given byThus, a linear unit corresponds to the first stage of a perceptron, without the threshold.Sigmoid units: (2)The sigmoid u

31、nit is illustrated in picture like the perceptron, the sigmoid unit first computes a linear combination of its inputs, then applies a threshold to the result. In the case of the sigmoid unit, however, the threshold output is a continuous function of its input. More precisely, the sigmoid unit comput

32、es its output o asWhere,B: (因题目有打印错误，所以感知器规则和delta规则均可，给出的是delta规则)Derivation process is: (6) 感知器规则（perceptron learning rule）5. Answer:P(no)=5/14 P(yes)=9/14 (1)P(sunny|no)=3/5 (1)P(cool|no)=1/5(1)P(high|no)=4/5(1)P(strong|no)=3/5(1)P(no|new instance)=P(no)*P(sunny|no)*P(cool|no)*P(high|no)*P(strong

33、|no)=5/14*3/5*1/5*4/5*3/5 = 0.02057=2.057*10-2(2)P(sunny|yes)=2/9(1)P(cool|yes)=3/9(1)P(high|yes)=3/9(1)P(strong|yes)=3/9(1)P(yes|new instance)=P(yes)*P(sunny|yes)*P(cool|yes)*P(high|yes)*P(strong|yes)=9/14*2/9*3/9*3/9*3/9 = 0.05291=5.291*10-3(2)ANSWER: NO(2)6. Answer:INDUCTIVE BIAS: (8)Consider a c

34、oncept learning algorithm L for the set of instances X, Let c be an arbitrary concept define over X, and let Dc = be an arbitrary set of training examples of c . Let denote the classification assigned to the instance xi by L after training on the data Dc .The inductive bias of L is any minimal set o

35、f assertions B such that for any target concept c and corresponding training examples Dc:(xi X)(B xi Dc) L(xi;Dc)-Thefutilityofbias-freelearning: (7)Alearnerthatmakesnoaprioriassumptionsregardingtheidentityofthetargetconcepthasnorationalbasisforclassifyinganyunseeninstances.Infact,theonlyreasonthatt

36、helearnerwasabletogeneralizebeyondtheobservedtrainingexamplesisthatitwasbiasedbytheinductivebias.Unfortunately，the only instances that will produce a unanimous vote are the previously observed training examples. For, all the other instances, taking a vote will be futile: each unobserved instance wil

37、l be classified positive by precisely half the hypotheses in the version space and will be classified negative by the other half.1 In the EnjoySport learning task, every example day is represented by 6 attributes. Given that attributes Sky has three possible values, and that AirTemp、Humidity、Wind、Wi

38、nd、Water and Forecast each have two possible values. Explain why the size of the hypothesis space is 973. How would the number of possible instances and possible hypotheses increase with the addition of one attribute A that takes on on K possible values?2 Write the algorithm of Candidate_Elimination

39、 using version space. Assume G is the set of maximally general hopytheses in hypothesis space H, and S is the set of maximally specific hopytheses.3 Consider the following set of training examples for EnjoySport:ExampleSkyAirTempHumidityWindWaterForcastEnjoySport1sunnywarmnormalstrongwarmsameYes2sun

40、nywarmhighstrongwarmsameyes3rainycoldhighstrongwarmchaggeno4sunnywarmhighstrongcoolchangeyes5sunnywarmnormalweakwarmsameno(a) What is the Entropy of the collection training examples with respect to the target function classification?(b) According to the 5 traning examples, compute the decision tree

41、that be learned by ID3, and show the decision tree.(log23=1.585, log25=2.322)4 Give several approaches to avoid overfitting in decision tree learning. How to determin the correct final tree size?5 Write the BackPropagation algorithm for feedforward network containing two layers of sigmoid units.6 Ex

42、plain the Maximum a posteriori(MAP) hypothesis.7 Using Naive Byes Classifier to classify the new instance:Our task is to predict the target value (yes or no) of the target concept PlayTennis for this new instance. The table blow provides a set of 14 training examples of the target concept. DayOutloo

43、kTemperatureHumidityWindPlayTennisD1D2D3D4D5D6D7D8D9D10D11D12D13D14SunnySunnyOvercastRainRainRainOvercastSunnySunnyRainSunnyOvercastOvercastRainHotHotHotMildCoolCoolCoolMildCoolMildMildMildHotMildHighHighHighHighNormalNormalNormalHighNormalNormalNormalHighNormalHighWeakStrongWeakWeakWeakStrongStrong

44、WeakWeakWeakStrongStrongWeakStrongNoNoYesYesYesNoYesNoYesYesYesYesYesNo8 Question Eight：The definition of three types of fitness functions in genetic algorithmQuestion one:（举一个例子，比如:导航仪、西洋跳棋）Question two:Initilize: G=?,?,?,?,?,? S=,Step 1: G=?,?,?,?,?,? S=sunny,warm,normal,strong,warm,sameStep2: com

45、ing one positive instance 2 G=?,?,?,?,?,? S=sunny,warm,?,strong,warm,sameStep3: coming one negative instance 3 G= S=sunny,warm,?,strong,warm,sameStep4: coming one positive instance 4 S= sunny,warm,?,strong,?,? G= Question three:(a) Entropy(S)=og(3/5) (b) Gain(S,sky) = Entropy(S) Choose any feature o

46、f AirTemp, wind and sky as the top node.The decision tree as follow: (If choose sky as the top node)Question Four: Answer: Inductive bias: give some proor assumption for a target concept made by the learner to have a basis for classifying unseen instances.Suppose L is a machine learning algorithm an

47、d x is a set of training examples. L(xi, Dc) denotes the classification assigned to xi by L after training examples on Dc. Then the inductive bias is a minimal set of assertion B, given an arbitrary target concept C and set of training examples Dc: (Xi ) (BDcXi) -| L(xi, Dc)C_E: the target concept i

48、s contained in the given gypothesis space H, and the training examples are all positive examples.ID3: a, small trees are preferred over larger trees. B, the trees that place high information gain attribute close to root are preferred over those that do not.BP:Smooth interpolation beteen data points.

49、Question Five: Answer: In nave bayes classification, we assump that all attributes are independent given the tatget value, while in bayes belif net, it specifes a set of conditional independence along with a set of probability distribution. Question Six： 随即梯度下降算法Question Seven：朴素贝叶斯例子Question Eight：The definit