Database Systems



Artificial Intelligence

CSE 5290/4301, Fall 2020

Instructor: Debasis Mitra, Ph.D.

Office: OEC 3-- E-mail: dmitra ‘at’ cs.fit. edu

Class Home Page:

Office Hours: MW 2-4pm I will try to be at but you may need to talk first as my video may be off screen (or by appointment)

Grading plan:

Graduate stds: Quizzes (5-10): 15%, Coding exercise: 5%, Exams 40%, Project: 40%

Undergraduate stds: Quizzes (5-10): 20%, Coding exercises: 30%, Exams 50%

All exams/assignments are online

CLASS coordinates: Crawford 210 TR 1530-1645hrs, Zoom URL:

SYLLABUS FOR AI SPRING 2020 FINAL EXAM.

Materials under *---* are excluded. 3.3-3.4.5 means 3.3 through 3.4.5

SEARCH, up to IDA* search, but not SMA*,

Adversarial search (min-max) & alpha-beta pruning is included

Up to materials on my slide Constrained Optimization

Ch 4-4.2

Ch 5-5.3

CONSTRAINTS

Ch 6-6.2.5, 6.3-6.3.2, 6.5 (*use of symmetries on p226*)

Temporal reasoning: My slides

LOGIC

Ch 7.3-7.5.2, *completeness of resolution*, 7.5.3-7.6.2, *walksat algorithm*,

Ch 8.2-8.3

Ch 9-9.2.2, 9.3-9.3.2, 9.4.1, 9.5-9.5.3

PROBABILISTIC REASONING

Ch 13.2-end

Ch 14-14.3, 14.7.2-3

LEARNING

Decision Tree 18 – 18.3.4

Evaluation 18.4-Model Selection 18.4.1

Regularization 18.4.3

Learning Theory 18.5.0 only

Regression 18.6 – 18.6.2

Classification 18.6.3 – 18.6.4

Neural Network 18.7 – 18.7.4 (exclude exotic varieties of NN on my slides)

Non-parametric models 18.8 – 18.8.4

SVM basics 18.9

Clustering basics (from my slides)

ETHICS

My slides

Florida Tech Academic Calendar:

This table will act as our curricular map for the semester. It helps me to track progress and plan next few days of the class, assignments, etc., but I edit this frequently. I keep this online in your view so that you may be in sync with me. However, use it at your discretion.

Meetings: ~ 28. Lectures planned: Search 4, Constraints 3, Automated Reasoning 4, Probabilistic Reasoning 4, Machine Learning 5, Ethics 1,

Exams 3, Std presentations 4

| |Activities (Spring2020) |Comments |

|Aug 18 T |AI an Introduction, and get-to-know Quiz | |

|Aug 20 R |Required CS background list | |

| |Big O-notation (Algo-Intro slide 1-10), | |

| |Djikstra algorithm (Algo-Graph slide 23-25), Min-spanning tree | |

| |algorithm (Algo-Graph slide 54, 57-8) | |

| | | |

| |Complexity Theory - lite | |

|Aug 25 T |AI SEARCH (From my slides): 8-puzzle: | |

| | | |

| |BFS- Uniform Cost; DFS-Depth Limited | |

| |Iterative-deepening | |

|Aug 27 R |Quiz-2 on BFS, DFS, IDS on canvas with pptx file |Graduate projects |

| | |described below this table, Due dates: YTD |

| |Heuristic Search: ucbfs, rules for heuristic function | |

| |MySlides 15-35 |Undergrad students pair up |

| |Text Slide Ch4a |for the Coding Assignment-2. |

| | |A discussion forum may be created on Canvas |

| | |for this – respond there. |

| | |I will check on the pair-names in class later. |

|Sep 01 T |Heuristic Search A*, IDA* |Coding exc-1 for UG announced. Due: 9-29 on canvas |

| | | |

|Sep 03 R |Textslides ch4a on heuristic search |Keeping a copy of slide 5 of Textslides ch4a (Romanian map) |

| |Back to Myslides 29-37 |handy will help in following the lecture today. |

| | | |

| | | |

|Sep 08 T |MySlides (search) 37 summary | |

| | | |

| |Game (Adversarial) search MySlides | |

| | | |

| |Local search from Text-slides Ch4b | |

| |Hill-climbing, Simulated Annealing, Local beam search, Genetic | |

| |Algorithm, Gradient search, | |

| | | |

| |Local search, MySlides continued (38-49) | |

| | | |

| |Remind imp of heuristics in PRUNING search tree; | |

| | | |

| |Skip Constraint Reasoning for now: | |

