Simple Gradient Descent Algorithm In Haskell

Question

After becoming interested in various bits of functional programming provided by non-functional languages, I've recently decided to start learning Haskell. As I'm fairly experienced with conventional imperative programming languages, I decided to make my "hello world" something a little more complex - an implementation of gradient descent with 2 variables.

The idea with this code is that you fill in the training set for the algorithm in the code, and then run the code something similar to this:

descentFunc = singleDescend trainingSet 0.1 deltas = descend descentFunc ( 100, 1 ) 100000 

Where 0.1 is the learning rate (referred to as lr in the code) 100000 is the number of iterations for the loop, and ( 100, 1 ) is an initial guess for the coefficients.

The actual code that's running is below. As I'm entirely new to Haskell, I was wondering whether code such as this is acceptable? And whether there's any obvious idioms I'm missing/misusing or any glaring style errors I've made.

Any comments on my implementation of the algorithm are welcome also.

import Data.List trainingSet = [ (1.0,10.0),(2.0,20.0),(3.0,30.0),(4.0,40.0) ] hypothesis (d1,d2) x = d1 + (d2 * x) squareDiff d (x,y) = diff * diff where diff = ( hypothesis d x ) - y costFunc ts d = scaleFactor * sum squares where scaleFactor = 1.0 / (2 * genericLength ts) squares = map (squareDiff d) ts diff d (x,y) = (hypothesis d x) - y descendTheta thetaFunc deltaFunc ts lr deltas = deltaFunc deltas - (scaleFactor * sum scaledDiffs) where scaleFactor = lr / genericLength ts diffs = map (diff deltas) ts scaledDiffs = map (\(x,y) -> x * thetaFunc y) $ zip diffs ts descendThetaZero = descendTheta (\_ -> 1) fst descendThetaOne = descendTheta (fst) snd singleDescend ts lr deltas = (thetaZero,thetaOne) where thetaZero = descendThetaZero ts lr deltas thetaOne = descendThetaOne ts lr deltas descend func deltas i | i == 0 = deltas | otherwise = descend func ( func deltas ) ( i - 1 ) 

Answer 1

Welcome to haskell, Your code is quite good for a beginner, I have only peripheral recommendations on your style.

import Test.HUnit import Data.List import Control.Arrow 

As @epsilon 'εⳆ2' halbe suggested below, use type signatures to define your functions first, this would help you avoid obvious errors.

type DeltaPair = (Double, Double) type PairFunc = DeltaPair -> Double trainingSet = [(1.0,10.0),(2.0,20.0),(3.0,30.0),(4.0,40.0)] 

The classes in Control.* are often very useful. These are just your functions that have been modified a little bit. This may seem like overkill to you, but as a beginner, you would profit tremendously if you internalize the functions in the Control.* space. At the very least, understand the functions used here. (I would certainly recommend your definition of the diff over this, but the point here is one of demonstration.)

diff :: DeltaPair -> DeltaPair -> Double diff d = uncurry (-) . first (flip hypothesis d) where hypothesis x = uncurry (+) . first (* x) 

The scaleDiffs can be written in two ways, one by recognizing that it is actually a zipWith and the other, using the functions in Control.Arrow to manipulate the pair. The second gets you a pointfree form. Use which ever you feel comfortable with, but understand both.

I have replaced genericLength with fromIntegral . length because it seems from your training set that the set is not very large. If that is not the case, change it back to genericLength

descendTheta :: PairFunc -> PairFunc -> [DeltaPair] -> Double -> DeltaPair -> Double descendTheta thetaFunc deltaFunc ts lr deltas = deltaFunc deltas - sSum where scaleFactor = lr / fromIntegral (length ts) -- scaledDiffs ts = zipWith (\x y -> x * thetaFunc y) (diffs ts) ts scaledDiffs ts = map (uncurry (*) . second thetaFunc) $ zip (diffs ts) ts diffs = map (diff deltas) sSum = scaleFactor * sum (scaledDiffs ts) 

It is often hard to decide which definitions go on the top level. A good rule of thumb is to see if the function being defined can be reused elsewhere. If they can't then they probably are better of as sub definitions under a where clause.

singleDescend :: [DeltaPair] -> Double -> DeltaPair -> DeltaPair singleDescend ts lr deltas = (fn descendThetaZero, fn descendThetaOne) where fn f = f ts lr deltas descendThetaZero = descendTheta (const 1) fst descendThetaOne = descendTheta fst snd 

We should always be on the look out for general functions. These help us tremendously in refactoring the code. Here is one such function.

napply :: Int -> (c -> c) -> c -> c napply n = ((!! n) .) . iterate descend :: (DeltaPair -> DeltaPair) -> DeltaPair -> Int -> DeltaPair descend = flip . flip napply deltas n = descend descentFunc (100, 1) n where descentFunc = singleDescend trainingSet 0.1 

A few unit tests

