A programming paradigm for machine learning with a case study of Bayesian networks

Lloyd Allison, Faculty of I.T., Monash University
ACSC2006, January 2006

Inductive programming (IP) is about components for machine learning -- studying, generalizing, defining, building, transforming and using them.

It employs Haskell and MML.

Here IP is illustrated by a case study of a learner for mixed Bayesian networks[*] (discrete and continuous variables) which is applied to a lost-person data-set.

Online at: www.csse.monash.edu.au/~lloyd/Seminars/2006-ACSC/index.shtml 1/2006.

generalized mixed Bayesian network for knowledge discovery over discrete and continuous variables in data mining of search and rescue data

Lost person application of IP case study of BNs

Some variable types...

Age --continuous

Gender --unordered discrete (Bounded, Enum)

Topography = Mountains | Piedmont | Tidewater
--i.e. Bounded, Enum and Ord.

Network+data 9,700 nits v. null+data 10,400 nits approx. (parameterized).

Variables

@0:  Tipe       = Alzheimers | Child |...
@1:  Age
@2:  Race       = ...
@3:  Gender     = ...
@4:  Topography = as above
@5:  Urban      = ...
@6:  HrsNt
@7:  DistIPP
@8:  TrackOffset
@9:  Health     = Well | Hurt | Dead --after!
@10: Outcome    = Find | Suspended | Invalid
@11: FindRes    = Ground | Air |...| Dog
@12: FindLoc    = Brush | Woods |...
@13: HrsFind
@14: HrsTot

Components used in IP case study of Bayes-nets

Bayesian network

DAG, node_bn, parents -> child

Classification tree

leaf node_ct

split node_ct

Model missing data,
ModelMaybe

Split missing data

Model discrete,
e.g. multinomial

Model continuous,
e.g. Normal

Split
Bounded Enum

Split
Ord

other...

^
|
|
|
|
h |
|
|
|
|
v

Components must be autonomous or must cooperate, e.g. to defeat over- (& under-) fitting, even as "height", h, increases.

MML

For data D and model M,

Bayes:	pr(M&D) = pr(M).pr(D\|M) = pr(D).pr(M\|D)
Shannon:	msgLen(E) = -log(pr(E))
Wallace:	msgLen(M&D) = msgLen(M)+msgLen(D\|M) = msgLen(D)+msgLen(M\|D)

Receiver	M; D\|M	Transmitter
	<------------------

(NB. MML is not in general identical to MAP, e.g. continuous params.)

for completeness, the BN estimator (learner)

estNetwork perm estMV dataSet =
 let
   n = (length . selAll) (estMV [])
   search _  []     = []  --done
   search ps (c:cs) =
    --parents ps, children c:cs
    let
      opFlag  = ints2flags [c] n  --child
      ipFlags = ints2flags ps  n  --parents
      cTree = estCTree            --see JFP 2005
                (estAndSelect estMV opFlag)
                (splitSelect ipFlags)
                dataSet dataSet
     in cTree : (search (c:ps) cs)

   trees  = search [] perm       --network
   msgLen = sum (map msg1 trees) --total msg1
   nlP datum = sum (map(\t -> condNlPr t datum datum) trees)
 in
   MnlPr msgLen nlP              --return a Model
         (\() -> "Net:"++(show trees))

Some new IP machinery for BNs, class Project

  class Project t where      --as in a Projection type
    select :: [Bool] -> t -> t
    ...

Lets us select certain variables (columns), e.g.

  data ModelMV dataSpace = MnlPrMV... --new Model type
  ...

  instance Model ModelMV where ...

  instance Project (ModelMV dataSpace) where ...

And also

  class Splits2 ds where
    splitSelect :: [Bool]->[ds]->[Splitter ds]

Model missing data, Maybe t

  modelMaybe m1 m2 =
    let
      negLogPr (Just x) = nlPr m1 True + nlPr m2 x
      negLogPr Nothing  = nlPr m1 False
    in
      MnlPr (msg1 m1 + msg1 m2) negLogPr
            ...'show' method omitted

-- a useful inductive programming (IP) operator, applicable to any model m2, ...

. . . and estimators

  estModelMaybe estModel dataSet =
    let
      present (Just _) = True
      present Nothing  = False
      m1 = uniformModelOfBool          --[*]
      m2 = estModel (map (\(Just x)->x)
                    (filter present dataSet))
    in modelMaybe m1 m

(This is not the same as coding missing as a 'special value'.)

[*] Or alternatively...

  m1 = estMultiState (map present dataSet)

or even...

  m1 = commonKnowledge

¿Do you want to model 'missingness', or not?

Defining the data-space


data Tipe = Alzheimers| Child| Despondent| ...

type Age  = Double
 ...

data Topography = Mountains| Piedmont| Tidewater
        deriving (Ord, Enum, Bounded,...)
 ...


type MissingPerson = (Maybe Tipe, Maybe Age, ... )

--standard Haskell-98.

Modelling the variables


e0 = estModelMaybe estMultiState            --Tipe

e1 = estModelMaybe(estNormal 0 90 1 70 0.5) --Age

 ... etc.

estMissingPerson = estVariate15 e0 e1 e2 e3 e4 e5 e6
                      e7 e8 e9 e10 e11 e12 e13 e14

Partitioning the data-space, class Splits

 ...

instance Splits Topography where splits = splitsBE

                    --or alternatively  = splitsOrd
 ... etc.

splitsBE --for Bounded Enum types,
splitsOrd --for Ord types

Also implemented 'setSplits' for high-arity Bounded Enum types.

Running the application


dataSet = read (readFile theDataFile)
          :: [MissingPerson]              --input

nw = estNetwork [1,2,3,0,4,5,6,7]
                estMissingPerson dataSet  --model

nullModel = estMissingPerson dataSet      --null

Conclusion

Code for new operators and models is general, small and quick to write.
Have shown multiple [layers of components] working together.