packages feed

HLearn-algebra (empty) → 0.0.1

raw patch · 6 files changed

+359/−0 lines, 6 filesdep +ConstraintKindsdep +basedep +binarysetup-changed

Dependencies added: ConstraintKinds, base, binary, deepseq, ghc-prim, hashable, parallel, semigroups, vector

Files

+ HLearn-algebra.cabal view
@@ -0,0 +1,31 @@+Name:                HLearn-algebra+Version:             0.0.1+Synopsis:            Algebraic foundation for the homomorphic learning+Description:         This module contains the algebraic basis for the HLearn library.  It is separated out in it's own library because it contains routines that may be useful to others.  In particular, it contains methods for automatically converting algorithms into online/parallel versions, and its structure is slightly more modular (although much less complete) than other algebra packages.+Category:            Data Mining, Machine Learning+License:             GPL+--License-file:        LICENSE+Author:              Mike izbicki+Maintainer:          mike@izbicki.me+Build-Type:          Simple+Cabal-Version:       >=1.8++Library+    Build-Depends:      +        base                >= 3 && < 5,+        ghc-prim,+        ConstraintKinds     >= 0.0.1,+        +        semigroups          >= 0.8,+        parallel            >= 3.2,+        deepseq             >= 1.3,+        binary              >= 0.5,+        hashable            >= 1.1.2,+        vector              >= 0.9+    hs-source-dirs:     src+    ghc-options:        -rtsopts -auto-all -caf-all -O2 +    Exposed-modules:+        HLearn.Algebra+        HLearn.Algebra.Models+        HLearn.Algebra.Structures+        HLearn.Algebra.Functions
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ src/HLearn/Algebra.hs view
@@ -0,0 +1,12 @@+-- | This is the base module for the HLearn library.  It exports all the functions / data structures needed.++module HLearn.Algebra+    ( module HLearn.Algebra.Models+    , module HLearn.Algebra.Structures+    , module HLearn.Algebra.Functions+    )+    where+          +import HLearn.Algebra.Models+import HLearn.Algebra.Structures+import HLearn.Algebra.Functions
+ src/HLearn/Algebra/Functions.hs view
@@ -0,0 +1,112 @@+{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE UndecidableInstances #-}++-- | This module contains \"low-level higher order functions\" for manipulating algebraic homomorphisms.  You probably want to use the 'HomTrainer' type-class rather than using these functions directly.++module HLearn.Algebra.Functions+    ( +    -- * Parallelism+    parallel+    -- * Manipulating homomorphisms+    , online, offline+    , batch, unbatch+    , semigroup+    -- * Helper functions+    , reduce+    )+    where++import qualified Control.ConstraintKinds as CK+-- import Control.Applicative+import Control.Concurrent+import Control.Parallel.Strategies+-- import Data.Traversable+-- import qualified Data.Foldable as F+import GHC.Exts (Constraint)+import Prelude hiding (filter)+import System.IO.Unsafe++import HLearn.Algebra.Structures++-------------------------------------------------------------------------------+-- higher order functions++-- | Parallelizes any batch trainer to run over multiple processors on a single machine.  The function automatically detects the number of available processors and parallelizes the function accordingly.  This requires the use of unsafePerformIO, however, the result should still be safe.+parallel :: +    ( Semigroup model+    , NFData model+    , CK.Partitionable container+    , CK.PartitionableConstraint container datapoint+    ) => (container datapoint -> model) -- ^ sequential batch trainer+      -> (container datapoint -> model) -- ^ parallel batch trainer+parallel train = \datapoint ->+--     F.foldl' (mappend) mempty $ parMap strat train (CK.partition n datapoint)+    reduce $ parMap strat train (CK.partition n datapoint)+    where+        strat = rdeepseq+        n = unsafePerformIO $ getNumCapabilities++-- | Converts a batch trainer into an online trainer.  The input function should be a semigroup homomorphism.+online :: +    ( Semigroup model+    ) => (datapoint -> model) -- ^ singleton trainer+      -> (model -> datapoint -> model) -- ^ online trainer+online train = \model datapoint -> model <> (train datapoint)++-- | The inverse of 'online'.  Converts an online trainer into a batch trainer.+offline :: +    ( Monoid model+    ) => (model -> datapoint -> model) -- ^ online singleton trainer+      -> (datapoint -> model) -- ^ singleton trainer+offline train = \dp -> train mempty dp++-- | Converts a singleton trainer into a batch trainer, which is also a semigroup homomorphism.+batch ::+    ( Monoid model+    , CK.Functor container+    , CK.FunctorConstraint container model+    , CK.FunctorConstraint container datapoint+    , CK.Foldable container+    , CK.FoldableConstraint container model+    ) => (datapoint -> model) -- ^ singleton trainer+      -> (container datapoint -> model) -- ^ batch trainer+batch train = \dps -> CK.foldl' mappend mempty $ CK.fmap train dps++-- | Inverse of 'unbatch'.  Converts a semigroup homomorphism into a singleton trainer.+unbatch :: +    ([datapoint] -> model) -- ^ batch trainer+    -> (datapoint -> model) -- ^ singleton trainer+unbatch train = \datapoint -> train [datapoint]++-- | Normally we would define our semigroup operation explicitly.  However, it is possible to generate one from an online trainer and a pseudo inverse.+semigroup :: +    (model -> datapoint -> model) -- ^ online trainer+    -> (model -> datapoint) -- ^ pseudo inverse+    -> (model -> model -> model) -- ^ The semigroup operation+semigroup trainonline pseudoinverse = \model1 model2 -> trainonline model1 (pseudoinverse model2)+    +-------------------------------------------------------------------------------+-- Helper Functions++-- | Like fold, but (i) only for use on the semigroup operation (\<\>) and (ii) uses the fan-in reduction strategy which is more efficient when the semigroup operation takes nonconstant time depending on the size of the data structures being reduced.+reduce :: +    ( Semigroup sg+    , CK.Foldable container+    , CK.FoldableConstraint container sg+    , CK.FoldableConstraint container [sg]+    ) => container sg -> sg+reduce = reduceL . CK.toList++reduceL :: (Semigroup sg) => [sg] -> sg+reduceL []  = error "reduce: cannot reduce empty list"+reduceL [x] = x+reduceL xs  = reduceL $ itr xs+    where+        itr :: (Semigroup sg) => [sg] -> [sg]+        itr []            = []+        itr [x]           = [x]+        itr (x1:x2:xs)    = (x1<>x2):(itr xs)
+ src/HLearn/Algebra/Models.hs view
@@ -0,0 +1,131 @@+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE FunctionalDependencies #-}+{-# LANGUAGE TypeSynonymInstances #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE ConstraintKinds #-}++-- | The 'HomTrainer' class forms the base of the HLearn library.  It represents homomorphisms from a free monoid/group to any other structure.  This captures our intuitive notion of how data mining and machine learning algorithms should behave, but in a way that allows for the easy creation of parallel and online algorithms.+--+-- Unfortunately, we must slightly complicate the matter by also introducing the 'Model' class.  Many learning algorithms take some sort of parameters, and we need the model class to define what those parameters should look like.  ++module HLearn.Algebra.Models+    ( +    -- * Parameters+    Model (..)+    , DefaultModel (..)+    +    -- * HomTrainer+    , HomTrainer (..)+    , DefaultHomTrainer (..)+    +    -- * Type synonyms+    , Labeled+    , Weighted+    , Label (..)++    , module Control.DeepSeq+    , module Data.Hashable+    , module Data.Binary+    )+    where+          +import qualified Control.ConstraintKinds as CK+          +import HLearn.Algebra.Structures+import HLearn.Algebra.Functions++import Control.DeepSeq+import Data.Hashable+import Data.Binary++-------------------------------------------------------------------------------+-- Idioms++type Labeled var label  = (label,var)+type Weighted var       = (var,Double)++-- | I only ever expect labels of type Bool, Int, and String, but it may be convenient to use other types as well for something.  This class and instance exist so that we have some reasonable assumptions about what properties labels should have for our other classes to work with.  It also keeps us from writing so many constraints.+class (Hashable label, Binary label, Ord label, Eq label, Show label, Read label) => Label label+instance (Hashable label, Binary label, Ord label, Eq label, Show label, Read label) => Label label++-------------------------------------------------------------------------------+-- Model++-- | Every model has at least one data type that that fully describes its parameters.  Many models do not actually *need* any parameters, in which case they will simply use an empty data type for modelparams.+class Model modelparams model | modelparams -> model, model -> modelparams where+    getparams :: model -> modelparams+    +-- | For those algorithms that do not require parameters (or that have reasonable default parameters), this class lets us use a more convenient calling notation.+class (Model modelparams model) => DefaultModel modelparams model where+    defparams :: modelparams++-- | A minimal complete definition of the class is the singleton trainer 'train1dp\''+class +    ( Semigroup model+    , Monoid model+    , Model modelparams model+    ) => HomTrainer modelparams datapoint model+        where++    -- | The singleton trainer+    {-# INLINE train1dp' #-}+    train1dp' :: modelparams -> datapoint -> model+    train1dp' modelparams = unbatch (train' modelparams)+    +    -- | The batch trainer+    {-# INLINE train' #-}+    train' ::     +        ( CK.Functor container+        , CK.FunctorConstraint container model+        , CK.FunctorConstraint container datapoint+        , CK.Foldable container+        , CK.FoldableConstraint container model+        ) => modelparams -> container datapoint -> model+    train' modelparams = batch (train1dp' modelparams)+    +    -- | The online trainer+    {-# INLINE add1dp #-}+    add1dp :: model -> datapoint -> model+    add1dp model = online (train1dp' (getparams model :: modelparams)) model+    +    -- | The batch online trainer; will be more efficient than simply calling 'add1dp' for each element being added+    {-# INLINE addBatch #-}+    addBatch ::+        ( CK.Functor container+        , CK.FunctorConstraint container model+        , CK.FunctorConstraint container datapoint+        , CK.Foldable container+        , CK.FoldableConstraint container model+        ) =>  model -> container datapoint -> model+    addBatch model = online (train' (getparams model :: modelparams)) model+    +    +-- | Provides parameterless functions for those training algorithms that do not require parameters+class +    ( DefaultModel modelparams model+    , HomTrainer modelparams datapoint model+    ) => DefaultHomTrainer modelparams datapoint model+        where+              +    -- | A singleton trainer that doesn't require parameters (uses 'defparams')+    {-# INLINE train1dp #-}+    train1dp :: datapoint -> model+    train1dp = train1dp' (defparams :: modelparams)+    +    -- | A batch trainer that doesn't require parameters (uses 'defparams')+    {-# INLINE train #-}+    train :: +        ( CK.Functor container+        , CK.FunctorConstraint container model+        , CK.FunctorConstraint container datapoint+        , CK.Foldable container+        , CK.FoldableConstraint container model+        ) => container datapoint -> model+    train = train' (defparams :: modelparams)+    +instance +    ( DefaultModel modelparams model+    , HomTrainer modelparams datapoint model+    ) => DefaultHomTrainer modelparams datapoint model
+ src/HLearn/Algebra/Structures.hs view
@@ -0,0 +1,71 @@+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE UndecidableInstances #-}++-- | These algebraic structures have sacrificed generality in favor of being easily used with the standard Haskell Prelude.  The fact that monoids are not guaranteed to be semigroups makes this difficult.++module HLearn.Algebra.Structures+    ( +    -- * Type classes+    RegularSemigroup (..)+    , Group(..)+    +    -- * Free Structures+    , RegSG2Group (..)++    , module Data.Semigroup+    )+    where++import Data.Semigroup++-------------------------------------------------------------------------------+-- Inverses++-- | Semigroups that also have an inverse.  See <https://en.wikipedia.org/wiki/Regular_semigroup>+class (Semigroup g) => RegularSemigroup g where+    inverse :: g -> g++-- -- | Semigroups where a unique inverse exists for each element.  See <https://en.wikipedia.org/wiki/Inverse_semigroup>+-- class (RegularSemigroup g) => InverseSemigroup g++-- | Regular semigroups that also have an identity; alternatively, monoids where every element has a unique inverse.  See <https://en.wikipedia.org/wiki/Group_(mathematics)>+class (RegularSemigroup g, Monoid g) => Group g++-------------------------------------------------------------------------------+-- RegSG2Group+++-- | Convert any regular semigroup into a group (and thus also a monoid) by adding a unique identity element+data (RegularSemigroup sg) => RegSG2Group sg = SGNothing | SGJust sg+    deriving (Show,Read,Ord,Eq)++instance (RegularSemigroup sg) => Semigroup (RegSG2Group sg) where+    SGNothing <> m = m+    m <> SGNothing = m+    (SGJust sg1) <> (SGJust sg2) = SGJust $ sg1<>sg2++instance (RegularSemigroup sg) => RegularSemigroup (RegSG2Group sg) where+    inverse SGNothing = SGNothing+    inverse (SGJust x) = SGJust $ inverse x++instance (RegularSemigroup sg) => Monoid (RegSG2Group sg) where+    mempty = SGNothing+    mappend = (<>)+    +instance (RegularSemigroup sg) => Group (RegSG2Group sg)++-- -------------------------------------------------------------------------------+-- -- SG2Monoid+-- +-- data (Semigroup sg) => SG2Monoid sg = SGNothing | SGJust sg+--     deriving (Show,Read)+-- +-- instance (Semigroup sg) => Monoid (SG2Monoid sg) where+--     mempty = SGNothing+--     mappend SGNothing m = m+--     mappend m SGNothing = m+--     mappend (SGJust sg1) (SGJust sg2) = SGJust $ sg1<>sg2+-- +-- instance (Semigroup sg) => Semigroup (SG2Monoid sg) where+--     (<>) = mappend