1 Introduction to Artificial Intelligence (AI)Abstract: What is AI? What happened within AI, history? Going deeper: What really is AI? Where AI happens? What will you learn? How will this course go? Prerequisites 12/6/2017 (C) Debasis Mitra

2 Introduction to AI: What is AI?AI Computer Science! Whatever is at the FRONTIER of computer science is AI! It is really about NEW challenges that is CURRENTLY beyond computing Chasing elusive goals! 12/6/2017 (C) Debasis Mitra

3 As soon as “it” is achieved – “it” is no longer AI! AI is really a perception! However, a pattern of topics and problems emerge as we pursue the “dream List of AI problems in text on slide 25: 12/6/2017 (C) Debasis Mitra

4 Introduction to AI: Historical JourneyEarly Computers = Calculator plus stored program The Dream: Neuron model 1943, Turing test, 1950 Look Ma, No Hands! Samuel’s checkers program: game playing Newell-Simon’s Logic Theorist: proving math theorems Geltner’s Geometry Engine: geometry theorems “AI” Dartmouth meeting Knowledge is power: Knowledge-based Systems, Mycin, Dendral, and other expert systems Expert systems industry boom, Fifth generation computing system (Japan), MCC (US) “Smart-X” Deep-learning resurgence, 2010-present 12/6/2017 (C) Debasis Mitra

5 Introduction to AI: Historical JourneyChallenge catches up, Smaller niche areas flourish Integrate: Agent view (text) Large knowledge bases, 1990-present MCC Cyc project / IBM Watson DARPA / SRI International /Apple Iphone Siri Big data to Intelligence Machine learning Handwriting recognition, Speech recognition, by HMM Big data, by Convolutional Neural Net, 2010+ 12/6/2017 (C) Debasis Mitra

6 Introduction to AI: What really is it?Computers manipulate numbers (hardware) Computers can map symbols internally to numbers (Unicode) First AI question: Can programs manipulate symbols? Symbolic AI: Expert systems Second AI question: Is symbol manipulation enough? No! Human intelligence is not just symbol manipulation And it is not efficient either as was thought of initially Third AI question: Should we go back to number manipulations Optimization: Machine learning … Future of AI: Numbers + Symbols! Data types: RealOrdinalPartial orderCategorical 12/6/2017 (C) Debasis Mitra

7 Introduction to AI: Course content<> No “Intelligence” Because, there is no definition of intelligence Search Algorithms Constraint Reasoning Automated Reasoning Probabilistic Reasoning Machine Learning Advanced topics (time permiting!) CV, Robotics, NLP Mid term 1: 20% Mid term 2: 25% Project: 20-30% Final: 30-20% 12/6/2017 (C) Debasis Mitra

8 Introduction to AI: Course content: SamplesSearch Algorithms Blind search Guided search Optimization Constraint Reasoning Consistency levels Back-jumping Randomized algorithms Automated Reasoning Logic First order logic Knowledge-base 12/6/2017 (C) Debasis Mitra

9 Introduction to AI: Course content: SamplesProbabilistic Reasoning Bayesian network Dynamic network Fuzzy logic Machine Learning Decision tree Clustering Training with samples Neural networks 6. Advanced topics Planning Computer Vision Robotics Natural Language Processing Three levels of learning in our course : Tourist-level: definition-concepts Deeper level: Solving exercises Expert level: Coding 12/6/2017 (C) Debasis Mitra

10 Introduction to AI: Where AI HappensIndustry! Frontiers Google, Amazon, Facebook, … start-ups, … Academic AI is far from real life, but Challenges are addressed by new algorithms here “Industry is 10 years behind academics,” a past PhD at Amazon now AIMA: our Text by Russell-Norvig My own humble interest: AI in Science and Engineering Conferences AAAI: Association for Advancement (used to be American  ) of AI IJCAI: International Joint Conference on AI IEA/AIE: Applied AI FLAIRS: Used to be FL AI Research Symposium Journals AI journal Journal of AI Research, online Applied AI … 12/6/2017 (C) Debasis Mitra

11 Introduction to AI: What can you do with this course?Some companies prefer students with AI background Current boom in Data Science (a new name for Data Mining) Helps in other advanced courses Machine learning Computer Vision Scientific computing Computational Molecular Biology Complex network Research in/out our department Specialized algorithms / concepts 12/6/2017 (C) Debasis Mitra

