• (map fn list)
• (reduce fn list)
• (filter fn list)
• (fn [args] code)
• (let [var init ...] code)
• (mapcat fn list)

• Depth-first search: order of search, stack space used, Big O
• Nested tree recursion

• Backchaining: be able to do simple problems.
  • depth-first search order
  • use in answering why questions
• Resolution: be able to do a simple problem
• Prolog

• Amphion: Stickel paper. What does Amphion do that is valuable?
• deductive composition of library programs: axioms represent what library programs do, deduction proves that a goal can be satisfied by composing library programs; proof is converted to a program.

• Expert system domains: lack of good input data, empirical rules, probabilistic reasoning
• Knowledge-based strategy: knowledge encoded as rules, shallow reasoning
• Rule-based systems: EMYCIN, knowledge represented as if-then rules
• Backchaining extended by ask the user.
• Bayes' Theorem: notation, formula, use in expert systems: statistics to diagnostic rule
• Bayesian Networks: benefits
• EMYCIN certainty factors: -1 to +1, measure of belief - disbelief
• Certainty factor combination
  • Data CF: SAME. KNOWN; > .2 threshold
  • Antecedent CF: $AND is minimum, $OR is maximum, TALLY is result
  • Conclude CF due to rule as a whole: TALLY * CONCLUDE / 1000
  • CF combinations from multiple rules: CF_p + CF_n * (1 - CF_p)
  • commutative and associative: order does not matter
• Problems with rules: leaving out a clause, sharp edges
• Explanations using rules
• Conceptual islands, orthogonal knowledge sources
• Decision trees, rule induction: problems
• Digital low-pass filter, use as a learning mechanism
• Overfitting, tuning fallacy or training-set phenomenon: performance on new cases is not as good as performance on training set

• Shannon information theory: encoding information with the shortest possible message
• Zipf's law: frequently used words are short.
• Context-free grammar
• Context-free language: recursive, tree structure, phrases can contain themselves
• Recursive descent parser: top-down; grammar rules become programs. Left recursion causes infinite loop.
• Semantic grammar: phrases have meaning in the application domain: reduces ambiguity
• NL access to database, physics problems

• Mapping in CS: function, array, hash table
• map, mapcat and reduce in Lisp/Clojure
• Functional programming: no side-effects means it can be distributed
• commutative and associative: order does not matter
• mapcat (mapcan in Lisp): concatenate lists
• MapReduce associates a key with each result
• Master, mapper, reducer
• Load balancing with hashing of key
• Failure and recovery
• PageRank: iterated MapReduce

Vocabulary