CS 271 Intro AI Fall 2009
Instructor: Max Welling
Office hours: Wednedays 1-2pm
The goal of this class is to familiarize you with the basic principles of artificial intelligence.
The course will primarily be lecture-based (Mondays and Wednesdays) while Fridays will be reserved for the students
to present papers and progress on their project.
Your grade will be based on your project results and class presentations (50%) and your final exam (50%).
Homework is mandataory but will not contribute to your final grade (unless you fail to submit your HW).
It's very important that you try each HW exercise, it's not important that you get it right the first time.
[HW-4 Solutions-partA; HW4-solutions-partB]
Week 1: Ch-2:agents [ppt] [pdf]
Week 2: Ch-3:intro search [ppt] [pdf]
Week 3:Ch-3:uninformed search [ppt] [pdf] ;
Ch-4 infomed search [ppt] [pdf]
Week 4 : Ch-4: Local Search [ppt] [pdf]
Week 5: Ch-5: Constraint Satisfaction [ppt] [pdf]
Week 6: Ch-6: Games [ppt] [pdf]
Week 7: Ch-7: Propositional Logic Part-I: [ppt] [pdf]; Part II: [ppt] [pdf]
Week 8: Ch-8: First Order Logic: [ppt] [pdf];
Week 9: Ch-9: Inference in First Order Logic: [ppt] [pdf];
Week 10: Reinforcement Learning : [ppt] [pdf];
This paper on Cryptogram solvers
Harder paper on CG solving
Invisible hand algorithm
My own Crypto-EM algorithm that you could implement and test as a project.
Homework : (always due the next Monday at midnight)
Reading-book: Chapter 26
Reading-paper: This paper on Cryptogram solvers
Reading-book: Chapter 1&2
Reading-paper: Read Alan Turing's famous1950 paper
Exercises: Exc. 2.1, 2.2, 2.5, 2.6,(due Monday Oct 5 midnight in EEE dropbox)
Week 3:Week 4:
Reading-book: Chapter 3
Reading-paper: Introduction Ant Colony Optimization
Exercises: 3.5 (book) + HW-Ch3 [doc] [pdf] (due Monday Oct 12 midnight in EEE dropbox)
Reading-book: Chapter 4
Reading-paper: Game of Life as a Turing Machines
Exercises: HW -Ch4 [doc][pdf] (due Monday Oct 19 midnight in EEE dropbox)
Reading-book: Chapter 5
Reading-paper: CSPs in AI
Exercises: HW Ch5 [doc][pdf] (due Monday Oct. 26 midnight in EEE dropbox)
Reading-book: Chapter 6
Exercises: HW Ch. 6 [doc] [pdf]
Reading-book: Chapter 7
Exercises: HW Ch. 7 [doc] [pdf]
Reading-book: Chapter 8
Exercises: HW Ch.8 page 268-270: 8.3; 8.6; 8.7; 8.8; 8.15. (due Monday Nov. 16 midnight in EEE dropbox)
Reading-book: Chapter 9
Reading-paper: Paper on Godel's Theorem amd the Mind
Exercises: HW Ch. 9 page 315-318: 9.3; 9.4; 9.9; 9.10a; 9.18; 9.19
Your project will consist of implementing a solver for the Cryptograms. A cryptogram is a piece of text where the letters have been permuted. Your task is to come up with
a solver that decodes a piece of text that is scambled. For instance, can you read this:?
L O K U L D C T L U H Z D Q Q C K V U K N S P D Y Q U T T O J R U E D U S S D K N C K V C T C Y T 2 7 1 . C Z C T P D M D O J K D V J J N Q R Y F !
No I presume? So get to work :-)
It is important that you do your research in the same way that you will do research during your PhD:
-If you were inspired by somebody elses work, make sure you reference that that work.
-Write a paper (with abstract, references etc.) in LATEX where you explain your algorithm.
-Perform experiments to analyze your algorithm. How fast is it? How does it compare to other
algorithms? How accurate is it? What are its weaknesses and strengths?
-Try to be original and not just copy things already done in the literature. Even better,
come up with a related problem and design a solver for that:
-e.g.1) a solver that can handle sentences where the space-bar function is also permuted with some other symbol.
-e.g.2) a solver that can handle mapping where two letters are mapped to the same symbol (information gets lost!)
-e.g.3) a solver based on some relatively unknown algorithm such as "ant colony optimization" or something.
You may work in groups of 5 people at most, but you are required to write your own code and report.
Some useful links:
(A solver by David Eppstein from ICS!)
(general page on Cryptogram solvers)
(If you want to found out what I wrote, copy and paste the coded sentence into this solver. I actually made a type....)
-Birkhoff-von Neumann theorem: A doubly stochastic matrix can always be written as a convex combination of
permutation matrices (a doubly stochastic matrix is a matrix with real positive entries where each row and column sum to one).
You could use this useful theorem in designing an algorithm because searching over the space of stochastic matrices is easier
over the space of permutation matrices.
-Another very useful page is the following list of English words with their frequencies of appearing in text.
(can you already think of a rough outline of an algorithm?)
-My Crypto-EM algorithm that you could implement and test
The following represents a very preliminary syllabus. Expect significant changes.
Introduction: Goals, history (Ch.1)
Uninformed Search (Ch.3)
Informed Search (Ch.4 NOT?? sec.4.5 and after)
Constraint satisfaction (Ch.5).
Propositional Logic (Ch.7 NOT "circuit based agents" on page 227 and after)
First Order Logic (Ch.8 NOT sec. 8.4 and after)
Inference in first order logic (Ch.9 NOT including "Completeness of Resolution" and after, p.300)
AI: Present and Future (Ch 27)
Final: Wed. Dec 9, 4-6 pm
Russel & Norvig : Artificial Intelligence; A Modern Approach.
Denise Garcia knows that her students sometimes cheat, but the situation she unearthed in February seemed different. A math teacher in West Hartford, Connecticut, Garcia had accidentally included an advanced equation in a problem set for her AP Calculus class. Yet somehow a handful of students in the 15-person class solved it correctly. Those students had also shown their work, defeating the traditional litmus test for sussing out cheating in STEM classrooms.
Garcia was perplexed, until she remembered a conversation from a few years earlier. Some former students had told her about an online tool called Wolfram|Alpha that could complete complicated calculations in seconds. It provided both the answers and the steps for reaching them, making it virtually undetectable when copied as homework.
Pippa Biddle is a writer interested in culture, complex systems, and making sense of the world.
Sign up to get Backchannel's weekly newsletter.
For years, students have turned to CliffsNotes for speedy reads of books, SparkNotes to whip up talking points for class discussions, and Wikipedia to pad their papers with historical tidbits. But today’s students have smarter tools at their disposal—namely, Wolfram|Alpha, a program that uses artificial intelligence to perfectly and untraceably solve equations. Wolfram|Alpha uses natural language processing technology, part of the AI family, to provide students with an academic shortcut that is faster than a tutor, more reliable than copying off of friends, and much easier than figuring out a solution yourself.
Since its release, Wolfram|Alpha has trickled through the education system, finding its way into the homework of college and high school students. Use of Wolfram|Alpha is difficult to trace, and in the hands of ambitious students, its perfect solutions are having unexpected consequences. It works by breaking down the pieces of a question, whether a mathematical problem or something like "What is the center of the United States?", and then cross-referencing those pieces against an enormous library of datasets that is constantly being expanded. These datasets include information on geodesic schemes, chemical compounds, human genes, historical weather measurements, and thousands of other topics that, when brought together, can be used to provide answers.
The system is constrained by the limits of its data library: It can’t interpret every question. It also can’t respond in natural language, or what a human would recognize as conversational speech. This is a stumbling block in AI in general. Even Siri, which relies heavily on Mathematica—another Wolfram Research product and the engine behind Wolfram|Alpha—can only answer questions in programmed response scripts, which are like a series of Mad Libs into which it plugs answers before spitting them out of your speaker or onto your screen.
Using Wolfram|Alpha is similar to executing a Google search, but Wolfram|Alpha delivers specific answers rather than endless pages of potentially relevant results. Anyone can go to the Wolfram|Alpha website, type a question or equation into a dialogue box, hit enter, and receive an answer. If you’re trying to solve x2 + 5x + 6 = 0, Wolfram|Alpha will give you the root plot, alternate forms, and solutions. If you are looking for a step-by-step explanation, there is a pro version available for $6.99/month with discounted options for students and educators.
I first heard about Wolfram|Alpha in my parents' kitchen. My father had come home from his job at a private school in Dobbs Ferry, New York. He dropped his bag on the floor, and asked me what I thought about Wolfram|Alpha. Earlier that day he had been confronted by STEM teachers who were frustrated with their students' use of the tool. It was, they said, blatant cheating. My father had left the office unsure of how to proceed. Should the school crack down on Wolfram|Alpha? Or did the school need to catch up to this new beat in education?
I’d never heard of it, but a quick post to Facebook revealed that many of my friends had—especially those studying math. Some had used it to get through college calculus, while a few were still using it at their jobs as engineers or quantitative analysts. The rise of Wolfram|Alpha had completely passed over my humanities-minded head, just as, for millions of minds, it had become ubiquitous. Turning to the tech for answers was, they said, normal. At the same time, all made it clear that they didn’t want their use of Wolfram|Alpha to be made public.
Though Wolfram|Alpha was designed to be an educational asset — a way to explore an equation from within— academia has found itself at a loss over how to respond. What some call cheating, others have heralded as a massive step forward in how we learn, what we teach, and what education is even good for. They say that Wolfram|Alpha is the future. Unsurprisingly, its creator agrees.
Stephen Wolfram, the mind behind Wolfram|Alpha, can’t do long division and didn’t learn his times tables until he’d hit 40. Indeed, the inspiration for Wolfram|Alpha, which he released in 2009, started with Wolfram’s own struggles as a math student. Growing up, Wolfram’s obsession was physics. By 12, he’d written a dictionary on physics, by his early teens he’d churned out three (as yet unpublished) books, and by 15 he was publishing scientific papers.
Despite his wunderkind science abilities, math was a constant stumbling block. He could come up with concepts, but executing calculations was hard. His solution was to get his hands on a computer. By programming it to solve equations and find patterns in data, he could leave the math to the machine and focus his brain on the science. It worked. In 1981, Wolfram became the youngest person to ever receive a MacArthur Fellowship. He was only 21.
Yet the tool that helped Wolfram build his reputation with physics ended up pulling him away from science. Wolfram became obsessed with complex systems and how computers could be used to study them. Five years after receiving his MacArthur Fellowship, Wolfram began developing Mathematica, and in 1988 Wolfram Research announced the release of its flagship product.
Wolfram never planned for his tool to become highbrow CliffsNotes, but he’s not too concerned about it, either. “Mechanical math,” Wolfram argues, “is a very low level of precise thinking.” Instead, Wolfram believes that we should be emphasizing computational thinking—something he describes as “trying to formulate your thoughts so that you can explain them to a sufficiently smart computer.” This has also been called computer-based math. Essentially, knowing algebra in today’s technology-saturated world won’t get you very far, but knowing how to ask a computer to do your algebra will. If students are making this shift, in his mind, they’re just ahead of the curve.
Alan Joyce, the director of content development for Wolfram Alpha, says that cheating is “absolutely the wrong way to look at what we do.” But the staff understands what might make teachers uncomfortable. Historically, education had to emphasize hand calculations, says John Dixon, a program manager at Wolfram Research. That’s because there wasn’t tech to fall back on and, when tech did start to appear, it wasn’t reliable. Only recently can computers calculate things automatically and precisely, and it’ll take some time for curriculums, and the teachers that are beholden to them, to catch up. Wolfram Research, Dixon says, wants to engage with teachers like Garcia, who are frustrated by the tool, to help them understand how it can help their students.
Indeed, the people who are directing the tool’s development view it as an educational equalizer that can give students who don’t have at-home homework helpers—like tutors or highly educated and accessible parents—access to what amounts to a personal tutor. It also has enormous potential within the classroom. A "show steps" button, which reveals the path to an answer, allows teachers to break down the components of a problem, rather than getting bogged down in mechanics. The "problem generator" can pull from real datasets to create relevant examples. “When you start to show educators the potential,” Dixon says, “you can see points where their eyes light up.”
For every teacher who’s converted to Dixon’s camp, there are multitudes of students who have been there for a while. As Alexander Feiner, an aspiring engineer and high school freshman told me, Wolfram|Alpha is a study aid, not a way of avoiding work — something that Dixon insists is the norm when it comes to out-of-classroom student use.
Still, the prevailing notion that Wolfram|Alpha is a form of cheating doesn’t appear to be dissipating. Much of this comes down to what homework is. If the purpose of homework is build greater understanding of concepts as presented in class, Joyce is adamant that teachers should view Wolfram|Alpha as an asset. It’s not that Wolfram Alpha has helped students “‘get through’ a math class by doing their homework for them,” he says, “but that we helped them actually understand what they were doing” in the first place. Dixon believes that Wolfram|Alpha can build confidence in students who don’t see themselves as having mathematical minds. Homework isn’t really about learning to do a calculation, but rather about learning to find and understand an answer regardless of how the calculation is executed.
That’s the route down which education appears to be headed. Once upon a time, education was all about packing as much information as possible into a human brain. Information was limited and expensive, and the smartest people were effectively the deepest and most organized filing cabinets. Today, it’s the opposite.“The notion of education as a transfer of information from experts to novices—and asking the novices to repeat that information, regurgitate it on command as proof that they have learned it—is completely disconnected from the reality of 2017,” says David Helfand, a Professor of Astronomy at Columbia University.
The technology isn’t going anywhere: Like copying out of the back of a book or splitting a problem set among friends, students aren’t likely to stop using Wolfram|Alpha just because a teacher says so. Even Garcia can see a future where Wolfram|Alpha fits in. “I think, in an ideal world, teachers, myself included, need to do a better job of incorporating technology…and finding ways of using it in productive ways,” she says.
Just as robotics has transformed manufacturing, tools like Wolfram|Alpha are forcing us to rethink an educational system by challenging it to rise to the new technological standard. Either we reshape our schools to embrace tools like Wolfram|Alpha, or we risk becoming living artifacts in a rapidly progressing world.