46838-s99 Machine Learning for Computational Finance Assignment 1

Due March 15, at the beginning of class

Describe a problem in Finance where you think machine learning techniques can be used to supplement or substitute for expert knowledge.
- (i) Define
  - (a) the class of tasks T your learning program should perform
  - (b) a performance measure P
  - (c) the experience E your learner can use
- (ii) Describe 2 different target functions your algorithm could learn. (Recall from class the Checkers program which could learn either a mapping from board positions to moves, or board positions to scores) Discuss advantages and disadvantages of these two possible functions.

The PayDividend learning task has the following properties:

Instances X: each described by the attributes
- Price (with possible values Up, Down and Same)
- Earnings (with possible values High and Low)
- Sector (with possible values Manufacturing and Service)
- Market (with possible values Bull and Bear)
- Exchange (with possible values NYSE and Nasdaq)
- Outlook (with possible values Strong and Weak)
Hypotheses H: Each hypothesis is described by a conjunction of constraints on the attributes Price Earnings Sector Market Exchange Outlook. The constraints may be ? (any value is acceptable) 0 (no value is acceptable), or a specific value.
Target Concept c: PayDividend: X -> {0,1}
Training Examples D: Positive and negative examples of the target function (see table below).

Example	Price	Earnings	Sector	Market	Exchange	Outlook	Pay Dividend
1	Up	High	Manufacturing	Bull	NYSE	Strong	Yes
2	Up	High	Service	Bull	NYSE	Strong	Yes
3	Down	Low	Service	Bull	NYSE	Weak	No
4	Up	High	Service	Bull	Nasdaq	Weak	Yes

Explain why the size of the hypothesis space is the PayDividend learning task is 973. How would the number of possible instances and possible hypotheses increase with the addition of a new attribute which can take on 3 different values. More generally, how does the number of possible instances and hypotheses grow with he addition of a new attribute A that takes on k possible values?

Consider the PayDividend learning task discussed in class and the associated hypothesis space H. Define a new hypothesis space H' that consists of all _pairwise_ disjunctions of the hypotheses in H. For example, a typical hypothesis in H' is:
```
(?, Low, Srv., ?, ?, ?)  V  (Up, ?, Srv., ?, ?, Strong)
```
- (i) How big is the instance space (i.e., how many instances are there?)
- (ii) How big is the hypothesis space H'? (i.e. how many hypotheses are there in H'? Give as tight an upper bound as you can).
- (iii) Is H fully contained within H' ? Prove your answer.
Give the sequence of S and G boundary sets computed by the CANDIDATE-ELIMINATION algorithm if it is given the sequence of examples given in the table in question 2 in reverse order. Although the final version space will be the same regardless of the sequence of examples (why?), the sets S and G computed at intermediate stages will, of course, depend on this sequence. Can you come up with ideas for ordering the training examples to minimize the sum of the sizes of these intermediate S and G sets used for the H used in the PayDividend example?
Problem 2.4 in the book
Problem 2.7 in the book
Problem 2.8 in the book

Rosie Jones

Last modified: Sat Mar 13 04:48:36 EST 1999