Machine Learning and Inductive Inference

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.

Theorie

Ongesorteerde vragen

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

• Als een hypothese een accuracy lager heeft dan de base accuracy, moet ze dan direct verworpen worden, waarom (niet)?
• Extensional vs Conceptual clustering
• Q-Learning: de update rule bij deterministisch vs niet-deterministisch
• lgg met theta subsumption van twee dingen
• gegeven: boom, plot op ROC
• 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}
• Eploration-exploitation trade-off bij reinforcement learning. Zijn er bij andere methodes gelijkaardige trade-offs? {laatst 2005}
• Hoe kan overfitting vermeden worden bij decision trees, rule learning en instance based learning. {laatst 2005}
• Bij lineaire SVM is er een maximum margin classifier. Is die er ook bij niet-lineaire SVM? {laatst 2005}
• Accuracy A groter als accuracy B. Is het mogelijk dat bij ROC analyse B beter is dan A? {laatst 2005}
• probleem met multi-instanceproblemen bij attribuut-value representation {laatst 2005}
• 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}
• 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 2005}
• curse of dimensionality {laatst 2005}
• APRIORI algoritme: leg het pruning van zoekspace uit {laatst 2005}
• wat is de inductive bias bij IBL? {laatst 2005}
• Vergelijk MDL en structural risk minimization {laatst 2005}
• What does the VC-dimension measure, and why is it useful? bijvraag: is het nog nuttig indien VC-dim oneindig? {laatst 2004}
• 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}
• To what property of learning do the "No Free Lunch" theorems refer? {laatst 2004}
• bagging vs boosting {laatst 2004}
  • of anders: What is the main difference between boosting and bagging? {2005-06-23 nm}
• VC-dim < log2 (|H|) {laatst 2004}
• example-driven vs not example-driven {laatst 2004}
• naive bayes als network voorstellen {laatst 2004}
• How should a decision tree induction program such as C4.5 be changed so that it can act as a clustering method? {laatst 2004}
• Reinforcement Learning combineren met andere learners {laatst 2004}
• Explain the concepts of predictiveness and predictability, in the context of clustering. {laatst 2004}
• Vergelijking IBL en SVM {laatst 2004}
• "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 {laatst 2004}
• Explain the principle of cross-validation. (How does it work, why is it needed?) {laatst 2004}
• In what sense is pruning rule sets more flexible than pruning trees? {laatst 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)

• vergelijking tussen mcnemar en methode in boek (waarom beter mcnemar) {laatst 2004}
• bij apriori, leg uit waarom je uit meerdere n-1 sets een set uitkomt van n {laatst 2004}

(Tip: zie gd+q)

• Bayes optimal classifier is beter dan de beste classifier, leg uit, leg berband met eager learning versus lazy learning {laatst 2003}
• 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}
• geef voorbeelden bij q leqrning 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}
• leg de relatie tussen h_mdl en h_map uit {laatst 2003}
• convergentie van Q-learning in eigen woorden uitleggen {laatst 2003}
• conceptual <-> extensional clustering {laatst 2003}
• Vergelijk Feedforward neural networks met SVM's op het vlak van niet-lineaire beslissingsoppervlakken {laatst 2003}
• Vergelijk Explanation Based learning en Inductive Logic Programming {laatst 2003}
• Wat is de notion of generality, bespreek en waar in de cursus komt dit voor? {laatst 2003}
• Wat gebeurt er als je bij Q-learning de "gamma" op 0 zet? {laatst 2003}
  • Of anders: What is the effect is in Q-learning the discount factor {gamma} becomes 0 {2005-06-23 nm}
• 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}
• What is the difference between characterizing vs descriptional induction {laatst 2003}
• Q-learning. Why is a different learning rule necessary for undeterministic Q-learning? {laatst 2003}
• "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 {laatst 2003}

Oefeningen

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

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

• 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}
• Oef op nearest neighbour. {laatst 2005}
• De grootte bepalen van de bezochte hypothese ruimte bij een example-driven en no example-driven rule learning algoritme. {laatst 2005}
• Wat is VC dimension van Nearest Neighbour {laatst 2005}

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

• (niet-deterministich) reinforcement learning {laatst 2005}
• naive bayesiaans algoritme {laatst 2005}
• 3NN op vbn van persoon die in fast-food restaurants gaat eten {laatst 2004}

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

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

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

• 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}
• 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}
  1. veel positieve voorbeelden geleerd, weinig negatieve
  2. veel negatieve voorbeelden geleerd, weinig positieve

• 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}
• Naive Bayes oefening, ook m-estimate gebruiken {laatst 2003}
• ROC curve, punt aanduiden op basis van een gegeven decisiontree {laatst 2003}

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

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