Database Systems



Artificial Intelligence

CSE 5290/4301, Spring 2020

Instructor: Debasis Mitra, Ph.D.

Office: Harris 325 E-mail: dmitra ‘at’ cs.fit. edu

Class Home Page:

Office Hours: MT 2-4 pm (or by appointment)

Grading plan:

Graduate stds: Quizzes (9, worst dropped): 15%, Coding exercise: 5%, Exams (other than 3-pointers) 40%, Project: 40%

Undergraduate stds: Quizzes (~9, worst dropped): 20%, Coding exercises: 30%, Exams (other than 3-pointers) 50%

|Class |

|TR 8:00-9:15pm |

| |

|Olin Eng 137 |

| |

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:

Detailed activities in Fall 2019 mapped on to the dates in Spring 2020, for now.

This table will act as our continuously developing plan for this semester: ~ 28 meetings

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

Exams 3, Std presentations 4

| |Activities |Comments |

|Jan 14 T |AI an Introduction, and get-to-know quiz |My thoughts on Grad projects for now |

| | | |

|Jan 16 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) | |

| | | |

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

| | | |

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

|-- |MLK, Jr. memorial holiday Jan20 | |

|Jan 21 T |AI SEARCH (From my slides): 8-puzzle: |Quiz-1 due |

| | | |

| |BFS- Uniform Cost; DFS-Depth Limited (up to sl 22) |Coding exc-1 announced. Due: Feb 11 in class |

| |Iterative-deepening | |

| | | |

| |NP-completeness (Algo-Complexity slides 6-9:NP; 10-14: Problem | |

| |class; 15-22: PvsNP; 32-33: CLK-thm; | |

| |41-46: NP-complete; 63-67: What-to-do-with-NPcomplete) | |

|Jan 23 R |In-class quiz on BFS, DFS |Graduate projects |

| | |Described below this table |

| |Heuristic Search A*, IDA* | |

| |MySlides 15-35 | |

| |Text Slide Ch4a | |

|Jan 28 T |Game (Adversarial) search MySlides: 1-8 | |

| |Local search from Text-slides Ch4b: Local search, Hill-climbing,| |

| |Simulated Annealing, Local beam search, Genetic Algorithm, | |

| |Gradient search, | |

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

|Jan 30 R |My SearchSlides continued (36-48) |Grad students stay back a few minutes AGAIN |

| |Take home quiz: Yes, if Bucharest->Timisoara A*-shortest path is |after lecture today, I would like to know |

| |not feasible to compute with given data, then compute the |what have you gathered so far |

| |reverse, Timisoara to Bucharest. | |

| | | |

| |Search - exercise problems? | |

| | | |

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

| |Backtracking, Forward Checking (TextSlides) | |

|Feb 4 T |Ch5 text slides |Take home quiz due |

|Feb 6 R |Quiz on search (15 min) |Grad Project written proposal due in class, |

| | |hard copy 2-3 pages (any format is ok) |

| |Constraint Reasoning | |

| |SPATIO-TEMPORAL CONSTRAINT REASONING from my slides. | |

| |A relevant web page: | |

| | | |

|Feb 11 T |Note: Input graph vs search tree vs control-flow-on-search-tree |Coding assignment-1 due |

| |vs (shortest) path | |

| | |Grad Project written proposal feedback |

| |MySlides,; AC-3, SAT, and SAT-DPLL |My talk on Maze to Stanford on R-4pm on skype |

| |SAT in Algo-complexity slides: 34-8 | |

| | | |

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

| |32, 36-7, 44 | |

| | | |

| |AUTOMATED REASONING (ch 7): Basics & Syntax | |

|Feb 13 R |AUTOMATED REASONING (ch 7): Syntax-Semantics-Model, | |

| |Satisfaction-Entailment-Inference procedure-Validity (up to | |

| |TextSlide 41, ch-7) | |

| |Assigned a take-home | |

|Feb 18 T |Grad Project status presentation (1/2 hr) |Take-home quiz due |

| | |More quiz assigned |

| | | |

| | |Grad Project status presentation, |

| | |each group 5-7 mi, make sure that your media |

| | |works in the class |

|Feb 20 R |Adversarial search: discussion |A sentence not in Horn form: |

| | |P is not true, ~P=>T |

| |AUTOMATED REASONING – continued: | |

| |Propositional Knowledge Base, Model checking algorithm, | |

