packages feed

semiring (empty) → 0.1

raw patch · 12 files changed

+503/−0 lines, 12 filesdep +Booleandep +HUnitdep +QuickChecksetup-changed

Dependencies added: Boolean, HUnit, QuickCheck, base, containers, monoids, test-framework, test-framework-hunit, test-framework-quickcheck2

Files

+ LICENSE view
@@ -0,0 +1,30 @@+Copyright (c) 2008, University of Brighton+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.+    * Redistributions in binary form must reproduce the above copyright+      notice, this list of conditions and the following disclaimer in+      the documentation and/or other materials provided with the+      distribution.+    * Neither the name of the University of Brighton nor the names of+      its contributors may be used to endorse or promote products+      derived from this software without specific prior written+      permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS+FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE+COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,+INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,+BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT+LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN+ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE+POSSIBILITY OF SUCH DAMAGE.
+ NLP/Semiring.hs view
@@ -0,0 +1,63 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module NLP.Semiring(+  -- * Semiring+  --                    +  -- $SemiringDesc++  Multiplicative(..), +  Monoid(..), +  Semiring, +  WeightedSemiring, +  Weighted(..)) where+ +import Data.Monoid+import Data.Monoid.Multiplicative +import Data.Monoid.Additive +import Data.Function (on)++++-- $SemiringDesc+-- Semirings (rings without additive inverses, <http://en.wikipedia.org/wiki/Semiring>) are +-- a commonly used structure for performing computations over finite state machines, +-- parsers, and other dynamic programmy-systems. This library extends the basic structures  +-- defined for Monoids to Semirings and includes implementations of the major semirings +-- for parsing. +--+-- This work is based largely on "Semiring Parsing" by Joshua Goodman. (<http://www.ldc.upenn.edu/acl/J/J99/J99-4004.pdf>)  +-- which describes many of the interesting parsing semirings.++++-- | A 'Semiring' is made up of an additive Monoid and a Multiplicative.+--   It must also satisfy several other algebraic properties checked by quickcheck. +class (Multiplicative a, Monoid a) => Semiring a+++-- | A 'WeightedSemiring' also includes a sensical ordering over choices. +--   i.e. out of two choices which is better. This is used for Viterbi selection.   +class (Semiring a, Ord a) => WeightedSemiring a++   +instance (Multiplicative a, Multiplicative b) => Multiplicative (a,b) where +    one = (one, one)+    times (a, b) (a', b') = (a `times` a', b `times` b')+++-- | Dual semirings can be useful. For instance combining the  +--   Prob semiring and the MultiDerivation ring gives the total likelihood of +--   a derivation along with the paths to get there. +instance (Semiring a, Semiring b) => Semiring (a,b)  +++-- | The 'Weighted' type is the main type of WeightedSemiring.+--   It combines scoring semiring with a history semiring.+-- +--   The best example of this is the ViterbiDerivation semiring.+newtype Weighted semi1 semi2 = Weighted (semi1, semi2)+    deriving (Eq, Show, Monoid, Multiplicative, Semiring)++instance (Ord semi1, Eq semi2) => Ord (Weighted semi1 semi2) where +    compare (Weighted s1) (Weighted s2) = (compare `on` fst) s1 s2 ++instance (WeightedSemiring a, Eq b, Semiring b) => WeightedSemiring (Weighted a b)
+ NLP/Semiring/Boolean.hs view
@@ -0,0 +1,17 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module NLP.Semiring.Boolean where+import NLP.Semiring+import qualified Data.Boolean as B+import Data.Boolean ((&&*),(||*)) +newtype Boolean = Boolean Bool+    deriving (Eq, Show, B.Boolean) ++instance Multiplicative Boolean where+    one = B.true+    times = (&&*)++instance Monoid Boolean where +    mempty = B.false+    mappend = (||*)++instance Semiring Boolean
+ NLP/Semiring/Counting.hs view
@@ -0,0 +1,21 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module NLP.Semiring.Counting where+import NLP.Semiring++-- | The 'Counting' semiring keeps track of the number of paths +--   or derivations led to a given output.+newtype Counting = Counting Integer+    deriving (Eq, Show, Num, Ord) ++instance Multiplicative Counting where+    one = 1+    times = (*) ++instance Monoid Counting where +    mempty = 0+    mappend = (+)+++instance Semiring Counting +instance WeightedSemiring Counting +
+ NLP/Semiring/Derivation.hs view
@@ -0,0 +1,59 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module NLP.Semiring.Derivation (Derivation(..), MultiDerivation(..)) where+import NLP.Semiring+import NLP.Semiring.Helpers+import qualified Data.Set as S +import Data.Monoid+import Data.Maybe (isNothing)+++-- | The 'Derivation' semiring keeps track of a single path or derivation +--   that led to the known output. If there are more than one path it discards +--   in favor the lesser path (based on ord). The main purpose of this semiring +--   is to track derivations for ViterbiNBestDerivation. If you want to keep all paths, +--   use 'MultiDerivation'.+--+--   Derivation takes a Monoid as an argument that describes how to build up paths or +--   more complicated structures.  +newtype Derivation m = Derivation (Maybe m)+    deriving (Eq, Show, Ord) ++instance (Monoid m) => Multiplicative (Derivation m) where+    one = Derivation $ Just mempty+    times (Derivation d1) (Derivation d2) = Derivation $ do +        d1' <- d1+        d2' <- d2+        return $ mappend d1' d2'++instance (Ord m) => Monoid (Derivation m) where +    mempty = Derivation Nothing+    mappend (Derivation s1) (Derivation s2) = +        Derivation $ case (s1,s2) of +                       (Nothing, s2) -> s2+                       (s1, Nothing) -> s1+                       (s1, s2) -> max s1 s2                          ++instance (Monoid m, Eq m, Ord m) => Semiring (Derivation m)+++-- | The 'MultiDerivation' semiring keeps track of a all paths or derivations +--   that led to the known output. This can be useful for debugging output.+-- +--  Keeping all these paths around can be expensive. 'MultiDerivation' leaves open +--  the implementation of the internal path monoid for more compact representations. +newtype MultiDerivation m = MultiDerivation (S.Set m)+    deriving (Eq, Show, Ord) ++instance (Monoid m, Ord m) => Multiplicative (MultiDerivation m) where+    one = MultiDerivation $ S.fromList [mempty]+    times (MultiDerivation d1) (MultiDerivation d2) = MultiDerivation $ +        S.fromList $ +        map (uncurry mappend) $ +        cartesian (S.toList d1) (S.toList d2) ++instance (Ord m) => Monoid (MultiDerivation m) where +    mempty = MultiDerivation S.empty+    mappend (MultiDerivation s1) (MultiDerivation s2) = MultiDerivation $ S.union s1 s2++instance (Ord m, Monoid m, Eq m) => Semiring (MultiDerivation m)+
+ NLP/Semiring/Prob.hs view
@@ -0,0 +1,19 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module NLP.Semiring.Prob where +import NLP.Semiring++-- | The 'Prob' semiring keeps track of the likelihood of the known output +--   by keeping track of the probability of all paths. +newtype Prob = Prob Double+    deriving (Eq, Show, Num, Fractional, Ord) ++instance Multiplicative Prob where+    one = 1.0+    times = (*) ++instance Monoid Prob where +    mempty = 0.0+    mappend = (+)++instance Semiring Prob +instance WeightedSemiring Prob
+ NLP/Semiring/Viterbi.hs view
@@ -0,0 +1,12 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+module NLP.Semiring.Viterbi where+import NLP.Semiring+import NLP.Semiring.ViterbiNBest++data One = One  +instance N One where +    mkN = One+    n _ = 1++type Viterbi semi = ViterbiNBest One semi+
+ NLP/Semiring/ViterbiNBest.hs view
@@ -0,0 +1,50 @@+{-# LANGUAGE ExistentialQuantification, ScopedTypeVariables #-}+module NLP.Semiring.ViterbiNBest where+import NLP.Semiring+import NLP.Semiring.Helpers+import Data.List +++class N a where +    mkN :: a+    n :: a -> Int+    +-- | The 'ViterbiNBest' semiring keeps track of the n best scoring path to a known+--   output. This score is determined by a user defined 'WeightedSemiring'. +-- +--   The value of n (the number of of values to rank) is included in the type to prevent +--   combining mismatching values. To create a new n, make a new unary type and an instance+--   of N.+-- +-- @+--   data Ten = Ten  +--   instance N Ten where +--    mkN = Ten+--    n _ = 10+-- @+-- +data ViterbiNBest n semi = ViterbiNBest [semi] +  deriving (Eq, Show)++instance (N n, Ord semi, WeightedSemiring semi) => Multiplicative (ViterbiNBest n semi) where+    one = ViterbiNBest [one]+    times (ViterbiNBest a) (ViterbiNBest b) = +        ViterbiNBest $+        take (n (mkN::n)) $+        reverse $ sort $+        map (uncurry times) $ cartesian a b ++instance (N n, WeightedSemiring semi, Ord semi) => Monoid (ViterbiNBest n semi) where +    mempty = ViterbiNBest []+    mappend (ViterbiNBest a) (ViterbiNBest b) = +        ViterbiNBest $ take (n (mkN::n)) $ reverse $ sort (a ++ b)++instance (N n, WeightedSemiring semi, Ord semi) => Semiring (ViterbiNBest n semi)+++data Ten = Ten  +instance N Ten where +    mkN = Ten+    n _ = 10++type Viterbi10Best semi = ViterbiNBest Ten semi
+ NLP/Semiring/ViterbiNBestDerivation.hs view
@@ -0,0 +1,21 @@+module NLP.Semiring.ViterbiNBestDerivation where+import NLP.Semiring+import Data.List +import NLP.Semiring.Viterbi+import NLP.Semiring.ViterbiNBest+import NLP.Semiring.Prob+import NLP.Semiring.Derivation++-- | The 'ViterbiNBestDerivation' is an example of a more complicated semiring+--   built up from smaller components. It keeps track of the top N scoring paths +--   along with their derivations.+-- +-- > type ViterbiNBestDerivation n m = ViterbiNBest n (Weighted Prob (Derivation m))+type ViterbiNBestDerivation n m = ViterbiNBest n (Weighted Prob (Derivation m))+++-- | The 'ViterbiDerivation' is a simpler semiring. It just keeps track of the best +--   scoring path and it's derivation.+--  +-- > type ViterbiDerivation m  = Viterbi (Weighted Prob (Derivation m))+type ViterbiDerivation m  = Viterbi (Weighted Prob (Derivation m))
+ Setup.lhs view
@@ -0,0 +1,3 @@+#!/usr/bin/env runhaskell+> import Distribution.Simple+> main = defaultMain
+ semiring.cabal view
@@ -0,0 +1,54 @@+name:                semiring+version:             0.1+synopsis:            Semirings, ring-like structures used for dynamic programming applications +description:         This provides a type class for semirings and +                     implementations of the common semirings used in natural language +                     processing.+category:            Natural Language Processing+license:             BSD3+license-file:        LICENSE+author:              Sasha Rush+maintainer:          <srush at mit dot edu>+build-Type:          Simple+cabal-version:       >= 1.2++flag testing+    description: Testing mode, only build minimal components+    default: False++library+    exposed-modules:     NLP.Semiring+                         NLP.Semiring.Boolean+                         NLP.Semiring.Prob+                         NLP.Semiring.Viterbi+                         NLP.Semiring.ViterbiNBest+                         NLP.Semiring.Counting+                         NLP.Semiring.Derivation+                         NLP.Semiring.ViterbiNBestDerivation++    if flag(testing)+        buildable: False++    build-Depends:   base       >= 3   && < 4,+                     containers >= 0.1 && < 0.3,+                     monoids    >= 0.2.0.2 && < 0.3,+                     Boolean++executable hstestsemi+    main-is:            Tests.hs+    hs-source-dirs: . tests/++    build-Depends:   base       >= 3   && < 4,+                     containers >= 0.1 && < 0.3,+                     monoids    >= 0.2.0.2 && < 0.3,+                     Boolean,+                     QuickCheck >= 2,+                     HUnit,+                     test-framework,+                     test-framework-hunit,+                     test-framework-quickcheck2+                    +                     +    if !flag(testing)+        buildable: False+
+ tests/Tests.hs view
@@ -0,0 +1,154 @@+{-# LANGUAGE ScopedTypeVariables #-}+module Main where ++import Test.Framework (defaultMain, testGroup)+import Test.Framework.Providers.HUnit+import Test.Framework.Providers.QuickCheck2 (testProperty)++import Test.QuickCheck+import Test.HUnit++import NLP.Semiring+import NLP.Semiring.Boolean+import NLP.Semiring.Prob+import NLP.Semiring.Viterbi+import NLP.Semiring.ViterbiNBest+import NLP.Semiring.Counting+import NLP.Semiring.Derivation+import NLP.Semiring.ViterbiNBestDerivation++import qualified Data.Set as S+import Data.List+import Control.Monad (liftM)++main = defaultMain tests++tests = [+        testGroup "Semiring Props"  [+                       testProperty "semiProb bool" prop_boolRing,+                       testProperty "semiProb prob" prop_probRing,+                       testProperty "semiProb viterbi" prop_viterbiRing,+                       testProperty "semiProb counting" prop_counting, +                       testProperty "semiProb viterbi n-best" prop_viterbiNBest,+                       testProperty "semiProb derivation" prop_derivation,+                       testProperty "semiProb multi-derivation" prop_multiDerivation,+                       testProperty "semiProb nbest derivation" prop_nbestMultiDerivation+            ]+        ]++instance Arbitrary Prob where +    arbitrary = Prob `liftM` choose (0.0, 1.0)++instance (N n, Ord a, Arbitrary a) => Arbitrary (ViterbiNBest n a) where +    arbitrary = do+      v <- arbitrary+      return $ ViterbiNBest $ reverse $ sort $ take (n $ (mkN::n)) $ v+ +instance Arbitrary Boolean where +    arbitrary = Boolean `liftM` choose (True, False)++instance Arbitrary Counting where +    arbitrary = Counting `liftM` abs `liftM` arbitrary++instance (Arbitrary a) => Arbitrary (Derivation a) where +    arbitrary = Derivation `liftM` arbitrary ++instance (Arbitrary a, Ord a) => Arbitrary (MultiDerivation a) where +    arbitrary = (MultiDerivation . S.fromList . take 10) `liftM` arbitrary +           +instance (Arbitrary a, Arbitrary b) => Arbitrary (Weighted a b) where +    arbitrary = Weighted `liftM` arbitrary +++type Eql s = (s -> s -> Bool) +++-- (a * b) * c = a * (b * c)+associativeTimes :: (Semiring s) => (s,s,s) -> Eql s -> Bool+associativeTimes (s1, s2, s3) eq =  +    ((s1 `times` s2) `times` s3) `eq`+    (s1 `times` (s2 `times` s3))++-- (a + b) + c = a + (b + c)+associativePlus :: (Semiring s) => (s,s,s) -> Eql s -> Bool+associativePlus (s1, s2, s3) eq = +    ((s1 `mappend` s2) `mappend` s3) `eq`+     (s1 `mappend` (s2 `mappend` s3))+++-- a + b = b + a+commutativePlus :: (Semiring s) => (s,s,s) -> Eql s -> Bool+commutativePlus (a, b, _) eq = +    (a `mappend` b)  `eq`+    (b `mappend` a)+++-- a * (b + c) = (a * b) +  (a * c)+distribution :: (Semiring s) => (s,s,s) -> Eql s -> Bool+distribution (s1, s2, s3) eq = +    (s1 `times` (s2 `mappend` s3)) `eq`+    ((s1 `times` s2) `mappend` (s1 `times` s3))+++-- a + 0 = 0 + a = a+zeroAdd :: (Semiring s) => (s,s,s) -> Eql s -> Bool+zeroAdd (a, _, _) eq = +    (mempty `mappend` a) `eq` a &&+    (a `mappend` mempty) `eq` a+++-- a * 0 = 0+zeroMult :: (Semiring s) => (s,s,s) -> Eql s -> Bool+zeroMult (a, _, _) eq = +    (mempty `times` a) `eq` mempty && +    (a `times` mempty) `eq` mempty +                     +++oneMult :: (Semiring s) => (s,s,s) -> Eql s -> Bool+oneMult (a, _, _) eq = +    (one `times` a) `eq` a &&+    (a `times` one) `eq` a++semiRingProps :: (Semiring s) => (s,s,s) -> Eql s -> Bool+semiRingProps s eq = and [distribution s eq, +                          associativePlus s eq, +                          zeroAdd s eq, +                          zeroMult s eq, +                          oneMult s eq, +                          commutativePlus s eq, +                          associativeTimes s eq]++doubEq a b = abs (a - b) < 0.000001 ++prop_probRing s1 s2 s3 = semiRingProps (s1, s2, s3) doubEq+  where types = ((s1,s2,s3 ):: (Prob, Prob, Prob))++prop_boolRing s1 s2 s3 = semiRingProps (s1, s2, s3) (==)+  where types = ((s1,s2,s3 ):: (Boolean, Boolean, Boolean))++prop_viterbiRing s1 s2 s3 = semiRingProps (s1, s2, s3) +                            (\(ViterbiNBest a) (ViterbiNBest b) -> and $ zipWith doubEq a b)+  where types = ((s1,s2,s3 ):: (Viterbi Prob, Viterbi Prob, Viterbi Prob))++prop_counting s1 s2 s3 = semiRingProps (s1, s2, s3) (==)+  where types = ((s1,s2,s3 ):: (Counting, Counting, Counting))+++prop_viterbiNBest s1 s2 s3 = semiRingProps (s1, s2, s3) (==)+  where types = ((s1,s2,s3 ):: (Viterbi10Best Counting, Viterbi10Best Counting, Viterbi10Best Counting))+++prop_derivation s1 s2 s3 = semiRingProps (s1, s2, s3) (==)+  where types = ((s1,s2,s3):: (Derivation String, Derivation String, Derivation String))++prop_multiDerivation s1 s2 s3 = semiRingProps (s1, s2, s3) (==)+  where types = ((s1,s2,s3):: (MultiDerivation String, MultiDerivation String, MultiDerivation String))++prop_nbestMultiDerivation s1 s2 s3 = +    semiRingProps (s1, s2, s3) +                      (\(ViterbiNBest a) (ViterbiNBest b) ->+                           and $ zipWith +                                   (\(Weighted (a,b)) (Weighted (a',b')) -> +                                        doubEq a a' && b == b') a b)+  where types = ((s1,s2,s3):: (ViterbiNBestDerivation Ten String, ViterbiNBestDerivation Ten String, ViterbiNBestDerivation Ten String))