CIS140 W2007 Quiz 4 Date: Friday, March 2, 2007 Robert Levinson There are 35 T/F and Multiple Choice Questions worth 2 points each and 3 Lisp questions worth 8 points each for a grand total of 94 points. {PART I: True, False} Please answer the following questions True or False. Simply Circle the Number of The R in RIKLS stands for "reinforcement learning". F A closed system never has more diversity than the total diversity in its (unconstrained) parts. T An A* heuristic that returns 2 at all states is definitely not admissable. T Nearest neighbor learning is just another ``name" for the version space algorithm. F One advantage resolution theorem proving has over existential graphs is that resolution proofs are usually shorter, higher level, intuitive, and easier to understand. F Constructing smallest size decision trees is NP-hard. T If A subsumes B, C subsumes C. T The danger of ``overfitting" your data is that your model may be too specific to likely work as well on future data. T The set of all prime integers can not be defined intensionally. F Nearest neighbor is incapable of learning how to solve the eight-puzzle F A "version space" always acts to maximize its expected bidirectional iterative Manhattan Distance, even in the presence of noise. F Although, Minimax is worst-case optimal it may not always recommend the move with actual maximum expected practical utility, even when the entire game-tree can be searched. T As of Feb. 28 2007, Go-Moku, Tic-Tac-Toe, Qubic, Checkers, Othello and Chess have all been solved (game-theoretic value determined) with or without the aid of some computer analysis. F In EMA-based weight learning, using the formula NewWeight= alpha*OldWeight + (1-alpha)*Newdatapoint, a dynamic alpha should be made to decrease as the system's error increases and increase as the system's error decreases. T In 1-2-3-4-5-6-7 (7 piles such that pile-i has i sticks) Nim, the first player can win with perfect play. F The following two terms unify: P(x,x), P(A,y) where x and y are variables and A is a constant. T The version space of a set of statements can be stored by simply remembering the most-specific rules that could possibly be true and the most-general rules that could possibly be true - the rest can be inferred through subsumption. T In the pennies game, there are 8 pennies. Player's alternate taking 1-3 pennies. The player who takes the last penny wins. Clearly, player 1 can always wins this game. F Nearest neighbor never actually learns an ``intensional definition" of the function or set it is approximating. T A decision tree never actually learns an ``intensional definition" of the function or set is is approximating. F One advantage perceptrons have over nearest neighbor is that they are usually faster to use to make a prediction. T One advantage nearest neighbor (NN) has over version spaces is that the training time for each example is shorter in NN. T One advantage version spaces have over decision trees is that generally head space ``snoclification" transcends lunch time. F One advantage perceptrons have over other learning methods is that perceptrons do not require numerical calculations. F One weakness of nearest neighbor is that it can only learn linear functions. F The 8-puzzle state: 245 617 380 is solvable. F Log-base-2 of 2 is 1. T The diversity (potential surprise) of a future event with n possible outcomes never exceeds (log 2 n) ``log-base-2 of n" bits. T There is an algorithm for solving all solvable 8-puzzle states in constant time. T Exponential moving averages tend to weigh more recent data higher than older data. T Clause form never includes quantifiers. T The diversity of a random 6-sided die is log2(1/6) bits. F Symmetry never decreases over time in a closed system. T Diversity of a system with N states is maximum if each state is equally likely. T A system must either be deterministic or open. T ******************* Write a Lisp function FLAMBE that takes a list and inserts the list after each of its top-level members. (flambe nil) is nil. Example: (flambe '(1 2 3)) should return: (1 (1 2 3) 2 (1 2 3) 3 (1 2 3)) (defun flambe (l) (apply #'append (mapcar #'(lambda (x) (list x l)) l))) Suppose your Lisp installation does not come with "butlast". Write a function MYBUTLAST that returns all but the last member of a non-empty list (example: (mybutlast '(3 2 1)) should return: (3 2) (defun mybutlast (l) (reverse (rest (reverse l)))) Write a Lisp function FLATTEN L that simply lists all atoms occurring at any level of a list L in order. Example: (flatten '(1 (2) ((3) 5) (4) 2 (6))) should return: (1 2 3 5 4 2 6) (defun flatten (l) (if l (if (atom l) (list l) (apply #'append (mapcar #'flatten l)))))