| |Forward chaining algo, Backward chaining algo (sl#40-66) | |

| | | |

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

|Feb 25 T |Pilot online test on Canvas over Search (5 min) | |

| | | |

| |AUTOMATED REASONING: Revisited PropLogic algorithms | |

| |First Order Logic-Motivation; | |

|Feb 27 R |AUTOMATED REASONING (possible lecture on Skype): | |

| |Model-Interpretation-Quantifiers-Inferencing | |

| |Completeness-Herbrand Universe, | |

|Mar 3 T |Quiz on Search and Constraint reasoning (with online component) |Grad Project First Progress Report due: |

| |15 min |updated proposal (quite possible that |

| | |your work has changed from your proposal – mention that), |

| |Revise, Frame problem-etc., (sl 17-28) |including work that has been done so far |

| | |and your plan for future |

|March 5, R |Occur check: Substitution like x/S(x) not allowed in most logic |Undergrad Coding Exc-2 due April 6, Monday, 11:59pm |

| |programming languages, Unification-algo syntactically checks for |Description is below this table |

| |that and fails in that case. Occur check makes it unsouond! |Form 2 persons’ groups, except one group has to be single |

| |Otherwise, x/S(S…(x)…) infinite looping – source of | |

| |semi-decidability of FOL | |

| | | |

| |Unification, Forward Chaining, Backward Chaining, Resolution | |

| |strategies | |

| | | |

| |Homework: Use slides 25-27 of Inferencing with FOL. Show the | |

| |steps of the proof for query Criminal(West). The slides animates | |

| |the proof tree for your understanding. You write the steps | |

| |explicitly as a Forward Chaining algorithm will work. Due in hard| |

| |copy, next class. | |

| | | |

| |Grad Project status discussion (cancelled presentation) & reports| |

| |(ungraded) returned! | |

| |Undergraduate student attendance required (unless pre-excused) | |

|Mar 9-20 |-- Spring break -- | |

| |Grad Project status presentation (15 min each group, to be | |

| |scheduled online, possibly March 26) | |

| |Revised report (soft copy, via the Canvas) due, including sample | |

| |output from your implementations, on the same day! Let us extend | |

| |this through Wednesday 5pm EDT. | |

|Mar 19, R |Lectures will be most likely on Zoom during the class hours; link| |

| |will be posted on Canvas; zoom is now linked from Canvas; maybe | |

| |limited to 40 min per session; in that case we will go with | |

| |multiple sessions; | |

| |I will do a trial run at 5pm this day 3-19-R for a few minutes. | |

| |Join the class (optional) if you can. | |

|Mar 24 T |Online lecture: will post zoom link on Canvas announcement just |Homework (on slides 25-27 of Inferencing with |

| |before the class. You must join “with computer audio,” and then |FOL) – The Forward-Chaining algo is |

| |mute yourself. |explained with animation on slides. |

| |There is a hand-raising feature on zoom. Also, you should have |You need to write down the deductive proof |

| |the chat open and use it if necessary. For asking question, you |step by step. |

| |may unmute yourself. |due: upload photocopy on the Canvas. |

| |I will share my screen, and would like 2-3 folks to be on video |This is also a new trial! Hopefully, all of you |

| |at a time for a better feel. Others should turn off video to |will submit. |

| |reduce bandwidth. | |

| | |I hope Undergrad students paired up |

| |REASONING WITH UNCERTAINTY: Ch 13: Motivation |for the Coding Assignment-2. |

| |Probability-Joint-Inference-Conditional-Baye’s rule; |A discussion forum is created on Canvas |

| | |for this – respond there. |

| |Zoom session continues: |I will check on the pair-names in class today. |

| |Three Graduate Project status presentations (8 min each group, | |

| |one of the group member will take over the screen sharing on | |

| |zoom, practice beforehand so that you may express succinctly your| |

| |results within time). | |

| |Organ Recognition, Indus Valley | |

|Mar 26 R |Test on Automated-Reasoning/Logic online (15 min. after you join |Provide me feedback on the online delivery mechanism. |

| |starting at 8+ pm, 10 questions) |I will take attendance next class onwards, |

| | |except for those who are excused beforehand. |

| |(Lecture for 20 min) |The class is recorded and linked from the |

| |Probabilistic reasoning contd. |class page. |

| |Ch 13: Sl 10-26 | |

| | |Feel free to use Canvas mail to communicate with me, |

| |Two Graduate Project status presentations (8 min each, practice |I may be on Canvas Chat MT 1:30-3:30p for OH. |

| |beforehand to express succinctly your results within time). | |

| |Time-series topology, Maze-path decision problem | |

|Mar 31 T |Probabilistic reasoning contd. | |

| |In-class quiz | |

| | | |

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

| | | |

| |Bayesian network Ch 14 starts | |

|Apr 2 R |Bayesian network Ch 14 contd. |Undergraduate coding assignment |

| |Possible in-class quiz. |(below) modified |

| | | |

| |If you do not see my chat box open remind me. |Graduate intermediate |

| | |Presentation-Slides or Report due by 5 pm April 2 |

|Apr 7 T |Undergrad Coding-2 status discussion | |

| | | |

| |MACHINE LEARNING: Decision tree, basics | |

|Apr 9 R |Online test on Probabilistic reasoning (20 minutes, 10 MCQ |Try to join with video on, |

| |questions, Ch 13, 14). You may need a blank paper handy for rough|zoom bandwidth seems not a problem |

| |work. | |

| | | |

| |MACHINE LEARNING: Decision tree, contd. | |

| | | |

| |Class will be recorded and shared as no one objected. | |

| |Please remind me to turn on recording ( | |

|Apr 14 T |Ch 18.6: MACHINE LEARNING continued: MDL, PAC, |Clarifications on Coding-2 (UG) being added below. |

| |18.6.1-2. Regression: Linear, | |

| |Multi-variate regression, linear |I am planning to offer a Summer course |

| |In-class quiz |“Computational virology: A machine learning perspective” |

| | |to address some of the genomics related questions with |

| |Graduate Project status presentation: Motion-type identification |viruses. Basics of genomics will be addressed. |

| | | |

| |Take Home on Probabilistic Reasoning (to publish during | |

| |class-time today), due 4/16/R/7:45pm | |

|Apr 16 R |18.6.3-4. Classifiers, Logistic regression, Perceptron 18.7.1-4. | UG Coding Exc-2 due Monday-4/20-11:59pm |

| |Artificial-neural Networks [Start from MySlide#24, exclude |(not 4/16/R) |

| |slides 39-43] | |

| | | |

|Apr 21 T |Artificial-neural Networks [Start from MySlide#24, exclude | |

| |slides 39-43] | |

| |18.7.1-4. Artificial-neural Networks | |

| |Ch 18.8: non-parametric, kNN and variations | |

|Apr 23 R |Ch 18.8: non-parametric: LSH (start - slide 51), | |

| |kernel-regression and 18.9-10 SVM | |

| | | |

| | | |

| |DT tutorial continues | |

|Apr 28 T |Clustering basics: K-means, from |Graduate Project Final report due Monday 27th by 9pm |

| | |on Canvas by e-mail (i) A report between 4-10 pages, |

| |K-median, Slide 64 hierarchical, density-based |including an abstract and references in NIPS |

| | |conference format |

| |Canvas problem: could not create Machine Learning (ML) exam, |(), you need not use LaTex, but just follow the formatting style., |

| |postponed for another class. |(ii) Your source code including |

| |A take-home for today, due 4/30/R/8pm |instructions on how to run and any dependencies and |

| | |library details, |

| |Graduate groups’ demo starts: Chris on Time series clustering by |and (iii) data files with metadata information (to understand |

| |persistence homology |data). |

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

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

|Apr 30 R |Please do the instructor review. |DISCLAIMER: CANVAS HAS NO FORMULA NOW. |

| | |I USE MY OWN SPREADSHEET. |

| |Test on ML, outside class hours: |YOU WILL SEE YOUR COMPREHENSIVE GRADE THERE IN A SEPARATE COLUMN IN CANVAS AND LETTER GRADE IN PAWS. |

| |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. | |

| |An additional Table-1 will be provided as a supplement to answer | |

| |some of the questions. (If I forget please e-mail me.) | |

| | | |

| |AI and Ethics (my slides are included in syllabus/tests) | |

| | | |

| |Exam: Predicate logic, Probabilistic reasoning, Machine Learning,| |

| |Ethics | |

| | | |

| |Graduate groups’ demo continues | |

|5/8/2020/R |We will continue with Grad demos during the exam period on |All Graduate project reports look very good! |

| |Thursday 8:30pm-. Mandatory for undergraduates to attend. |However, I have some minor but strong suggestions. |

| | |They are below in a table. |

| |The exam will be for 30 minutes from your start time. Only online|I will expect them taken care of by |

| |test, no take-home. You may take the test any time between |the coming weekend. |

| |9am-8pm on 5/8/R (like the MLtest was). | |

| |You will need 3 Tables from the class page, I suggest you |Grading weights at the top of the table. |

| |download them before starting the exam. Having additional rough | |

| |papers to work on may help. Feel free to use calculator but that | |

| |may not be needed. Unfortunately, test answers will not be | |

| |available soon, maybe next week! Good luck! | |

| |Peace, health, and productivity! | |

| | | |

| |Exam period: Thursday, May 7, 8:30-10:30 p.m. | |

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

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

|8 p.m. Class |Tuesday and Thursday |Exam: Thursday, May 7, 8:30-10:30 p.m. |

GRADUATE PROJECTS

(Project partners may be individually graded if necessary)

| |Suggestion |Done? |

|Update report |Motion detection: Sample images of input as Fig. Graphic description of the network | |

| |architecture. | |

|Extra data |ToMato: IEEE and/or Stanford group presentation? | |

|Possibly a 10 min|Segmentation output masks will be needed corresponding to each input image, for my | |

|presentation |archival & the paper. | |

|Update report |Time-series: More needed on your slice-by-slice algorithm: formal algorithm as a figure, | |

| |and | |

| |explanation with a running example. | |

| |Add info on computation speed. | |

| |Add country-to-country comparison as an appendix. | |

| |Stanford group presentation? ArXiv submission? | |

|Update report |IVC: Provide numbers on used real data, then augmented data. Exact transformation math | |

| |and the augmentation process used: | |

| |rotation steps, translation steps and range, etc. | |

| |I presume as you transformed data you also transformed the bounding box by the same | |

| |transformation. Explain it. | |

|Update report |Maze: More on evaluation process needed: test set numbers by each case? | |

| |Four sample-mazes as figures: (with & without path) X (successful, not) | |

| |Table-2: compile or training time? | |

| |will you update last paper and submit to any AI journal? | |

Maze-decision problem: Our work so far was on the existence of path between coordinates (0,0) and (n-1,n-1) corners in an n x n maze. We would like to do the same between (0,0) and (x,y) for variable x,y Middle layers -> eight numbers.

What I see happening is a disconnect. You apparently do have a machine learning model that

somehow detects the text box or boxes. I do not understand how? One way would be to draw

your neural network's architecture and explain what is going on. If you do really have a solution

to the problem of "text box recognition" that is great! I, and you, need to understand what is

going on.

I asked you to submit a report clarifying this.

Deep learning of activities-recognition: Any available activities database available online with labels that you would like to work with? (Yes, I found Microsoft has a kinnect image database; NIST-IARPA-challenge (ActEV) database? Any other?)

How will you augment data for training? Which computer will you work on? May need large memory, fast processor and GPU?

Mathematical model or category-classification? I prefer category classification (car entering/existing parking lot, backhand/forehand stroke, etc.)

Tim Porath (and Sarah Arend?)

After 1st presentation

Did you converge on a data set and validation plan?

Training code? Input layer format matching with your data?

Clustering time-series based on topology: Persistence-based clustering of time-series. Cancer image from contrast-enhanced ultrasound (CEUS) data. (No knowledge of cancer or ultrasound is needed)

(1) Learn about time-series. There are plenty of time-series databases, the most known one is the Univ CA-Riverside (UCR) database.



Even though, you will possibly work with our medical data.

(2) How to compare two time-series, or what are the types of “distance” between two time-series?

(3) Learn Topological data analysis (TDA) and “persistence homology” (PH).

(4) Apply PH to cluster time-series based on their shapes.

(5) If possible, compare against another clustering technique, e.g., K-means clustering.

Chris Woodle (and Valerie Kobzarenko)

After 1st presentation

Is the code for time-series to PD ready? Debug with hand generated cases.

PD to PD comparison (after removing diagonal-hugging points) is point-cloud comparison. Which software to use? Algorithm? Sum-of-min?

Topology based clustering of organ voxels in a whole-body CT image (2D or 3D?): Learn TDA and ToMato software, use it on large whole-body image. Try to automatically recognize organs, based on “persistence homology” (PH, encodes shape).

(1) Download ImageJ first, to visualize data.

(2) Learn PH as it represents shape of an object.

(3) Learn density-based clustering, ToMato software uses that.

(4) ToMato has two implementations available on the Internet: Python-based, works only on 2D (can we modify source to make it work on 3D?); and C++ that works on nD but very difficult to install for library mismatch (not maintained). Check which one you would like to work with. Two students last semester made the C++ version work, we can seek help from them if needed.

(5) Try to find multi-organ 3D medical image online, any animal or any medical imaging modality will do. For that matter, any image with isolated (should have complicated shape) clusters will do, as long as you can map it to a shape-based-object-recognition problem. After some success from you, we will release human anatomy data to you.

Mircia Silaghi and Ran Bi

After 1st presentation

Did you obtain organ/ROI segmentation? Wise tool is another candidate.

PD for whole-body image? Any pattern for each organ – look over PDs for multiple images.

Template PD point cloud should let you recognize organs. Needs PD -> image mapping.

After 2nd presentation & Intermediate report

Figures should have self-content captions with as much explanations as possible.

Semantically organize them under same figure number, Fig 1a, b, ...

Refer the Fig number within the text.

I am not very clear on your Figure p8 if it removes kidney. Looks more like merger of two organs, upper kidney + liver or spleen

Is PD translation invariant? Rotation and scale?

Future idea (Not in your project): Can we have a GUI that would visualize the clustering

on left panel and the PD used on the right. Moreover, the parameters can be changed on

sliding scales, d value, the diagonal for cutoff, others. One mouse overs a PD point

and it highlights the cluster on left, and one mouse-overs on a cluster and it shows the PD on the left.

Discovering approximate symmetry group, and symmetry axes (3D protein) of objects with deep learning:

CODING EXERCISES

1. All students, individual assignment: Implement or use library for three data structures: queue, stack, and priority queue with integers. Note, queue and stack ignores any number or weight in graph. Use these data structures to develop three graph-search algorithms over input: a graph, a source node, and a goal node. Three data structures from the above should be pluggable in your code. There will be three search algorithms with three data structures. Use your search algorithms to input the Romanian road-network map from the textbook (Fig. 3.2, p68), the start node as Bucharest and the goal node as Timisoara. Children from the root Bucharest to be expanded are in this order: Urziceni, Fagaras, Giurgiu, and then Pitesti. Note, the priority queue may rearrange the node orders, which is ok. The priority queue will use the shortest distances from Bucharest to the nodes in it using the road-distances on the map (NOT the straight-line-distances) and hence, should find a shortest path. Your algorithm should print the nodes as they are traversed by your algorithm.

Submission in hard copy: a) Source codes; b) Full search tree by running each of your search algorithms. Due: Feb 11 in class [20 pts]

