Machine Learning and Inductive Inference

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Tips

• Het is schriftelijk, je mag dus je boek en je oefeningen meebrengen. Zorg er dus voor dat je goed weet waar alles staat in het boek.
• Er staan hieronder een lijst met mooie examenvragen van toen de prof nog met een vorig boek werkte, er is geen garantie dat de prof deze vragen vraagt, maar het is wel een mooie samenvatting om uw cursus aan op te hangen.
• De prof lijkt ROC leuk te vinden, in de les is duidelijk gezegd dat ROC zeker een examenvraag is.

Examen 20 juni 2008 namiddag

• 1) Bespreek het verschil tussen learning modellen die worden gemaakt met het minimal description length (MDL) principe en deze die een eenvoudige model nastreven (dus Occam's Razor toepassen).
• 2) Gegeven een aantal punten. Geef een hierarchische clustering met de single linkage afstand en een met de complete linkage afstand.
• 3) Leg uit waarom de voorspelling van de meest waarschijnlijke hypothese (MAP-hypothese) toch niet de meest waarschijnlijke voorspelling is.
• 4) Gegeven een hypothese-ruimte bestaande uit louter conjunctieve concepten en een lijst van 8 attributen (8 ingredienten voor op een pizza in dit geval); toon aan dat de VC-dimensie minstens 3 is en maximaal 8. (Hint (niet gegeven): toon door middel van een voorbeeld aan dat VC-dimensie van 3 haalbaar is en door middel van contradictie aan dat een VC-dimensie van 9 onmogelijk is.)
• 5) Welke parameter regelt bij reinforcement learning de "geduldigheid" van de agent?
• 6) Een Theta-subsumption vraag. Gevraagd was de lattice te tekenen horende bij deze partiële orderelatie.
• 7) Kan Naive Bayes de XOR functie leren? Argumenteer.
• 8) Gegeven twee classifiers (in de vorm van een regelset), plot deze op een ROC curve. (bv: IF stupid THEN positive (9/20) en IF dumb THEN negative (23/40) waarbij 9/20 aangeeft dat er 9 juist werden geclassificeerd op 20 voorbeelden).
• 9) Gegeven waren alle mogelijke subsets van {a,b,c,d,e}, dewelke werden aangereikt met de frequency count. Schrap alle itemsets dewelke niet door het Apriori algoritme worden gegenereerd, gegeven een bepaalde minimale support.
• 10) Een eenvoudige 3NN vraag waarbij je de Hamming afstand moest gebruiken.

Examen 13 juni 2008 voormiddag

• 1) Als een learning algoritme een sterkere bias heeft is zijn VC-dimensie dan hoger/lager/geen verband (leg uit in 2 zinnen)
• 2) We willen een aantal attributen Xi mappen op Yi en we willen daarvoor dat X een grote predictiveness heeft en Y een hoge predictibility. Maar wat als X een hoge predictibility en Y een hoge predictiveness heeft.
• 3) Vergelijk MAP en ML vanuit de inductive bias
• 4) Show a set of 3 pizza's that is shattered by this hypotheses space (hypothese ruimte geg.)
• 5) Q-learning: X en Y zijn 2 continuee variabelen zijn van een state, er zijn dus oneindig veel states. Hoe los je dit op? Wat als er een eindig aantal states zijn en oneindig veel acties.
• 6) Een voorbeeld van een True/False regel en plot op een ROC diagram
• 7) Een aantal vragen over True Pos en False Pos (in een situatie schets)
• 8) Least general generalisation under theta subsumption
• 9) Je krijgt een getelde set, schrap alle niet frequent item sets die je apriori niet moet tellen.
• 10) oefening op 3 nearest neighbours.

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)

Examen 12 juni 2006 namiddag

Deze zijn nog niet aangepast in de vragen hieronder. Heb de vragen niet bij me, dus t zal een ruwe omschrijving worden.

1. Verklaar waarom multi instance problems niet goed voorgesteld kunnen worden met de normale attribuut voorstelling. (oude vraag)
2. "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 (oude vraag)
3. Sommige tree decision learners gebruiken een parameter om aan te geven hoeveel instances er minimaal door een blad gedekt moeten worden. Verklaar het verband met noise data en met k-clustering (nieuwe vraag)
4. Waarom kunnen de standaard rule learners niet gebruikt worden bij association rule learning. Bijvraag: indien je een regel met confidence 30% hebt, heeft die regel dan wel nut? Kun je die met andere woorden nog gebruiken. (nieuwe vraag, 2006)
5. Bijvraag uit cursus bij n-crossfolding. Pas 10-voudige crossfolding toe op 10 datagegevens waarvan 5 in klasse A en 5 in klasse B zitten. Wat zijn je conclusies? {juni 2006}
6. Gegeven de mogelijke waarden voor deze attributen: weather = sky/sunny/cloudy, temperature = hot/cold, wind = strong/weak. De hypotheseruimte bestaat enkel uit conjuncties van deze zaken. Zoek de grootst mogelijke ondergrens voor VC(X) voor alle instance-ruimten X die mogelijk zijn {juni 2006}

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}
• topdown geeft meestal generalere hypothesen, is dit ook zo bij decision trees (die zijn ook topdown gemaakt) {laatst 2005}

Induction of rule sets & association 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

• Extensional vs Conceptual clustering{laatst 2004}
• Explain the concepts of predictiveness and predictability, in the context of clustering. {laatst 2006}
  • bijvraag: je beslist om een cluster op te splitsen: wat gebeurt er met de predictiveness/predictability ?

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,juni 2006}
• 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 verband 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}
• Exploration-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
• Verklaar waarom multi instance problems niet goed voorgesteld kunnen worden met de normale attribuut voorstelling. {2005,2006}
• Vergelijk Explanation Based learning en Inductive Logic Programming {laatst 2003} zie p312 boek
• Wat is de notion of generality, bespreek en waar in de cursus komt dit voor? (zie begin fundamentals of IDL){laatst 2003}
• What is the difference between characterizing vs descriptional induction {laatst 2003}

Ongesorteerde vragen

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

• Max probability classification is niet altijd exact te berekenen, waarom? kan je oplossingen bedenken? {laatst 2005}
• Sommige tree decision learners gebruiken een parameter om aan te geven hoeveel instances er minimaal door een blad gedekt moeten worden. Verklaar het verband met noise data en met k-clustering {juni 2006}

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}
• 3NN op vbn van persoon die in fast-food restaurants gaat eten {laatst 2004}

Bayesian learning

• naive bayesiaans algoritme {laatst 2005}
• Naive Bayes oefening, ook m-estimate gebruiken {laatst 2003}

Reinforcement learning

• (niet-deterministich) reinforcement learning {laatst 2005}
• 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.

• 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)

• 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. {laatst 2006}
  • 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. {laatst 2006}
  • 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}

• 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