Machine Learning and Inductive Inference

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Tips

• De prof leest eerst het antwoord op u blad alvorens wat meer uitleg over iets specifiek te vragen. Zorg dus dat je duidelijk en volledig bent met je schriftelijke voorbereiding.
• De prof lijkt ROC leuk te vinden, in de les is duidelijk gezegd dat ROC zeker een examenvraag is.

Examen 12 juni 2006 voormiddag

Deze zijn reeds toegevoegd/aangepast in de onderstaande examenvragen.

• 1) Zie examenvragen : Eploration-exploitation trade-off bij reinforcement learning. Zijn er bij andere methodes gelijkaardige trade-offs?
• 2) Zie examenvragen : Explain the concepts of predictiveness and predictability, in the context of clustering.
• 3) Zie examenvragen : What are the main similarities and dissimilarities you see between instance based learners and support vector machines?
• 4) Nieuwe vraag : Comparing bagging and boosting, which one would you expect to be more robust to noise? Explain why.
• 5) Classify the following tasks as standard(attribute-value), multi-instance and multi-relational learning tasks.
  • Each example consists of a bunch of keys and whether it can be used to open a lock. The task is to learn what kind of key opens the lock.
  • Each example consists of a 3D-description of a molecule and a classification. The task is to find a substructure that occurs in all positive and no negative examples.
  • Each example consists of a description of a graph and its classification. The description of the graph consists of the number of nodes, number of edges and number of other properties it may or may not have. The task is to relate the classification of the graph to these properties.
• 6) Order according to theta-subsumption.
  • p(X) <- q(X), r(X)
  • p(X) <- q(Y), r(Y)
  • p(X) <- q(Y), r(X)
  • p(X) <- q(X), r(a)
  • p(X) <- q(a), r(b)
  • p(a) <- q(X)
  • q(a) <- q(X)

Theorie

Versionspaces

• To what property of learning do the "No Free Lunch" theorems refer? {laatst 2004}

Induction of decision trees

• How should a decision tree induction program such as C4.5 be changed so that it can act as a clustering method? {laatst 2004}
• In what sense is pruning rule sets more flexible than pruning trees? {laatst 2004}

Induction of rule sets & assuciation rules

• APRIORI algoritme: leg het pruning van zoekspace uit {laatst 2005}
• bij apriori, leg uit waarom je uit meerdere n-1 sets een set uitkomt van n {laatst 2004}

(Tip: zie gd+q)

Instance-based learning

• wat is de inductive bias bij IBL? {laatst 2005}
• Hoe kan overfitting vermeden worden bij decision trees, rule learning en instance based learning. {laatst 2005}
• curse of dimensionality {laatst 2005}
• What are the main similarities and dissimilarities you see between instance based learners and support vector machines? {examenvragen toledo, laatst 2006}

Clustering

• Explain the concepts of predictiveness and predictability, in the context of clustering. {laatst 2006}

Evaluating hypotheses

• Als een hypothese een accuracy lager heeft dan de base accuracy, moet ze dan direct verworpen worden, waarom (niet)?
• Accuracy A groter als accuracy B. Is het mogelijk dat bij ROC analyse B beter is dan A? {laatst 2005}
• "als een classifier onder de convex omhullende ligt in de ROC, dan is er altijd een classifier op de convex omhullende die een betere prediction accuracy heeft" Waar of niet, leg uit {2003,2004}
• Is the following statement correct or not: "if A is not on the convex hull in a ROC diagram, there must be at least one classifier on the convex hull with higher predictive accuracy than A." {laatst 2004}

(Tip: let op het woordje accuracy)

• ROC: A classifier A has TP=0 and FP=1. Interpret this. Is it possible to derive a better classifier from A in some principled way? {laatst 2004}
• Explain the principle of cross-validation. (How does it work, why is it needed?) {laatst 2004}
• vergelijking tussen McNemar en methode in boek (waarom beter McNemar) {laatst 2004}

Numerical approaches:ANN's, SVM's

• Een concept kan ook zeer algemeen gegeven worden, met dan een reeks exceptions, hoe zou je dit aanpakken? {laatst 2005}
  • of anders: Sometimes a concept can most easily be defined in terms of "exceptions", that is, by giving a simple, but too general description and then giving a more specific description describing the exceptions. Can you explain intuitively how artificial neural networks can represent such concepts? {2005-06-23 nm}
• Bij lineaire SVM is er een maximum margin classifier. Is die er ook bij niet-lineaire SVM? {laatst 2005}
• Vergelijk MDL en structural risk minimization {laatst 2005}
• Vergelijking IBL en SVM {laatst 2004}
• Vergelijk Feedforward neural networks met SVM's op het vlak van niet-lineaire beslissingsoppervlakken {laatst 2003}
• Can a perceptron, consisting of a single neuron, learn the boolean function (A and not B) or (not A and B)? Motivate your answer. {examenvragen toledo}