tests = TestList [ TestLabel "1" test1, TestLabel "2" test2, TestLabel "3" test3 ] test1 = TestCase $ assertEqual "A1" (100.0, 1.0) (deltas 0) test2 = TestCase $ assertEqual "A1" (92.25,-17.25) (deltas 1) test3 = TestCase $ assertEqual "A1" (89.8375,-19.875) (deltas 2) tt = runTestTT tests 

These two does not seem to be used any where

{- squareDiff :: Num a => (a, a) -> (a, a) -> a squareDiff = ((^ 2) .) . diff costFunc :: Fractional a => [(a, a)] -> (a, a) -> a costFunc ts d = scaleFactor * sum squares where scaleFactor = 1.0 / (2 * fromIntegral (length ts)) squares = map (squareDiff d) ts -} 

Answer 2

one obvious change would be to add type signatures, i additionally introduced some type synonyms to distinguish between all those Doubles. A bit explanation could be done towards the algorithm - I don't know what it actually want to achieve. I am no programmer so the non understanding comes quite often.

Next thing is it seems costFunc is never used - why is it there?

and I've replaced genericLength by length and converting the result - as the library says length is faster.

type TrainData = [(Double,Double)] type LearnRate = Double type DeltaPair = (Double,Double) trainingSet :: TrainData trainingSet = [ (1.0,10.0),(2.0,20.0),(3.0,30.0),(4.0,40.0) ] hypothesis :: DeltaPair -> Double -> Double hypothesis (d1,d2) x = d1 + (d2 * x) costFunc :: TrainData -> DeltaPair -> Double costFunc ts d = scaleFactor * sum squares where scaleFactor = 1.0 / (2 * fromIntegral (length ts)) squares = map (square . diff d) ts square x = x * x diff :: DeltaPair -> (Double, Double) -> Double diff d (x,y) = hypothesis d x - y descendTheta :: ((Double, Double) -> Double) -> (DeltaPair -> Double) -> TrainData -> LearnRate -> DeltaPair -> Double descendTheta thetaFunc deltaFunc ts lr deltas = deltaFunc deltas - (scaleFactor * sum scaledDiffs) where scaleFactor = lr / fromIntegral (length ts) diffs = map (diff deltas) ts scaledDiffs = map (\(x,y) -> x * thetaFunc y) $ zip diffs ts descendThetaZero :: TrainData -> LearnRate -> (Double, Double) -> Double descendThetaZero = descendTheta (const 1) fst descendThetaOne :: TrainData -> LearnRate -> (Double, Double) -> Double descendThetaOne = descendTheta fst snd singleDescend :: TrainData -> LearnRate -> DeltaPair -> DeltaPair singleDescend ts lr deltas = (thetaZero, thetaOne) where thetaZero = descendThetaZero ts lr deltas thetaOne = descendThetaOne ts lr deltas descend :: (DeltaPair -> DeltaPair) -> DeltaPair -> Int -> DeltaPair descend f deltas i | i < 0 = error "no negative numbers" | i == 0 = deltas | otherwise = descend f (f deltas) (i-1) main :: IO () main = print (descend descendFunc (100, 1) 10000) where descendFunc = singleDescend trainingSet 0.1 

Answer 3

This was the simplest rewrite of your code that I could come up with:

{-# LANGUAGE UnicodeSyntax #-} import Data.List trainingSet = [(1, 10), (2, 20), (3, 30), (4, 40)] hypothesis (δ1, δ2) x = δ1 + δ2 * x diff δs (x, y) = hypothesis δs x - y average xs = realToFrac (sum xs) / genericLength xs descendθ θFunc ts lr δs = lr * average (map (\t -> diff δs t * θFunc t) ts) next ts lr δs@(δ0, δ1) = (δ0', δ1') where δ0' = δ0 - descendθ (\(x, y) -> 1) ts lr δs δ1' = δ1 - descendθ (\(x, y) -> x) ts lr δs descend f δs i = iterate f δs !! i 

Some general comments:

You don't need to put .0s on your numeric literals to indicate they are Doubles like you would in C. A type signature will suffice.

I used the unicode syntax extension for greek variable names to make it easier on my eyes.

Your descend function is just iterate in disguise.

Your variable naming in your descendTheta function was incredibly confusing, since you name your output variables theta, even thought they are basically the same as your input variables, which you named delta. I decided to name them both delta for consistency, leaving theta only to refer to the projection of the data set that you are descending on.

Your scaledDiffs function was incredibly awkward and a round-about way to do what essentiallyw as a single map and average. Unfortunately, the average function is not in the Haskell standard library, but the definition I included in the code is the most general version and will type-check for anything you would want to average.

Your training set and learning rate are constant over the entire run, so you could actually improve the above code even more by using the Reader monad to thread those variables through your code without explicit parameter-passing. If you don't know what the Reader monad is, just ask and I will update this post with a demonstration of it. It's very easy to use.

Also, I disagree that you must put type signatures on your code. For application code that only you will maintain, using type signatures is mostly a matter of style. For libraries, though, or code other people have to maintain, I would strongly recommend type signatures.