Monday, December 29, 2008

Fuzzy Logic

We all have our little pet methods that we like to use. I for instance will try to use microprocessors (specifically Atmel or PIC) to solve a problem I encounter. You may use FPGAs or CPLDs. Some crazy people will use .NET and embedded WinCE or somesuch. Everyone has different tools and methods that they are familiar and comfortable with.

One of the tools that I use to solve problems is fuzzy logic. I want to say it's not very well known, at least, I don't get many appreciative nods when I mention it to colleagues. I plan to talk about it as a solution to various problems so it will be useful for you listening (Hello? Anyone out there yet?) if I were to explain it and its use.

Where to start? It might be best to start mathematically. In a mathy sense, fuzzy logic is a method to map m-dimensional input space to n-dimensional output space in a continuous nonlinear fashion. The output may or may not be 'smooth' (ie, differentiable at all valid points in both directions), but my gut feeling is that it is. Don't ask me to prove it, I won't. I'm sure it's proved in some paper somewhere. If math is really your thing then I'm sure this will matter to you, so by all means, look it up.

So what does that mean? Fuzzy logic is basically a function. It can take any number of inputs and produce any number of outputs. The output can depend on one or many of the input variables. So if we have a fuzzy logic function that takes two inputs and produce two outputs: [a,b]=fuzzy(c,d) The inputs and outputs are usually limited to a certain range (If you're mathy, it's called input space and output space. Non-mathy types: you too can feel important and smart by saying things like My fuzzy logic function maps a three-dimensional input space to a two-dimensional output space. And I always drink my tea with my pinky sticking out - I'm distinguished that way.). An input may be limited to values from 0 to 20, and for values outside that range you'd either cut it off to the limit value (ie, 0 or 20 depending on where you go outside the range) or extrapolate somehow. I generally choose to cut the values off. Outputs are also limited as a result of the limitations to the input - since the input space is limited so is the output space.

Now there are all kinds of multi-dimensional nonlinear functions. Usually they're defined something like this:


x varies from 0 to infinity
y varies from 0 to infinity

for x=0 and y=0, z=0
for x>0 and y=0, z=0
for x>0 and y>0, z=x*y

This scheme covers all values, is nonlinear, and if you're careful enough in the definition produces a continuous function. The beauty of fuzzy logic isn't the fact that it IS a nonlinear mapping of multi-dimensional input space to multi-dimensional output space (say THAT five times fast!), but the HOW of how it accomplishes that mapping.

This is where the 'fuzzy' part of fuzzy logic comes in. In the above example we have some logic and it's very precise. Inputs have precise values, EXACT values even. And we have logic: If x IS 1 AND y IS 1 THEN z IS 1. What if I don't want to be so exact? What if I want to say IF x is BIG and y is SMALL THEN z IS MEDIUM?

You might be asking yourself 'Why would I want to create a function to express such a concept?' If you're starting off from a mathy 'multi-dimensional input space' type of position then you probably don't see the need for such a statement, or a means to evaluate it. If you're mathy then you like numbers and variables and ranges - oh my! But if you're an actual person (the jury is still out on whether mathy 'people' are actually human) then fuzzy logic is for you. Take the example of tipping at a restaurant.

At a restaurant you usually have to give a tip which is some percentage of your total bill. I evaluate this percentage based on the level of service I receive and the quality of the food. We'll score them both based on a ten-point scale with 0 being the worst, 10 the best. I will generally tip between 0 and 33% of a bill. Let's functionize that:

0 < Tip% < .33
0 < Food < 10
0 < Service < 10

Tip% = f(Service,Food)

Ok, so how much should I tip? Fuzzy logic has the answer.

The first step in fuzzy logic is to 'fuzzify' the inputs. We do this with what are called 'input membership functions'. That's just a mathy way of expressing a concept like: '0 is definitely (100%) awful service while 2.5 is definitely not (0%). All values in between that vary linearly'. If you graph it, that would be a triangle with your peak at the 'definitely' point and then a straight line drawn to your 'definitely not point/points' Since 'awful service' was at the low end of our range for service it only has one 'definitely not' point. For 'OK' service we might place the peak at 5 and the low points at 10 and 0. It will be a triangle that spans the whole range with its peak at 5.

For both Service and Food we'll define 'Awful','OK', and 'Great' levels. Awful peaks at 0 and bottoms out at 5, OK peaks at 5 and bottoms out at 0 and 10, and Great peaks at 10 and bottoms out at 5. Now for any numeric input value from 0 to 10 we can describe how accurately the service is 'Awful', 'OK', and 'Great'. For instance:

Service = 5
0 = Awful(Service) %The service is not at all Awful
1 = OK(Service) %The service is definitely OK
0 = Great(Service) %The service is not at all Great

Service = 7.5
0 = Awful(Service) %The service is not at all awful
.5 = OK(Service) %The service is somewhat OK
.5 = Great(Service)%The service is somewhat Great

It is worth noting that these membership functions don't have to look like triangles - they can look like squares or gaussian functions or trapezoids. The complexity of the calculations to determine value of the membership function increases, but not the general idea.

Now that we know to what extent the level of Service or Food matches our descriptions (Awful,OK,Great), we can create the output with rules. This requires output membership functions. These work pretty much like the input membership functions but in reverse. Each output membership function has an output number associated with it as well as the degree to which it is asserted. For tipping I'll say that the tip is 'Small' if it's 0%, it's 'Normal' if it's 16.5% and it's 'Big' if it's 33%. These membership functions also have shapes associated with them but for an expedited example it only matters where their nominal output values (or center points if you're thinking with shapes) are on the output axis. The output number is determined by doing a weighted sum of each nominal output value times the degree to which it is asserted. Thus we can say that the tip should be 33% Low, 50% Normal and 75% Big, and if we do a weighted sum we get:

0*.33+16.5*.5+.75*33 = ~8.5% tip (roughly)

So once we know how much each output membership function is 'asserted' we can tell how much we should tip. How do we tell how much each output membership function is asserted?

That's where rules come in. To determine the level of assertion we make rules that read like:


You'd probably make a lot of these rules for a tipping system, and depending on how much you value food versus service your rules would be different than everyone elses. So in the above example if the degree to which the Service is Good is .5, and the degree to which Food is Good, how do we evaluate the AND? There are several ways. You can multiply the two .5's and get .25 for the level of the tip being Normal or we could choose the maximum of the two values. There are other ways, but it has to make some sense. You can also have OR's as logical operations (the OR operation is usually a minimum of the two) and NOT (usually 1-value). How the operations are evaluated changes based on the type of system you are putting together, so don't be too shy about the 'right' way. My AND's are usually the product and my OR's are usually minimum.

So using these operations you assign some weight to each output (Normal, Big, Low). As seen above, multiple rules produce weight for Normal. When this happens, you either add all of the weights together or select the highest. When you've gone through each rule you'll have a weight for each output:

Low = 0
Normal = .5
High = .5

Then you go back two steps above and perform the weighted average of the output values. In this case you'd get:

0*0+.5*16.5+.5*33 = 24.75% tip

That must have been some good service (or maybe food)!

So, if you've followed me this far, you can see that fuzzy logic excels at creating nonlinear multidimensional functions in a way that humans can relate to (ie, in a way that matches our decision-making process). It produces real number outputs from real-number inputs, and it has a firm mathematical basis (that you can look up if you want, I'm satisfied that it works). I hope you can see all of the potential uses for this, because my hands are getting tired from typing so I'm signing off. Tune in later for some practical controls-related uses of fuzzy logic.

1 comment:

Will Dwinnell said...

I like your introduction to fuzzy logic. It's been my observation that fuzzy logic is often good at establishing a policy which is part of a larger solution, as opposed to generating the system output directly.

"Fuzzy decision system for threshold selection to cluster cauliflower plant blobs from field visual images", by L. García-Pérez, M. C. García-Alegre is an excellent example. In short, that solution iteratively increments or decrements a global threshold for image segmentation, with the fuzzy logic component deciding whether to increment or decrement the threshold, based on thresholded image statistics.