| |REASONING WITH CONSTRAINTS: Motivating with Map/Graph coloring, | |

| |Backtracking, Forward Checking (TextSlides) | |

|Sep 10 R |Grad project discussion | |

| | | |

| |Local search, MySlides continued (39-49) | |

| | | |

| |Brief intro to artificial neural network: My slides 25, 28, 30, | |

| |32, 36-7, 44 | |

| | | |

| |Constraint Reasoning | |

|Sep 15 T |Grad Project proposal presentation, 10 min each group |Send me updated Project slides (e-mail) by 9/22/T/11:59pm |

| |(UG students must attend: I do ask simple questions on grad | |

| |project | |

| | | |

|Sep 17 R |MySlides,; AC-3, SAT, and SAT-DPLL |A Canvas quiz on Search, 5pm-9am, 20 min |

| |SAT in Algo-complexity slides: 34-8 |* Some figures are uploaded as PowerPoint (SearchFigures.pptx)  for the test where the syllabus is on Canvas. |

| | |* Use the best answer, i.e. read all choices first. |

| |AUTOMATED REASONING (ch 7): Syntax-Semantics-Model, |* Closed book test. Do not refer to any material during the test. |

| |Satisfaction-Entailment-Inference procedure-Validity (up to |* You may need extra papers for scratch work. |

| |TextSlide 41, ch-7) |* Use your honor code to not to talk to anyone about the test during or after the test as long as it is available online. |

| | | |

|Sep 22 T |Automated Reasoning – Forward chaining algo, Backward chaining |Send me updated Project slides (e-mail) |

| |algo. |by 9/22/T/11:59pm |

| | | |

|Sep 24 R |AUTOMATED REASONING – continued: |A sentence not in Horn form: |

| |Repeat: Forward chaining algo, Backward chaining algo (sl#40-66) |P is not true, , ~P=>T |

| |CNF, Resolution Algo (p255), Horn Clause, Definite clause | |

| | | |

| |SAT definition, from my Algo slides | |

|Sep 29 T |AUTOMATED REASONING: First Order / Predicate Logic-Motivation; |Grad Project progress report October 10-R, on Canvas. |

| |Model-Interpretation-Quantifiers-Inferencing | |

|Oct 01 R |AUTOMATED REASONING Algorithms: Unification, Forward Chaining, |UG Project-1 Due at 11:59pm, upload on Canvas. |

| |Backward Chaining, Resolution strategies, | |

| |Completeness-Herbrand Universe, | |

|Oct 06 T |Continued Automated Reasoning | |

|Oct 08, R |A Senior Design Project idea: | |

| | | |

| |Revised Auto-Reasoning | |

| |Sample logic programming codes | |

| | | |

| |Occur check: Substitution like x/S(x) not allowed in most logic | |

| |programming languages, Unification-algo syntactically checks for | |

| |that and fails in that case. Otherwise, x/S(S…(x)…) infinite | |

| |looping – source of semi-decidability of FOL Occur check makes an| |

| |algorithm unsouond! | |

| | | |

| | | |

| |Probabilistic Reasoning |Grad Project progress report October 14-W, on Canvas |

| | |Auto-Reasoning-2 homework, Test moves to next week. |

| |UG Project-2 discussion (below) | |

|Oct 13 T |Probabilistic Reasoning - continued |AutoReasoning Homework-2 on Canvas |

| | | |

| | |Nov 6-R No class meeting (work on projects) |

|Oct 15 R |REASONING WITH UNCERTAINTY: Ch 13: Motivation | |

| |Probability-Joint-Inference-Conditional-Baye’s rule | |

|Oct 20 T |Bayesian network Ch 14 starts. | |

| | | |

| |(Sample exercise Ch13: 13.8, 14, 15 ) | |

|Oct 22 R |Machine Learning, from text-slide Ch18 | Test on Automated-Reasoning/Logic online |

| | |(30 min, 16 questions) starts at 5pm US Eastern, |

| | |due by next day before 12 noon |

|Oct 27 T |Grad projects discussion |Undergraduate Project-2 due 10/28 |

| |UG proj-2 status | |

| | |Short exc on Prob reasoning to be on canvas, |

| |MACHINE LEARNING MySlides: Decision tree, basics |due Oct 29 at 10am |

|Oct 29 R |MACHINE LEARNING: ML-miscellaneous, |Probabilistic Reasoning test: 11/4/W/5pm-11/5/R/10am |

| |Linear regression, linear classification | |

|Nov 03 T |MACHINE LEARNING: Neural Net, Non-parametric learning kNN | |

| |variations | |

| |LSH (start - slide 51), kernel-regression | |

|Nov 05 R |No Class, work on your project | |

|Nov 10 T |Contd. ML Ch 18.9-10: non-parametric SVM | |

| |Clustering basics: K-means, from | |

| | | |

| |K-median, Slide 64 hierarchical, density-based | |

|Nov 11 VeternsDay|--- | |

|Nov 12 R |Clustering: k-means, hierarchical | |

|Nov 17 T |Constraint Reasoning Ch. 6 |Graduate Project Intermediate Report |

| | |(I prefer updated last report, with highlighting of changes/new works, |

| | |as much as possible): Due Friday, 11-20 |

| | | |

| | |Machine learning test, Tuesday evening 11-24 |

| | |You may need to do rough work to answer some questions |

|Nov 19 R | |Graduate Project Final report due |

| | |December 3 by 9pm on Canvas |

| | |Submit commented code, any relevant data, and a final report. You may update the final report but make sure (1) that one can use it for the|

| | |next semester, and (2) it is in doc, not pdf, so that I may copy-paste figures if needed. Provide your results and as many example figures |

| | |as possible. |

| | |All three in a zip file, named using: |

| | |Sp20_project name’s signature id_one group member’s name |

|Nov 24 T |Graduate presentation |FOR GRADING I USE MY OWN SPREADSHEET. |

| | |ON CANVAS, THERE IS A AGGREGATE |

| | |ASSIGNMENT (NULL) THAT CONTAINS |

| |Test on ML, outside class hours: |FORMULAS |

| |Available 4/30/R/9am | |

| |Due 4/30/R/8pm just before the class | |

| |--Download the Table-1 before starting the test— | |

| | |

| |Note: A smartphone may be too small a device to view everything | |

| |for this test. | |

| | | |

|Nov 25-27 | | |

|Thanksgiving | | |

|Dec 01 T |AI and Ethics (my slides are included in syllabus/tests) |Final project report due from each group, |

|(Dec-2 Last day | |both undergrad and grad. |

|of class) |Please do the instructor review. | |

| | | |

| |The closed-book online exam will be for 40 minutes from your | |

| |start time. Only online test, no take-home. You may take the test| |

| |any time between 9am-8pm on 12/10/R. | |

| |You may need to download some tables/figures before starting the | |

| |exam. Having additional rough papers to work on may help. Feel | |

| |free to use calculator but that may not be needed. Test answers | |

| |may available after everybody finishes test Good luck! | |

| |Peace, health, and productivity! | |

| |Above updated for Fall 2020 | |

| | up for evening classes, TR, in that web site |

| |ion-schedules/spring-final-examination-schedule/ | |

|Exam: |

|

|dules/fall-final-examination-schedule/ |

|Thursday, Dec. 10 |

|3:30–5:30 p.m. |

| |

Graduate Project groups:

1. Viet D Nguyen & JordanMurray: Indus-Valley Civilization OCR with deep learning, /Fall2020/Spr20-IVC-AIfinalreport.pdf

Twenty-six original IVC-images are with me. Let me share them with you.

Detection task should be the bounding boxes for Graphemes (characters) in the text.

See SVHN data: , and Goodfellow’s (2013) work and any later results.

I have the code for data augmentation for training set from the last semester.

/Fall2020/sp20_motif_Qi_mike(1).7z

Twenty-six original images are in imges/ directory within the zipped materials. You will need to note each grapheme’s bounding corners in texts before augmenting.

You may like to embed that augmentation code in RetinaNet that they used (again, code on the Internet).

2. RobertBreininger & Afi EE Gbekevi: Topological analysis of hidden patterns in COVID-19 spatio-temporal spread, /Fall2020/Spr20-CovidTimeSeries-report.docx

Learn more on “persistence homology.”

Topological analysis of COVID-19 data: In the previous semester, in this project, persistence homology was used to analyze the COVID-19 data.

Will you like to do more computational topology for this project, or will you like to use some other methods to analyze the data, such as linear regression or principal component analysis, and compare results with that from topological analysis?

3. Jacob Bowers: Reduction of Temporal Automata to Temporal-constraint Network,

Briefly explain where you are now in TaTcn work? What will you do within the scope of this class project.

4. Henry Bay: TB image analysis, also check:



Data source, Images downloaded, Objective of project, PyRadiomics software, …

Proposal presentation in class: Present and briefly explain the problem (and data) you are working on to the class with slides in 10 min. On 9-15-T [10]

A Progress report on 10-8-R. [20]

Undergraduate Project (I may provide more clarifications here):

PROJECT-1: Depth first search (DFS) for Traveling Sales Person (TSP) problem. Create a 50x50 Boolean matrix of all 0’s. Input 5 nodes’ coordinates, insert random arcs between nodes as 1’s in the matrix. One of the shortest-distance Hamiltonian Cycles is the TSP solution. Hamiltonian Cycle (HC) is a subgraph that covers each node once and only once and returns to the starting node. Distance between nodes are Manhattan distances along the matrix. Track complexity with multiple (between 5 to 10, including at least one no-HC case) random input graphs. [This part 1 is an individual assignment, but form groups of 2 for the next stages] [40]

There are two HCs in the following graph with four nodes in color.

Their lengths are respectively 31 and 23. The shorter one is the solution to the TSP.

| | | | | | | | | | | |1 |1 |1 |1 |1 |1 |1 |1 | | | |1 | | | |1 | |1 |1 |1 | | |1 | | | |1 | |1 | |1 | | |1 | | | |1 | |1 | |1 | | |1 | | | |1 | |1 | |1 | | |1 |1 |1 | |1 |1 |1 |1 |1 | | | | |1 |1 |1 | | | | | |Suggestion: Find a Hamiltonian path (a path covering all nodes once and only once, and no cycle yet) using blind-DFS. Then, connect the leaf node to the start node to obtain the HC. Note, you still have to find the shortest-length HC, for solving the TSP. Also note, a graph may not have any HC at all, which should be detected if needed.

Submission (Three files): (1) Source code, (2) Results of running over all your input graphs, (3) Three sample runs explained and visualized by drawing.

Now that I got your attention--

Naive DFS only searches for A goal. For an optimization problem like TSP,  you need to look for all "goals" or all Hamiltonian Circuits (the shortest one is the TSP solution).

This means you have to force DFS to continue even after finding an HC, until all possibilities are exhausted.

You will also need to keep track of the shortest HC found "so-far," to output the best one after all possibilities are exhausted.

BFS will do it but consume much more memory.

Do your best! Write what does your algorithm do briefly alongside your sample results.

Due (tentatively): 9-29- 10-1-2020-R-11:59pm on canvas.

PROJECT-2: Find an efficient algorithm (e.g., branch and bound, dynamic programming, etc., your choice) for TSP and compare its complexity against naïve DFS. You may use downloaded code, as long as you (1) acknowledge source, (2) make some modification and note where you modified, and (3) understand and describe both algorithm and code.

Increase your input set of graphs to minimum 30 (including the input graphs from the project-1 for each of the group member): minimum 15 for positive (HC exists) and 15 for negative. Report average time-complexities for each algorithm, Naïve DFS and the smart one. No need to show any “debugging” example run this time. Whatever smart algorithm you use discuss about it.

Minimum-spanning tree may be used as the h-value within A* search, that is complete.

Local searches like Genetic Algorithm or Simulated Annealing will be much faster, but may not find HC even when it exists or the shortest HC. Feel free to use them, feel free to download code (see above condition), and to use downloaded random graph generator, just enjoy the assignment! Guarantee of optimality of TSP is not required, however, for the next phase of the project, you want to detect correctly if any HC exists (soundness of algorithm).

Suggestion on random graph generator (if you do not find one online): Assign random nodes in the matrix and then, randomly turn on each matrix element to 0/1 with probability p, say 0.5. Better would be to create paths between nodes randomly, if you can think of a way.

A suggested “improved” DFS algorithm: Find next closest node (you have x-y coordinates) and run A* search to find shortest path to that node.

[Group of 2 students each] Due: October-28-W [40]

Submission (tentatively): A report discussing both Naïve DFS and smart algorithms, random graph generator, results including sample runs and time complexity of algorithms (excluding graph generators), your experience, etc. No code needed at this stage.

PROJECT-3: Use CNN (preferably in Tensorflow) to detect Hamiltonian Circuit solution. Input layer: a graph, Target output layer: Yes/No (HC). You will need to create thousands of training graphs with known labels Yes/No. At least 500 yes, 500 no, for training. At least 50 yes, 50 no, for testing.

Submission on Canvas: A report discussing (1) your graph generation (or, selection, if you generate randomly and use your previous algorithm to select yes/no), (2) deep learning network and parameters, (3) results (accuracy graph against epoch, for both training and test sets), and (4) CNN code (Tensorflow). Jupyter IDE is typically used by most data scientists.

[Same group as for Project 2]

Due: 11/29 Immediately after Thanksgiving break. [20]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download