Computational learning theory

• Is the following sentence true or false: "A learner using a hypothesis space with a VC-dimension of N will always obtain zero training error on a training set of at most N examples". Explain your answer. {2005-06-23 NM}
• What does the VC-dimension measure, and why is it useful? bijvraag: is het nog nuttig indien VC-dim oneindig? {laatst 2004}
• VC-dim < log2 (|H|) {laatst 2004}
• What is the difference in difficulty of learning with (1) random chosen training examples (2) training examples given by the teacher (3) training examples chosen by learner {laatst 2003} (zie slide 4 en verder)

Baysian learning

• naive bayes als network voorstellen {laatst 2004}
• Bayes optimal classifier is beter dan de beste classifier, leg uit, leg berband met eager learning versus lazy learning {laatst 2003}
• leg de relatie tussen h_mdl (minimum description length) en h_map (maximum a posteriori) uit {laatst 2003}

Combining classifiers

• What is the main difference between boosting and bagging? {2005-06-23 nm}
• Comparing bagging and boosting, which one would you expect to be more robust to noise? Explain why. {laatst 2006}
• hoe kunt ge door het combineren van hypothesen gebieden identificeren waar bepaalde hypotheses het goed doen zodat je de gewichten die je aan de hypothesen geeft kunt aanpassen {laatst 2003}

Reinforcement learning

• Q-Learning: de update rule bij deterministisch vs niet-deterministisch
• convergentie van Q-learning in eigen woorden uitleggen {laatst 2003}
• geef voorbeelden bij Q-learning waar ge niet met qtable kunt werken (maar wel met generalisatie) en ook een voorbeeld voor waar ge zelfs niet met generalisatie kunt werken {laatst 2003}
• In what sense is it useful to combine reinforcement learning with

other learning techniques? {laatst 2004}

• What is the effect is in Q-learning the discount factor {gamma} becomes 0 {2005-06-23 nm}
• Q-learning. Why is a different learning rule necessary for undeterministic Q-learning? {laatst 2003}
• Eploration-exploitation trade-off bij reinforcement learning. Zijn er bij andere methodes gelijkaardige trade-offs? {laatst 2006}

Inductive logic programming

• lgg met theta subsumption van twee dingen
• probleem met multi-instanceproblemen bij attribuut-value representation {laatst 2005}
• Vergelijk Explanation Based learning en Inductive Logic Programming {laatst 2003} zie p312 boek

Ongesorteerde vragen

Gelieve een vraag bij het juiste onderwerp te plaatsen indien je weet waarbij het past

