-
Notifications
You must be signed in to change notification settings - Fork 23
/
instruction-notes.html
642 lines (642 loc) · 34.6 KB
/
instruction-notes.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="generator" content="pandoc" />
<meta name="author" content="Joseph C. Osborn" />
<title>Schedule</title>
<style type="text/css">code{white-space: pre;}</style>
</head>
<body>
<div id="header">
<h1 class="title">Schedule</h1>
<h2 class="author">Joseph C. Osborn</h2>
</div>
<p>This document is intended for use by the instructor and TAs, since we don’t want to commit to a firm schedule or show the readings/assignments too far in advance (it might be confusing).</p>
<ul>
<li>Day 1: What is AI?
<ul>
<li><dl>
<dt>Reading</dt>
<dd>Before doing today’s assignment, students should read the excerpts from Philip Agre’s “Computation and Human Experience” as well as the D. Fox Harrell paper in the reader.
</dd>
</dl></li>
<li><dl>
<dt>Topic 1: What is AI?</dt>
<dd>Hi, who am I?
</dd>
<dd>Introduction to main threads of AI research. What is and is not AI. Historical and present uses of the term. AI winter. Sidestepping “what is ‘intelligence’”? Creative and commercial uses of AI. Generative methods. Modern AI as a set of techniques, rather than an attempt to simulate the brain. “Getting good results” vs “learning/claiming something about cognition”.
</dd>
<dd>(If possible, include some Game AI, some mixed initiative stuff (Tanagra), some of my research area here.)
<ul>
<li>Knowledge based</li>
<li>Grammars, logical systems, argumentation, social simulations, explicit representation of knowledge…</li>
<li>Expense, fragility, rhetorical purpose, …</li>
<li>Statistical</li>
<li>Genetic algorithms/programming, neural nets, machine learning …</li>
<li>Choice of loss function, metrics, overfitting, “money laundering for bias” …</li>
</ul>
</dd>
</dl></li>
<li><dl>
<dt>Exercise</dt>
<dd>Identify three “AI” systems. For each one, discuss and decide whether it is mainly knowledge-based or mainly statistical/machine-learning-based.
</dd>
</dl></li>
<li><dl>
<dt>Topic 2: Critical Technical Practice & the Ethics of AI</dt>
<dd>Explanation of Agre’s and Harrell’s work. Examples from recent high-profile AI incidents including Microsoft’s “Tay” chatbot, noise-based attacks on Google’s image classifiers, MaxMind’s IP mapping, Facebook’s algorithmic feed emotion manipulation research, automated sentencing/parole…
</dd>
</dl></li>
<li>Topic 3: IPython. How to submit assignments. Q&A.</li>
<li>What worked:
<ul>
<li>AI and ethics examples, group activity, pretty much every active learning segment got some response except “name some AI techniques”, ethics material.</li>
</ul></li>
<li>What didn’t work:
<ul>
<li>Arriving late (ugh), rushing through critical technical practice material.</li>
</ul></li>
<li>What to change for next time:
<ul>
<li>More active learning and student-driven exampling, less lecture, shorter reading addressed across more days.</li>
</ul></li>
<li><dl>
<dt>Assignment 1</dt>
<dd>Individual (short) assignment.
</dd>
</dl>
<p>Pick an AI system, describe it briefly, and explain its “perspective.” Who wrote this system and for what purpose? Who uses the system—are their goals aligned with those of the system authors? From a knowledge representation standpoint, how does it view the world? Which concepts are central, and which concepts are peripheral? How does this system interact with humans, and what does it know or assume about the humans who use it? How could a hostile user or third party subvert this system and break it or harrass/injure other users? Consult the documentation of this system, or articles written about it, if necessary. Write at least 300 words.</p>
<em>TAs could help students think of or explicate AI systems and draw out answers to these questions. Enterprising students could write more, engaging with the subject more deeply; or compare two or more different AI approaches to the same problem, with respect to the criteria above.</em></li>
<li><dl>
<dt>Assignment 2</dt>
<dd>Individual (short) assignment.
</dd>
</dl>
<p>Submit an IPython notebook with a Markdown cell briefly introducing yourself: your background in programming and/or AI, what you hope to gain from this course, and your favorite hobby or hobbies outside of programming (and even outside of computing).</p>
Also include a Python cell which prints out your name using the <code>print()</code> function.</li>
</ul></li>
<li>Day 2: Python, data structures, and algorithms
<ul>
<li>Topic 1: Building and processing interesting data structures
<ul>
<li>Get students to do the typing as much as possible</li>
<li>Python basics
<ul>
<li>Print each number between 1 and 10
<ul>
<li>for x in range</li>
</ul></li>
<li>Functions with ordered and keyword arguments</li>
<li>Draw an image in IPython</li>
<li>Random numbers</li>
</ul></li>
<li>Tuples, arrays, dicts
<ul>
<li>reverse a list, animal sounds</li>
<li>plot a graph in IPython</li>
<li>For x in y</li>
</ul></li>
<li>Classes
<ul>
<li>define and use custom objects</li>
<li>animal sounds 2—but don’t worry about inheritance for now, just polymorphism and info hiding</li>
</ul></li>
<li>Iterative functions (and stacks/queues/pointers)</li>
<li>Recursive functions (and accumulators)</li>
</ul></li>
<li>Topic 2: State machines and string recognizers
<ul>
<li>CS theory basics</li>
<li>Languages, intersection and union</li>
<li>Finite (word) automata</li>
<li>Deterministic vs nondeterministic</li>
<li>Extensions (symbolic FA, pushdown automata, counter automata, timed automata)</li>
<li>“Inspired by” (behavior trees, …)</li>
</ul></li>
<li>Exercise:
<ul>
<li>Pair up</li>
<li>Pick an agent from your experience (video game character, routine worker, animal, robot, …) and write out (possibly repetitive) sequences of actions they might perform (it’s okay to indicate cycles or similar with “…” or what-have-you) OR pick a string language and enumerate examples</li>
<li>What are the “letters”—basic actions—and what are the states?</li>
<li>Draw a state machine that captures that language of actions</li>
</ul></li>
<li>Topic 3: Graph traversal
<ul>
<li>(Quick: state machine implementation strategies)</li>
<li>Basic graph theory (trees)</li>
<li>Depth-first vs breadth-first
<ul>
<li>Ask for pseudocode (recursive AND iterative)</li>
</ul></li>
<li>Directed graphs, DAGs, and general graphs</li>
<li>Complications for depth- and breadth-first in presence of cycles
<ul>
<li>Ask for pseudocode (recursive AND iterative)</li>
</ul></li>
</ul></li>
<li>What worked:
<ul>
<li>State machine exercise. Many students knew Python already so that material was successful.</li>
</ul></li>
<li>What didn’t work:
<ul>
<li>Rushing through tree/graph material, not having a 100% prepared set of examples for Python learning.</li>
</ul></li>
<li>What to change for next time:
<ul>
<li>More active learning and student-driven exampling, a little less state machine theory material (save it for a subsequent day) and a little more tree/graph material, maybe even before the state machines.</li>
</ul></li>
<li><dl>
<dt>Assignment</dt>
<dd>Individual (short) assignment. Write two state machine evaluators for deterministic finite word automata: one which takes a state machine representing a language along with a string, and checks whether the machine accepts the string; and another which takes such a state machine and generates strings from it.
</dd>
</dl>
<em>We’ll provide the state machine data structures. Students with extra time could write a regular expression parser, or write functions to take the intersection or union of two languages, or visualize the evaluation steps using e.g. <code>pillow</code>.</em></li>
</ul></li>
<li>Day 3: Search and Planning
<ul>
<li>Reading
<ul>
<li>Red Blob Games’ <a href="http://www.redblobgames.com/pathfinding/a-star/introduction.html">A* tutorial</a></li>
<li>Excerpts from Sutton & Barto’s reinforcement learning book <span class="citation">(1998)</span> (available <a href="https://webdocs.cs.ualberta.ca/~sutton/book/ebook/the-book.html">here</a>):
<ul>
<li>Sections 1.1–1.5</li>
<li>Section 2.1</li>
<li>Sections 3.1–3.3 (and as much of chapter 3 as you have time for)</li>
</ul></li>
<li>At least section 3 (“MONTE CARLO TREE SEARCH”) of Cameron Browne et al’s <a href="http://repository.essex.ac.uk/4117/1/MCTS-Survey.pdf">survey of MCTS methods</a></li>
</ul></li>
<li>Topic 1: Posing problems as graph search. Example: PuzzleGraph. Heuristic search (A*). Exploit/explore. Discrete constraint problems too (n-queens). Graph vs grid representations of space.
<ul>
<li>Recommend following the links from RedBlobGames’ tutorial as well.</li>
</ul></li>
<li>Exercise: Pair up. Pick an interesting problem and try to phrase it as “search” or planning. What are the operators at a given state? What are reward values at the end? Do operators have costs? Etc. Candidates include: transforming mathematical formulae, solving some logic puzzle, graph coloring, cooking…</li>
<li>Topic 2: MCTS, expected value, and backpropagation of reward
<ul>
<li>How do I calculate expected value?</li>
<li>Tree policy: How do I pick action? uniform random, weighted random, random among untried possibilities, … balancing exploit/explore</li>
<li>Default policy: How do I pick action? Want to explore as much as possible?</li>
<li>Backpropagation: max, decay, …</li>
</ul></li>
<li>Topic 3: Reinforcement learning: the problem, the basic idea, how it differs from MCTS (MCTS is a special case)
<ul>
<li>“MCTS estimates temporary state values in order to decide the next move, whereas TDL learns the long-term value of each state that then guides future behaviour”—mcts guesses more</li>
</ul></li>
<li>What worked:
<ul>
<li>Graph search, A* material, MCTS explanation, small-group activity</li>
</ul></li>
<li>What didn’t work:
<ul>
<li>RL material wasn’t prepared thoroughly enough</li>
<li>Maze should have been an immutable value object!</li>
</ul></li>
<li>What to change:
<ul>
<li>Needed more active learning opportunities, more specific RL material, too many different topics in one day (nobody had time to do enough reading).</li>
</ul></li>
<li><dl>
<dt>Assignment</dt>
<dd>Individual or pair (long) assignment. (1) should be done by tomorrow, (2) and (3) by Monday.
<ol style="list-style-type: decimal">
<li>Write a Python program to solve switch and door puzzles with one of the heuristic search algorithms described during the lecture. <em>(We’ll provide a Puzzle class and sample puzzles, and maybe a function to draw puzzles or solution paths to the console or an image?)</em> Try it on the provided sample puzzles; if some puzzles give your program trouble, try to explain why that happens.</li>
</ol>
</dd>
</dl>
<ol start="2" style="list-style-type: decimal">
<li><p>Once you have this working, write an agent which finds a policy for a “blind” puzzle using MCTS. “Blind” puzzles are just like the puzzles above, only (1) you don’t get to see the whole puzzle or know the goal states in advance, and (2) some nodes are trap doors with a chance of dropping the player into a bottomless pit! Try different policies for deciding between exploit/explore and for doing rollouts and compare them. <em>(We’ll provide a BlindPuzzle class and sample mazes, and maybe a function to draw mazes or maze paths to the console or an image?)</em></p></li>
<li><p>Do (2) but with reinforcement learning. Compare state-value vs action-value learning vs MCTS in terms of iterations required to reach a certain score, etc.</p></li>
</ol>
<em>(TAs could help with writing the code or understanding the algorithms. Eager students could implement multiple algorithms, select one on the fly, generate mazes, visualize the path-finding algorithms.)</em></li>
</ul></li>
<li>Day 4: Intro to probability and probabilistic programming
<ul>
<li><strong>Note: also need to do intermediate evaluations at the end of the day</strong></li>
<li>Topic 0: Feedback/notes on yesterday’s assignment
<ul>
<li>Ask the TAs for code to let you put Maze objects into sets or use them as keys in dicts. I meant to include that from the start. This lets you avoid tricks like turning the Maze into a string for this purpose.</li>
<li>NOTE: If you put a Maze into a set or use it as a dict key, don’t modify it at all afterwards (e.g. via <code>move_player</code>, <code>toggle</code>, or setting its variables)! Only clone it and change the clones—otherwise the set/dict will break in super confusing ways.</li>
</ul>
<ol style="list-style-type: decimal">
<li>Should use <code>m.move_player()</code> and <code>m.toggle()</code> to modify game state and not e.g. check if <code>m.grid[y][x] == "#"</code></li>
<li>Since this is destructive, they should copy the maze using <code>m.clone()</code> before making a move</li>
<li>They can’t (easily) use a distance grid because switching switches changes which doors are open and closed, so player position doesn’t suffice to represent world state, so:</li>
<li>They need to track whether a maze has been seen before. One way is to use a set to track seen mazes.</li>
<li>They need to track the cost and predecessor state along with Maze states. Some ways of doing that include:
<ul>
<li>Add <code>cost</code> and <code>predecessor</code> properties to maze objects.</li>
<li>Include <code>cost</code> and <code>predecessor</code> with the maze in the frontier in a tuple. Of course, using priority queues the tuple’s first element should be <code>g(n) + h(n)</code> where <code>g(n)</code> is the real cost to reach node <code>n</code> and <code>h(n)</code> is the heuristic value (e.g. Manhattan distance from goal) at <code>n</code>.</li>
<li>Keep a <code>costs</code> dict and a <code>predecessors</code> dict or a <code>best_paths</code> dict keyed by Maze objects.</li>
</ul></li>
</ol></li>
<li>Topic 1: Basic probability/Bayes rule
<ul>
<li>what probability of an event means</li>
<li>P(X) – cases where X happens / all possible cases</li>
<li>P(X, Y) – cases where both X and Y happen / all possible cases</li>
<li>If X,Y independent, then P(X,Y) = P(X) P(Y)</li>
<li>P(X | Y) = P(Y|X) P(X) / P(Y) – or equivalently, P(Y,X) = P(X|Y) P(Y) / P(X)</li>
<li>Chaining: P(G,S,R)=P(G | S,R) P(S | R) P(R)</li>
<li>I like the <a href="https://en.wikipedia.org/wiki/Conditional_probability">wikipedia page</a> on conditional probability too</li>
<li>Bayesian statistics
<ul>
<li>Prior (background belief) and posterior (after considering prior) probability</li>
<li>Not, “What is the chance of X happening”, but “Given my background knowledge/superstition/experience, what is the chance of X happening?”</li>
<li>Example priors: Uniform/flat prior; or:
<ul>
<li>“An example is a prior distribution for the temperature at noon tomorrow. A reasonable approach is to make the prior a normal distribution with expected value equal to today’s noontime temperature, with variance equal to the day-to-day variance of atmospheric temperature, or a distribution of the temperature for that day of the year.”</li>
</ul></li>
<li>Priors are really important but we don’t have time to get too deeply into them</li>
</ul></li>
<li>Bayes nets</li>
<li>Given P(X | Y), P(X), and P(Y), we can find P(Y | X) with Bayes rule</li>
<li>P(X)=“Chance of rain”, P(Y)=“chance of clouds”: “Chance of rain when it’s cloudy = chance of clouds * chance of clouds given rain / chance of rain”</li>
<li>Bayes nets</li>
<li>Random variables and expected value
<ul>
<li>P(X=x)</li>
<li>“probability-weighted average of all possible values”</li>
</ul></li>
<li>Distributions (normal, poisson, negative binomial), mean/variance, and PDFs</li>
</ul></li>
<li>Exercise: Make a bayes net for some situation. It’s okay to use e.g. “low/medium/high” for the probabilities in the tables.</li>
<li>Topic 2: Probabilistic programming
<ul>
<li>Programming with distribution variables</li>
<li>“probabilistic programming languages extend a well-specified deterministic programming language with primitive constructs for random choice” <span class="citation">(Goodman and Stuhlmüller 2014)</span></li>
<li>“If we view the semantics of the underlying deterministic language as a map from programs to executions of the program, the semantics of a PPL built on it will be a map from programs to distributions over executions. When the program halts with probability one, this induces a proper distribution over return values.” <span class="citation">(Goodman and Stuhlmüller 2014)</span></li>
<li>WebPPL examples</li>
</ul></li>
<li>Topic 3: Let’s talk about projects
<ul>
<li>Project format</li>
<li>Project suggestions</li>
</ul></li>
<li>What went well:
<ul>
<li>Basic probability, Bayes nets and exercise, connection to ML, WebPPL</li>
</ul></li>
<li>What went poorly:
<ul>
<li>Bayes rule. Typo in my notes, stumbled, ended up with a result I couldn’t interpret well.</li>
</ul></li>
<li>What to do next time:
<ul>
<li>Should have practiced the Bayes Rule part of the lecture specifically!</li>
<li>Should have had more examples of belief nets in the bag.</li>
</ul></li>
<li><dl>
<dt>Assignment 1</dt>
<dd>Individual (small) assignment.
</dd>
</dl>
Give me a list of three or more project ideas you might be interested in doing, either from the suggestions or your own idea. If you have a partner or partners in mind, let me know as well. Submit them (as Markdown <code>.md</code> files) in the folder <code>projects/4-project-ideas</code>.</li>
<li><dl>
<dt>Assignment 2</dt>
<dd>Individual (small) assignment.
</dd>
</dl>
Fill out the preliminary evaluation form and send it to a TA. They’ll anonymize them and send them on to me so I can adjust the course based on your feedback. You can find the form in the <code>projects/4-evaluations</code> folder.</li>
<li>Assignment 3: MCTS and Reinforcement Learning agents for maze solving.</li>
<li><dl>
<dt>Assignment 4 (Optional)</dt>
<dd>Individual or pair (small) assignment.
</dd>
</dl>
<p>Make a probabilistic program expressing your Bayesian model from earlier today. Try to give it a prior based on your intuition, or by loading up a dataset. Either PyMC3 or WebPPL is fine.</p>
Submit it as an <code>.ipynb</code> or a <code>.wppl</code> file in <code>projects/4-probabilistic</code>.</li>
</ul></li>
<li>Day 5: Creative AI
<ul>
<li><dl>
<dt>Reading (do it this afternoon/tonight, since I didn’t get it ready in advance. It will help with the assignment!)</dt>
<dd>Kate Comptons’s classic <a href="http://galaxykate0.tumblr.com/post/139774965871/so-you-want-to-build-a-generator">procedural content generation post</a> and <a href="http://www.crystalcodepalace.com/tracery">tracery tutorial</a>
</dd>
<dd>Look at some <a href="http://cheapbotsdonequick.com">cheap bots done quick</a> bots
</dd>
<dd>Look at <a href="http://ncase.me/simulating">emoji world</a>
</dd>
<dd>Look at some <a href="https://twitter.com/deepforger?lang=en">deep forger</a> examples
</dd>
</dl></li>
<li>Note: <a href="http://events.nucl.ai/program/tracks/">Nucl.ai</a> just started streaming! Check it out in your down time.</li>
<li>Topic 0: MCTS/RL recap</li>
<li>Topic 1: What is creative AI? Let’s go through some examples.
<ul>
<li>Importance of framing, anthropomorphizability</li>
<li>Not about “right answers”, but “feels right” or “interesting” or “visualizing possibilities” or “helping creators”</li>
</ul></li>
<li>Exercise: Think of examples?</li>
<li>Topic 2: Planning, hierarchical planning, and planning for story/music/etc generation
<ul>
<li>World model</li>
<li>Hierarchical decomposition</li>
</ul></li>
<li>Exercise: Break down a storyworld/genre/music-style/art-composition/etc into planning operators/world models?</li>
<li>Topic 3: Grammars (special case of above) and Tracery
<ul>
<li>Grammars + objectives ~~ planning</li>
</ul></li>
<li>Topic 4: Artificial life: Cellular automata and genetic algorithms/evolutionary search
<ul>
<li>CAs, what they are, how they work</li>
<li>GAs, special type of search, how they work</li>
</ul></li>
<li>What went well:
<ul>
<li>ALife, GAs, MCTS recap, idea of creative AI and overview, planning domains</li>
</ul></li>
<li>What went poorly:
<ul>
<li>Grammar overview, group “creative AI” exercise didn’t go as deep as I’d hoped, didn’t get to the planning exercise</li>
</ul></li>
<li>What to do next time:
<ul>
<li>Planning exercise; more grammar examples prepared</li>
</ul></li>
<li><dl>
<dt>Assignment 1:</dt>
<dd>Individual or pair (medium-length) assignment. Get it started today and try to finish it by the end of the week. Go as far as you can with it.
</dd>
</dl>
<p>Make a Tracery grammar to generate some interesting artifact: Genre stories, TV episodes, SVG images, Emoji compositions, musical leitmotifs, classified ads, inspirational quotes, fantasy game items, small programs… and use it somehow, maybe in a Twitter bot (using cheapbotsdonequick) or in some other context.</p>
<p>AND/OR</p>
Make an emoji world simulation, under similar constraints as above: go as far as you can!</li>
</ul></li>
<li>Day 6: Formal Logic & Prolog Crash Course
<ul>
<li>Reading, in this order:
<ul>
<li>Art of Prolog, chapter 1</li>
<li>Kowalski’s “Algorithm = Logic + Control”</li>
<li>Art of Prolog, chapter 6 if you have time</li>
</ul></li>
<li>Topic 1: Propositional logic and inference
<ul>
<li>Why logic?</li>
<li>Propositional logic basics: propositional variables, and, or, not, implies</li>
<li>Queries</li>
<li>Horn logic and resolution: mechanical proof</li>
<li>Existential and universal quantifiers</li>
<li>Queries with logic variables, and uninterpreted functions</li>
</ul></li>
<li>Topic 2: Prolog and proof search. “Old school” symbolic AI stuff.
<ul>
<li>First, mention Prolog is used in Watson and other query answering systems</li>
<li>Prolog rules and queries</li>
<li>Logic variables again</li>
<li>Knowledge bases</li>
<li>Graphs</li>
<li>Planning with temporal logic and event calculus</li>
<li>General game playing</li>
</ul></li>
<li>Exercise:
<ul>
<li>Pair up. Pick a domain distinct from the family tree example and write some first-order logic/Prolog rules (on paper) for a knowledge base about that domain. Include facts, some rules, and some example queries. Some example domains:
<ul>
<li>Romantic interests/dating compatibility</li>
<li>Car features, options, prices, and ratings</li>
<li>Types of animals/animal-guessing game knowledge base</li>
<li>…</li>
</ul></li>
</ul></li>
<li>Topic 3: Prolog data structures
<ul>
<li>Lists and recursion
<ul>
<li>member/2
<ul>
<li>member(E,[E|_]). member(E,[_|L]) :- member(E,L).</li>
</ul></li>
<li>append/3
<ul>
<li>append([],L,L). append([H|T],L,[H|L2]) :- append(T,L,L2).</li>
</ul></li>
<li>path/3
<ul>
<li>path1(E,E,[]). path1(S,E,[S|P]) :- edge(S,M), path1(M,E,P).
<ul>
<li>but: cycles in DFS! let’s do iterative deepening instead by fixing path length each time:</li>
</ul></li>
<li>path2(S,E,P) :- length(P,_), path1(S,E,P).</li>
</ul></li>
</ul></li>
<li>Numerical operations, math, and constraints: #=, #=, #>, #<, #>=, #=<</li>
<li>Functors, including “,”</li>
</ul></li>
<li>What went well:
<ul>
<li>Knowledge bases, basic propositional logic, derivations, starter Prolog, KB exercise</li>
</ul></li>
<li>What went poorly:
<ul>
<li>Framing narrative, deductive rules, advanced propositional logic, CLP</li>
</ul></li>
<li>What to do next time:
<ul>
<li>Real logic intro, real first order stuff, don’t mix syllogistic stuff and propositional stuff, prepare CLP examples</li>
</ul></li>
<li><dl>
<dt>Assignment:</dt>
<dd>Individual or pair (medium-length) assignment. (SKIPPED, maybe something like this on Monday)
</dd>
</dl>
Write a maze solver or other planning problem in Prolog. It’s OK if it’s simpler than the Python maze or doesn’t return paths; the key thing is to specify what movement through a maze means, and derive the solution algorithm automatically from that. Good starting points might be, “recognizing a tweet of up to 140 characters” or “confirming a maze solution of fewer than N steps”.</li>
</ul></li>
<li>Day 7: Machine learning as function approximation
<ul>
<li>Topic 1: Error minimization and regression/gradient descent
<ul>
<li>Today we’re focusing on supervised learning.</li>
<li>Inputs, outputs/labeling, function approximation, feature design, curse of dimensionality, …</li>
<li>Separability, linearity, …</li>
<li>Test set vs validation set, dropout, overfitting, stochastic gradient descent, …</li>
<li>What does this have in common with MCTS?</li>
</ul></li>
<li>Exercise: Pick a data set and design some features/inputs/outputs. Is your data easy or hard to collect?</li>
<li>Topic 2: Perceptrons and perceptron learning
<ul>
<li>Perceptron: vector of inputs -> output boolean, learn vector of weights and bias y = (wx+b > 0); usually formulated with input x0 = 1 and w0 = b and y = (wx > 0)
<ul>
<li>Classification problem</li>
<li>Initialize all weights to small random values (used to suggest all zeroes, but this suggestion works better with the stochastic gradient descent methods used for training bigger NNs)</li>
<li>cost function: How to score a predicted output vs the actual labeled output</li>
<li>learning = descending the gradient of the cost function</li>
<li>Perceptron is a linear function, so it’s differentiable.</li>
</ul></li>
<li>Learning algorithm: For each sample input/output, evaluate y = wx (no > 0 here); compare y vs desired output d; update each weight wi += c(d, y) * xi. (e.g. c(a,b) = a - b)
<ul>
<li>Example on some linear thing</li>
<li>Will it converge? Yes, iff linearly separable.</li>
<li>Let’s try it on XOR and see</li>
<li>If not linearly separable, will it get close to an approximate answer? NO</li>
</ul></li>
</ul></li>
<li>Topic 3: Multilayer perceptrons, if there’s time. Or multiclass.</li>
<li>What went well:
<ul>
<li>General ML intro, data set exercise, most perceptron stuff. Overall a pretty good day.</li>
</ul></li>
<li>What went poorly:
<ul>
<li>Derivation of perceptron weight updates, until I found my feet and said it the right way</li>
</ul></li>
<li>What to do next time:
<ul>
<li>Run through the derivation once for practice, should have written down my insight from this morning about “dw/derror”.</li>
</ul></li>
<li><dl>
<dt>Assignment:</dt>
<dd>Write a perceptron yourself, classify something.
<ul>
<li>Finish implementing the <code>perceptron</code> function and implement the validation logic for the last (random points above/below a line) example.</li>
<li>Tweak parameters, training vs validation set size, number of training epochs, noisiness of the data, etc, and take notes on how accuracy changes.</li>
<li>If you can, find a dataset with a binary output label and train a perceptron on it.</li>
</ul>
</dd>
<dd>Install scikit-neuralnetwork or Keras
</dd>
</dl></li>
</ul></li>
<li>Day 8: Deep Neural Networks
<ul>
<li><strong>Note: need to finalize projects by end of today or tomorrow</strong></li>
<li><dl>
<dt>Reading</dt>
<dd>http://deeplearningbook.org, especially chapters 6, 9, 14
</dd>
<dd>Side references: NEAT, https://nucl.ai/blog/extreme-style-machines/
</dd>
</dl></li>
<li>Topic 1: Deep neural networks (and intro to scikit-neuralnetwork)
<ul>
<li>Most neural networks have many “hidden” layers between the inputs and outputs, not just the one layer described yesterday
<ul>
<li>The “> 0” bit is a kind of “output transformation” from activation values to classes.</li>
</ul></li>
<li>Are those networks made out of linear perceptrons like yesterday, or something else?
<ul>
<li>By analogy to non-linear neuron firing “activation”, we use activation functions that are “nearly” linear. The default suggestion is ReLU (rectified linear units) because they’re simple and cheap to calculate and don’t have the same saturation issues as sigmoids (becoming insensitive to inputs)</li>
<li>However, for output units sigmoids are still used in predicting binary variables (and softmax for multi-class prediction): ensure there’s always a strong gradient when you have a wrong answer.</li>
<li>The loss function has to be designed with the output layer in mind</li>
<li><a href="http://www.deeplearningbook.org/contents/mlp.html">Citations for above</a></li>
</ul></li>
<li>Learning in deep networks
<ul>
<li>Backpropagation, similar to RL/MCTS but using derivatives</li>
<li>“back-propagation refers only to the method for computing the gradient, while another algorithm, such as stochastic gradient descent, is used to perform learning using this gradient”</li>
<li>Find gradient (partial derivative) of cost function WRT parameters, then try to climb down that gradient by tweaking parameters. (dweight/derror is what we want to find)</li>
</ul></li>
</ul></li>
<li>Break and project idea talk</li>
<li>Topic 2: Image recognition and convolution
<ul>
<li>LeCun, 1989</li>
<li>Useful if your data has a grid topology, e.g. time series (1d) or image data (2d) or video (3d) or …</li>
<li>Anyone know what convolution is? It’s a kind of operation on matrices, and convolutional nets “just” use convolutions instead of multiplications in one or more of their layers.</li>
<li>Convolution is more or less a weighted average considering nearby elements more strongly than far-away ones.</li>
<li>For example, for a 2D image there’s a nested sum and a 2D weight function
<ul>
<li>“kernel”, like in image processing</li>
<li>What happens at the edges of the image?</li>
</ul></li>
<li>If a regular neural network lets every input unit react with every output unit equally, convolutions enforce some locality and admit smaller, more efficient networks (or equivalently, similarly sized networks that extract more medium-level features)
<ul>
<li>Multiple convolution layers can build up high level structures starting from the low level inputs</li>
</ul></li>
<li>One layer: Convolve to linear activations->Run through nonlinear activation function like ReLU (“detector”)->pool local groups into summary statistics (to achieve e.g. translation invariance)</li>
</ul></li>
<li>Break and project idea talk</li>
<li>Topic 3: Auto-encoders
<ul>
<li>(1987 and onwards)</li>
<li>Neural net trained to try copying input to output</li>
<li>Design them to be unable to learn perfect copying, so that their approximate copies only “resemble” the inputs, to learn useful/typical/important properties of the data</li>
<li>Often, we care more about the learned parameters than the actual outputs</li>
<li>Why is this useful?
<ul>
<li>Dimensionality reduction, feature learning…</li>
<li>Denoising, reconstruction, …</li>
<li>A colleague uses these for Magic: The Gathering card generation from partial examples</li>
</ul></li>
</ul></li>
<li><dl>
<dt>Assignment:</dt>
<dd>Try writing a convolutional image classifier or an autoencoder, following example code for your chosen deep learning framework.
</dd>
</dl></li>
</ul></li>
<li>Day 9: Computer History Museum
<ul>
<li>Assignment: If we haven’t talked about your project ideas yet, find me and talk to me.</li>
<li><p>Assignment: Explication of a historical AI system.</p>
<p>Pick an AI system you see or see referenced in the museum, or consult a Wikipedia article or the course reader (the section just before Kowalski’s paper talks about a few historical AI systems remade in miniature in Prolog). Explicate it as you did on the first day:</p>
<p>Describe it briefly and explain its “perspective.” Who wrote this system and for what purpose? Who uses the system—are their goals aligned with those of the system authors? From a knowledge representation standpoint, how does it view the world? Which concepts are central, and which concepts are peripheral? How does this system interact with humans, and what does it know or assume about the humans who use it? How could a hostile user or third party subvert this system and break it or harrass/injure other users? Consult the documentation of this system, or articles written about it, if necessary. Write at least 300 words.</p></li>
</ul></li>
<li>Day 10: Intermediate Prolog techniques; recurrent neural networks.
<ul>
<li><dl>
<dt>Reading</dt>
<dd>ML:
<ul>
<li>“The Unreasonable Effectiveness of RNNs” (Blog post)</li>
<li>deeplearning.org chapter 10, 11</li>
<li>http://karpathy.github.io/2016/05/31/rl/</li>
</ul>
</dd>
<dd>Prolog:
<ul>
<li>Art of Prolog, chapter 14</li>
</ul>
</dd>
</dl></li>
<li>Topic 1: List/tree processing and meta-interpreters. Prolog in Prolog.</li>
<li>Topic 2: RNNs and string-to-string translation
<ul>
<li>Recurrent NNs: NNs with cycles.</li>
<li>Unrolling. Show diagram.</li>
<li>backpropagation through time.</li>
<li>LSTM
<ul>
<li>Input, output, forget gates collect activations from inside and outside the block, and control the activation of the cell via multiplications (small black circles). The input and output gates multiply the input and output of the cell while the forget gate multiplies the cell’s previous state. No activation function is applied within the cell. Gate activations usually logistic sigmoid, cell input and output usually logistic sigmoid but sometimes output is identity function.</li>
</ul></li>
</ul></li>
<li>Project talk.</li>
<li>Assignment: Work on projects.</li>
</ul></li>
<li>Day 11: Argumentation and Non-Monotonic Logics
<ul>
<li><dl>
<dt>Reading</dt>
<dd>At least Nute’s defeasible logic paper.
</dd>
</dl></li>
<li>Topic 1: Reasoning with exceptions; non-binary logic; defeasible logic, deontic logic, …</li>
<li>Topic 2: Reasoning about counterfactuals</li>
<li>Topic 3: Evaluating arguments</li>
<li><dl>
<dt>Assignment:</dt>
<dd>Individual (medium-length) assignment.
</dd>
</dl>
<p><em>Todo: clean up.</em></p>
<p>Encode some argumentation logic or legal thing or social thing or artistic thing or…</p>
Generate argument trees using a meta-interpreter and evaluate their quality. Provide a writeup describing your rationale and showing some example claims, arguments, and evaluations. There should be a couple of arguments generated for each claim so we (human readers) can see differences in the evaluations. If there’s no “subjectivity” in the argumentation, you’re probably not doing it right!</li>
</ul></li>
<li>Day 12: Project workshopping and research talk. Or more Prolog stuff, general game playing? Or other topics related to the projects?</li>
<li>Day 13: Presentations 1. New directions in AI.</li>
<li>Day 14: Presentations 2.</li>
</ul>
<h1 id="references" class="unnumbered">References</h1>
<div id="refs" class="references">
<div id="ref-dippl">
<p>Goodman, Noah D, and Andreas Stuhlmüller. 2014. “The Design and Implementation of Probabilistic Programming Languages.” <a href="http://dippl.org" class="uri">http://dippl.org</a>.</p>
</div>
<div id="ref-sutton1998reinforcement">
<p>Sutton, Richard S, and Andrew G Barto. 1998. <em>Reinforcement Learning: An Introduction</em>. Vol. 1. 1. MIT press Cambridge.</p>
</div>
</div>
</body>
</html>