12 Introduction to AI: Pre-Quiz (One sentence each, total 7 min)Name: Level (UG/Grad): Major, if non-CS: What did you know about AI (i.e. your current perception)? If you were to develop an AI program, what would that be on? Name 3 topics that will be covered in this course. Name one of the popular AI software or application. Why are you taking this course (honest answer please)? 12/6/2017 (C) Debasis Mitra

13 Introduction to AI: Required BackgroundList-Queue-Stack- Tree-Graph-Spanning tree- Djikstra- Recursion-Convert to Iteration Combinatorics BigO-Loop Complexity-NP- Programming skill in any high level language: I encourage you to learn Python, it is “hot” now 12/6/2017 (C) Debasis Mitra

14 Introduction to AI: Required Background List-Queue-Stack-(pointer/array) Stack: (data type: data+operation 12/6/2017 (C) Debasis Mitra

15 Introduction to AI: Required Background List-Queue-Stack-(First-in-First-Out) Max/Min Heap / Priority-Queue: (a binary tree to provide Max/Min value quickly O(log N), N nodes) 12/6/2017 (C) Debasis Mitra

16 Introduction to AI: Required Background Tree-Graph-Spanning tree-Graph (V, E): Directed/ Un- Labeled / Un- Weighted / Not- 12/6/2017 (C) Debasis Mitra

17 Introduction to AI: Required Background Tree-Graph-Spanning tree-(Subgraph without loop, but covers all nodes) Many spanning trees possible On weighted graph, Minimum spanning tree= least total wt 12/6/2017 (C) Debasis Mitra

18 Introduction to AI: Required Background Shortest-path findingSingle-source-shortest-path-to-all: (Djikstra’s algorithm) 12/6/2017 (C) Debasis Mitra

19 Introduction to AI: Required Background Recursion-IterationFibonacci series computing: f(n) = f(n-1) + f(n-2), f(0)=f(1)=1 12/6/2017 (C) Debasis Mitra

20 Introduction to AI: Required Background Recursion-IterationIterative fibonacci(n) fib(0) = fib(1) = 1; for i=2 through n do fib(i) = fib(i-1) + fib(i-2); end for; return fib(n). Avoids repetition: 12/6/2017 (C) Debasis Mitra

21 Introduction to AI: Required Background CombinatoricsPermutation-Combination-Factorial-PowerSet Quiz Questions (do later): 20 nodes, how many pair of nodes? 20 nodes, how many triangles possible? 20 nodes, how many subsets of nodes? 20 letters, how many unique words of length 20 possible? 12/6/2017 (C) Debasis Mitra

22 Introduction to AI: Required Background BigO-Loop Complexity-NP-Iterative fibonacci(n) fib(0) = fib(1) = 1; for i=2 through n do fib(i) = fib(i-1) + fib(i-2); end for; return fib(n). What is O(?) here? What is O(?) here? for i in range (1, n) for j in range (1, m) for k in range (1, n) -whatever- Q5. What is O(?) here, in terms of n and m? Q6. What if you replace range of k to (1, 100) 12/6/2017

23 Introduction to AI: Required Background QUIZQuiz Questions: KEY 20 nodes, how many pair of nodes, excluding self loops? 20 choose 2, def of ‘choose’, = 20! / ((20-2)! * 2!) if you include self-loops: above+20 20 nodes, how many triangles possible, excluding repeat nodes, or straight-line triangles? 20 choose 3, = 20! / ((20-3)! * 3!) 20 nodes, how subsets of nodes? 2^20, each element absent/present in the subset, true/false bit-string is often used for subsets of fixed sized sets 20 letters, how many unique words possible for word of length 20? unique lettering: 20!, first position 20 possibilities * next position 19 possibilities * … not unique lettering: 2 0^20, each position 20 possibilities, 20*20* … 20-times max size of word up to 20: ^2 + 20^3 + …+20^20 if no max size is specified: infinity for i in range (1, n) for j in range (1, m) for k in range (1, n) -whatever- 5. What is O(?) here, in terms of n and m?: O(n2m) 6. What if you replace range of k to (1, 100): O(nm) 12/6/2017 (C) Debasis Mitra