• Extensional vs Conceptual clustering{laatst 2004}
• topdown geeft meestal generalere hypothesen, is dit ook zo bij decision trees (die zijn ook topdown gemaakt) {laatst 2005}
• max probability classification is niet altijd exact te berekenen, waarom? kan je oplossingen bedenken? {laatst 20050
• Wat is de notion of generality, bespreek en waar in de cursus komt dit voor? {laatst 2003}
• What is the difference between characterizing vs descriptional induction {laatst 2003}

Oefeningen

ROC

• Classifier A has 90% accuracy on a training set with 50% positives. B has 80% accuracy on a training set with 70% positives. Show where A and B lie on a ROC diagram (If you can't obtain a single point, indicate the area.) {2005-06-23 NM}

• ROC curve met A en B gegeven, 50% - 50% verdeling pos en neg, geef kostenfuncties waarbij A beter is dan B en andersom {laatst 2004}

• ROC: Given a ROC diagram with 2 hypotheses A and B, and a 50-50 distribution of positive and negtive examples. Give an example situation where A is a better hypothesis that B and vice versa {laatst 2003}

• hypotheses vergelijken, waar liggen 1 en 2 op de ROC-curve en waarom + 1 en 2 zijn geleerd door learner die high accuracy nastreeft {laatst 2004}

• ROC curve, punt aanduiden op basis van een gegeven decisiontree {laatst 2003}

Instance Based

• Oef op nearest neighbour. {laatst 2005}
• Wat is VC dimension van Nearest Neighbour {laatst 2005}

Q-Learning

• Q-learning vraagske met robot dat mail moet afgeven op een aantal plaatsen, toepasselijke toestandsruimte geven en optimaal pad geleerd na 2 gegeven epochs {laatst 2004}

Inductive Logic Programming

• Quantitative sstructure-activity relationship (QSAR) modeling means that some quantified activity of a molecule is relevant of a molecule. Classify the following approaches to QSAR to structure modeling as standard (attribute,value), multi-instance, or multi-relational learning approaches.

• Classify the following tasks as standard (attribute-value), multi-instance, and multi-relational learning tasks:{laatst 2004}
  1. Each example consists of a drawing that contains geometric figures (triangles, squares, ...), and a classification. All geometric figures are described with a fixed number of attributes. The classification depends on the occurence of a single specific symbol (e.g., a triangle pointing up) in the drawing. The task is to learn which symbol this is.
  2. The format of an example is the same as above, but now the figures are also ordered from left to right and occur in fixed locations (or "slots"). A slot may also be empty. The classification depends on specific symbols occuring on specific locations (e.g., the first slot contains a circle and the third slot contains a triangle pointing up). The task is to learn the classification rule.
  3. The format of an example is the same as above, but now the classification depends on a combination of two specific figures (e.g., an example is positive if it contains both a circle and a square).

• Classify the following tasks as standard(attribute-value), multi-instance and multi-relational learning tasks.
  • Each example consists of a bunch of keys and whether it can be used to open a lock. The task is to learn what kind of key opens the lock.
  • Each example consists of a 3D-description of a molecule and a classification. The task is to find a substructure that occurs in all positive and no negative examples.
  • Each example consists of a description of a graph and its classification. The description of the graph consists of the number of nodes, number of edges and number of other properties it may or may not have. The task is to relate the classification of the graph to these properties.

• Order according to theta-subsumption.
  • p(X) <- q(X), r(X)
  • p(X) <- q(Y), r(Y)
  • p(X) <- q(Y), r(X)
  • p(X) <- q(X), r(a)
  • p(X) <- q(a), r(b)
  • p(a) <- q(X)
  • q(a) <- q(X)

Anderen

• 1. Discovering substructures in a molecule that influence the molecule's activity. Substructures can be described as graphs, and multiple substructures in the same molecule may have a cumulative effect on the molecule's activity.
  2. The molecules all consist of a fixed "skeleton". with a number of slots in which one of a limited set of functional groups can be placed. Occurrence of specific functional groups in specific positions is to be related to activity of the molecule.
  3. Each molecule is described as a list of spacial configurations that it can be in. Each configuration is divided as a fixed set of attributes. A molecule is active as soon as one of its configurations fulfills some condition. The goal is to learn these conditions from the data. {2005-06-23 NM}

• De grootte bepalen van de bezochte hypothese ruimte bij een example-driven en no example-driven rule learning algoritme. {laatst 2005}
• vb van tennisspelen, geef de grootte van de search space int geval van non-exampledriven en int geval van exampledriven {laatst 2003}

• lgg {laatst 2005}
  1. likes(frank, grimbergen) <- lives(frank, grimbergen), brewery(grimbergen, grimbergen)
  2. likes(mike, jupiler) <- lives(mike, leuven), brewery(jupiler, leuven)

• compute the lgg of (or something like :-) ): {laatst 2003}
  1. loves(ann,mickey) <- owns(ann,odie),dog(mickey),dog(odie)
  2. loves(jon,garfield) <- cat(spock),owns(jon,spock),cat(garfield)

• (niet-deterministich) reinforcement learning {laatst 2005}
• naive bayesiaans algoritme {laatst 2005}
• Naive Bayes oefening, ook m-estimate gebruiken {laatst 2003}

• 3NN op vbn van persoon die in fast-food restaurants gaat eten {laatst 2004}
• maak een feedforward neural network voor A and ((b and c) or d) {laatst 2003}

• A restaurant has a "fruit salad of the day" on the menu; each day this is a different combination of several kinds of fruit (choen from apple, banana, strawberry, pineapple, mango, raspberry). In a certain week the salads below are served. Find out wich combinations of fruit occur in at least 50% of the salads, by simulating Apriori. Give at least one example of an association rule that can be derived from the result. {laatst 2004}
  1. apple, strawberry, pineapple, raspberry
  2. apple, banana, mango, raspberry
  3. raspberry, banana, mango
  4. apple, raspberry, mango
  5. apple, pineapple, mango, raspberry
  6. mango, pineapple, raspberry, banana

• A tavern servers the following beers: Jupiler, Hoegaarden, Duvel. You can drink there at a table inside or outside. Jef is a regular customer in this tavern, and the waiter has the data below on him (weather - beer - place). On a rainy day, Jef sits down at a table inside. Use Naïve Bayes to predict which beer he will order. {laatst 2004}
  1. cloudy - Duvel - outside
  2. rainy - Jupiler - inside
  3. cloudy - Duvel - inside
  4. sunny - Hoegaarden - outside
  5. rainy - Hoegaarden - inside
  6. sunny - Duvel - inside

• decision tree: A && ((B && C) || D) {laatst 2004}
• decision tree: (A && B) || C || D {laatst 2003}

• 1. veel positieve voorbeelden geleerd, weinig negatieve
  2. veel negatieve voorbeelden geleerd, weinig positieve