AI.VersionSpaces

Documentation

data BSR a i o

Representation of a traditional version space, as described by Hirsh: Hirsh, H.: 1991, 'Theoretical Underpinnings of Version Spaces'. In: Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. pp. 665670.

Constructors

EmptyBSR

BSR

Fields

storage :: a

narrow :: BSR a i o -> i -> o -> BSR a i o

hypos :: BSR a i o -> [i -> o]

showBSR :: BSR a i o -> String

Renders a BSR to a string to show whether the BSR is empty or not. Additional details place undesirable restrictions on the state storage.

union :: VersionSpace a b -> VersionSpace a b -> VersionSpace a b

Union two versionspaces, generating a third.

join :: (Eq b, Eq d) => VersionSpace a b -> VersionSpace c d -> VersionSpace (a, c) (b, d)

Join two versionspaces, generating a third.

tr :: Eq b => (i -> a) -> (o -> b) -> (b -> o) -> VersionSpace a b -> VersionSpace i o

Transform a version space to mutate the input and/or output types. Transforms require that three functions be specified:

i -> a

Transform the input of the resulting version space to the input of the initial versionspace.

o -> b

Transform the output of the initial versionspace into the output of the resulting versionspace.

b -> o

Transform the output of the resulting versionspace into the output of the initial versionspace. This is necessary to support training: the training examples will be in terms of the resulting versionspace, so the output must be transformed back into the terms of the initial versionspace.

data VersionSpace i o where

Version Space algebraic operators:

Constructors

Empty :: VersionSpace i o

VS :: BSR a i o -> VersionSpace i o

Join :: (Eq d, Eq b) => VersionSpace a b -> VersionSpace c d -> VersionSpace (a, c) (b, d)

Union :: VersionSpace a b -> VersionSpace a b -> VersionSpace a b

Tr :: Eq b => (i -> a) -> (o -> b) -> (b -> o) -> VersionSpace a b -> VersionSpace i o

showVS :: VersionSpace i o -> String

Serializes a versionspace to a human-readable string, for certain values of human.

train :: Eq o => VersionSpace i o -> i -> o -> VersionSpace i o

Train a version space, reducing the set of valid hypotheses. We handle the Empty VS cases prior to the corresponding non-empty cases because the Empties are simplifying cases, so logic can be short-circuited by collapsing parts of the hierarchy before recursing.

hypotheses :: VersionSpace i o -> [i -> o]

Retrieve the valid hypotheses for a version space.

runVS :: VersionSpace a b -> a -> [b]

Runs all valid hypotheses from the version space on the specified input.