Friday, August 27, 2010

Fuzzy Logic in F#, Now More Functional!

Before moving forward with some fuzzy logic examples, I decided to take a step back in complexity. I decided that my “tzoid” approach was overkill for 80% of the cool stuff you can do with fuzzy logic. So I came up with something simpler and more functional. But first, a bit more background on fuzzy inference and what I’m trying to achieve.

In its most basic form, fuzzy inference uses at least one pair of fuzzy sets to map a crisp input value onto a new crisp output value. There are a number of ways to do this, but the most common is to take the height of the input set at the input value as x, use that height to truncate the output set, and then “defuzzify” that output set to a crisp value. (Different defuzzification methods work better depending on the domain, but using the centroid is one common method.)

In pseudo-F#, and graphically, this process might look like:

inputValue |> (heightAt inputSet) |> (truncate outputSet) |> defuzzify

The former is for a single rule. However, most applications require a rule set of a number of rules. The process can be extended by mapping and folding, and then applying some defuzzification function such as a weighted average. Again in pseudo-F#, and graphically, this extended process might look like:

|> map ( (heightAt inputSet) >> (truncate outputSet)) ruleset
|> fold defuzzify

And lastly, the input value and input set might be extended to vectors of paired values, each handling a different type of input (e.g. speed, height, acceleration, etc.). These can be combined by some simple method, for example, taking the minimum height for conjunctive rules, the maximum height for disjunctive rules, etc.

So what is the minimal useful implementation of this? Here are some ideas:

1) To start with, I’ll assume a single input set rather than a vector. This will simplify things, and the resulting code will be easy to extend to vectors.

2) Any input set can be described as a simple trapezoid. (Perhaps with an infinite extension on one axis or another.)

3) Any output set can be described as a symmetric triangle. (i.e. an isosceles triangle with its base on the x-axis.)

4) All the sets have a maximum membership value of one.

5) The defuzzification function is a weighted average of truncated output triangle area and centroid.

The code below demonstrates an implementation of this using the tomato price example from an earlier post. Since all the input sets in the original problem were describable as trapezoids and all the output sets were describable as symmetric triangles, the result is identical. Except, of course, there is a lot less source code this time around. (As always, all the code here is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

So what is the “take away”?

It’s not that fuzzy logic is some magic method which yields results not achievable by any other method. The truth is, most problems solvable by fuzzy logic are solvable by other means, such as regression, differential equations, numeric modeling, or other types of rule-based systems. And sometimes, if they are made complex enough or are based on enough data, these other methods can yield more exact results.

What the take away is, is this: fuzzy logic is a conceptually compact and computationally efficient means for transferring imprecise, high-level solutions into precise computer logic.

Very simple, in fact so simple that:

1) Fuzzy logic can be made cheap enough for consumer appliances like microwave ovens, washing machines, and vacuum cleaners.

2) Fuzzy logic can be made reasonably cheap and fast. Fast enough to hundreds or even thousands of inferences per second for things like video cameras and machine control.

3) Fuzzy logic can be made reasonably cheap and parallel. For example, image enhancement for a digital camera by processing entire blocks of pixels. And fuzzy logic is simple enough that it can be implemented on other-purpose parallel hardware – such as graphics adapters – without too much effort. It’s not difficult to imagine an F# implementation of some fuzzy logic system which uses a domain specific language (DSL) and/or F# quotations to interface using CUDA or even High Level Shader Language (HLSL).

module Fuzzy
// Type abbreviations.
type InFunc = float->float
type OutFunc = float->(float*float)
// The input functions are trapezoids.
// The precomputations and closures
// make them look more complicated than
// they really are.
// Technically, since Min and Max are
// trapezoids with one side at infinity,
// a single function would suffice.
// But three functions are more efficient
// and comprehensible.
// Infinite to the left.
let inMin x0 x1 =
  let m = 1.0/(x0-x1)
  let b = 1.0-x0*m 
  (fun x ->  
     match x<=x0 with
     | true -> 1.0
     | _ -> 
     match x<=x1 with
     | true -> x*m+b
     | _ -> 0.0 )
// In the middle.
let inMid x0 x1 x2 x3 =
  let ml = 1.0/(x1-x0)
  let mh = 1.0/(x2-x3)
  let bl = 1.0-x1*ml
  let bh = 1.0-x2*mh
  (fun x -> 
     match x<x0 with
     | true -> 0.0
     | _ ->
     match x<x1 with
     | true -> x*ml+bl
     | _ ->
     match x<=x2 with
     | true -> 1.0
     | _ ->
     match x<=x3 with
     | true -> x*mh+bh
     | _ -> 0.0 )
// Infinite to the right.
let inMax x0 x1 =
  let m = 1.0/(x1-x0)
  let b = 1.0-x1*m 
  (fun x ->  
     match x>=x1 with
     | true -> 1.0
     | _ -> 
     match x>=x0 with
     | true -> x*m+b
     | _ -> 0.0 )
// The output function is a symmetric triangle.
// This function produces the area and centroid.
let outSym xc dx h = 
// Fire one rule.
let fire x (inSet:InFunc,outSet:OutFunc) =
  x |> inSet |> outSet
// Fire and defuzzify a ruleset.
let fireAll sets x = (fire x) sets 
  |> List.fold (fun (aa,cc)(a,c)->(aa+a,cc+a*c)) (0.0,0.0)
  |> (fun (aa,cc)->cc/aa)
// Here's the now familiar tomato problem.
// By happy coincidence, all the input sets 
// can be coded as trapezoids and the output
// sets as symmetric triangles.
let tiny   = inMin 1.0 2.0 
let small  = inMid 1.0 2.0 2.0 3.0
let medium = inMid 2.0 3.0 3.0 4.0
let large  = inMax 3.0 5.0
let cheap      = outSym 1.00 0.50
let moderate   = outSym 1.50 0.50
let expensive  = outSym 2.00 0.50
let outrageous = outSym 4.00 2.00
let rules =
// Inspection will show that the results
// are identical to the "tzoid" version.
for size in 0.25..0.25..5.00 do
  printfn "%f, %f" size (fireAll rules size)
printf "Your breakpoint here."

1 comment:

Nhivekar said...

How i can write defuzzification in C-language?