KIIS 2008: Written assignments

The assignments should go in depth with a topic considered in the course, or perhaps another topic in the range of "Artificial intelligence and intelligent systems". Each student should select a topic and task within that topic, and agree with the teachers about this. It is strongly recommended to develop a (small!) implementation as the central theme in the assignment; some topics are suggested below.

The report is expected to explain the problem that you approach, give a brief introduction to the methods and technologies that you have used, and describe you application and results.

It is allowed for students to work in smaller groups on the assigment, but each student must give in his own report, written entirely by himself; however, program text may be shared. In case of such a collaboration, the report must state how this was made and possibly which parts of the program text that are shared.

If time permits, we will arrange student presentations of "work in progress", but the reports will not be commented by the teacher before the exam.

Proposals

• Abduction with Prolog and CHR: See the programming project concerning an extension of the planning example, p. 80. of the course note Logic programming as a framework ...
• Hidden Markov Models in PRISM:
  1) Consider the exercise in section 7 of of the course note Logical-Statistical models and parameter learning in the PRISM system. You may solve the questions stated, and consider if the method sketched can be used as a spell checker; describe how you can use a trained model for checking whether a word looks as a "reasonable" spelling. (NB: Modern spell checkers use a dictionary, so the example is a bit artificial).
  2) In analogy with the above, write a HMM describing the order words occurring in a text and see how well it performs for generating ("funny") text and for checking whether a given sentence is "reasonable". Notice that this is not trivial, since there are many different word in a text, so you may need to make some simplifying assumptions and modifications to the model and training texts.
  3) Find another kind of sequential data that seem relevant for an HMM and implement this. Consider which sort of problems the trained HMM may solve for you.
• Natural language analysis with DCG+CHR: The paper referenced below describes how use case text (in the sense of OOA/OOP) is converted into UML diagrams by means of DCG and CHR. No full program text is available, so the task is the background of the article, to put together a small application which converts the sort of texts considered into a knowledge base (of CHR constraints; drop the step into UML!). If you can identify another application where a similar, restricted language is relevant, it may be more interesting to develop a new grammar for this.
  H. Christiansen, C.T. Have, K. Tveitane. From use cases to UML class diagrams using logic grammars and constraints. G. Angelova, K. Bontcheva, R. Mitkov, N. Nicolov, N. Nikolov (eds.): International Conference: Recent Advances in Natural Language Processing: Proceedings Proc. RANLP 2007, Recent Advances in Natural Language Processing. Shoumen, Bulgaria: INCOMA Ltd., pp. 128-132 (2007). Available here.
• Natural language analysis with HYPROLOG:
HYPROLOG is a system based on Prolog+CHR which implements abduction and a similar mechanism called assumptions; notice that it also understands the DCG syntax. Read about these assumptions and write an implementation of a simplistic language using the facilities of this system.
• Language analysis with DCG: Write a syntax checker for a subset of HTML or XML using DCG. When it works try, to extend your solution to do something sensible in case of forgotten end tags (e.g., continue parsing the rest, or even suggesting which tag is missing).
• Probabilistic abduction:
The paper referenced below describes how probabilistic abduction can be implemented in CHR. It works in a different way than the approach to abduction with CHR we have seen in the course, in that CHR constraints are used to hold pending processes, each trying to find an explanation. This describes also a so-called best-first search approach, by means of which we can find the explanation of highest probability without having to compute all explanations. Find a good test case where probabilistic abduction is relevant and implement it as described.
H. Christiansen, Implementing Probabilistic Abductive Logic Programming with Constraint Handling Rules, 35 pp., Recent advanced in Constraint Handling Rules. T. Frühwirth, T. Schrijvers (eds.). Volume of Springer Lecture Notes of Computer Science; to appear 2008. Available here.
• Neural networks: Identify a classification problem for which a neural network seems relevant. Develop an implementation of a neural net (using whatever tool you may find available), train it and test how well it performs. You may possible compare different networks for the same problem. (It is not recommended to program everything from scratch, but you should find a suitable program package or high-level neural network tool).
• Genetic algorithms: Identify an optimization problem for which it may be worthwhile trying a genetic algorithm. Implement this, adjust the different parameters and see if you can have interesting solutions produced. NB: If you decide to implement everything from scratch, do not spend time on a sophisticated user interface!!. If you can find a suitable program package that can do most of the work for you, that may be the best (you teacher is not aware of any easy-to-use packages or systems)
• You own proposal: ...