2. Only Undergraduate Students assignment 2 (in group of two students): Code the min-max algorithm for the adversarial game search with and without alpha-beta pruning, Input: NxN tic-tac-toe with varying N between 0 through as much as you can handle. For N>5, implement fixed ply (depth of search) at 5 3. You will need a board evaluation function at the leaf node of the search tree. Let the heuristic value be normalized to [-1, 1].

Output: 1) Play yourself (human-computer) against it – print sample game for N=7. [All real play outputs are to be with alpha-beta pruning.]

2) Play against some other group (recorded jointly with the other group for the same game), with N=10.

2) Let your code play against itself (two copies of your code, computer-computer), for N=9. Same output.

3) Record CPU times for play-against-itself N=3, 5, 9

Submission on the Canvas: source code, print-outs, and a report. [30 pts]

Due: April 16-Thursday-11:59pm.

ASK FOR ANY CLARIFICATION.

1) Many are finding that the complexity is too high for N>3. In that case use ply=3, i.e., evaluate board after 3 recursive calls. You should be able to 3^2 depth that way (theoretically :)

2) There is a rule-of-game issue. Say for N=4, there are 4 ways to win/loose on horizontal rows, similar, for columns. However, there should be only 2 ways to win/loose with diagonals, for any N.

3) Don’t forget to implement the alpha-beta pruning. That saves a lot of computational time! I modified the assignment above to exclude “without alpha-beta pruning” part.

UG Groups:

Emran - Siyu Fu

Erika - Rishob

Thanart – Stian

Hunter – Jose

Nic – Taylor

Andrew

Alternative: Research on quantum neural nets.

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

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

Google Online Preview   Download