In this post we talk about the fuzzy logic algorithm that is used reputation systems. At Verify, we’re building a reputation protocol on the Ethereum blockchain and are sharing these posts in an effort to share our knowledge with the wider crypto community.
We have introduced reputation in previous posts and we have also mentioned that one way to quantify trust is through fuzzy logic algorithm. So what is fuzzy logic anyway?
In binary logic we either have 1 or 0, True or False, Like or Dislike and many other forms of approval and denial. With Fuzzy logic we include what is between the 1 and the 0. For example, instead of saying this pizza is “tasty” or is “not tasty” we say this pizza is “somewhat tasty” instead of the flat tasty or not boolean. It gives you more room to classify your choice. Now, if you ask a bunch of people what they think of the taste. Some will say it was “delicious”, others would say somewhat tasty, and others will describe it differently some may even dare to say that it was “not delicious”. Fuzzy logic came to imitate that kind of response. So instead of computers responding with a binary response of a yes or no, they are able to decide things in between the yes and no.
Fuzzy logic at its core incorporates “If-Then” rules to derive a solution. It is most effective when experience is involved that is what the If-Then is there for. With it it is able to decide based on some experience. The word fuzzy may reflect negative sense however it is the contrary it has been proven very effective in various applications be it hardware or software.
An example of how a Fuzzy logic system may operate is say a throttle control unit in an autonomous plane; instead of you saying or using mathematical notations to control altitude you say if altitude is high then decrease throttle, if altitude is too low then increase throttle. It basically utilizes human-like behaviour, in which you use descriptive terms that are not necessarily precise.
How it Works
To understand how it works, let us try to compare it to something we are familiar with. At some point in our lives we’ve encountered the question that asks you to map items in left left column to items in the right column. Something like this:
You see we take the input which is the left column and map it to the column in the right. In between we ran some rules; for example the rule said Banana == Yellow and so on. Now with that in mind let us jump to fuzzy logic.
Before designing we need to understand what we are trying to control, and what data inputs we have that allows us to measure that control? Answering that will allows us to define the linguistic values for the system. Let us dive directly into a complete example and learn the concepts as we solve for the fuzzy system.
Let us take the example of an autonomous plane flying at an optimal altitude (Ao); we have a control unit to either increase throttle or decrease throttle to stay at this optimal altitude (without using other control surfaces), basically a cruise control system. So as an answer to previous two questions we are trying to control throttle based on altitude.
Now that we have answered the two most important questions, other things will fall in place.
Say our sensor gives us a reading (Ar) of the current altitude. We take that reading and subtract it from the optimal reading. Ar — Ao = Error. Error is called the reading error. In our case it is the altitude error.
Now assume we also obtain the rate of change in Altitude. It is basically rate of change of error. This rate of change is called error-dot.
At this point we have defined what is called the inputs, we need to set the outputs as well. So working with the altitude. Let us define the outputs as:
Increase throttle , No Change and Decrease Throttle; falling in the ranges of 100 km/h and -100kmh.
Now that we have defined our inputs and outputs we need to add what is called membership functions, which is basically setting labels for events to each of the inputs and outputs. I.e:
For the Altitude error we have three main cases (membership functions) where:
- Current reading is less than optimal reading Ar < Ao, this case the Error would
Negative - Current reading equals the optimal reading Ar = Ao, this case the Error would be
Zero - Current reading is larger than optimal reading Ar > Ao, this case the Error
would be Positive
We will do the same for the error dot. We also have three main cases (membership functions) where:
- If the change in error is decreasing = Negative
- If the change in error is not change = Zero
- If the change in error is increasing = Positive
Will have to do the same for the output. We have three main membership functions
- Increase throttle
- (No change)
- Decrease throttle.
Now we will map them together and set our IF-THEN rules, for example:
- If Error is Negative (Ar < Ao) and Error-dot is Negative THEN Increase throttle.
- If Error is Zero (Ar = Ao) and Error-dot is Zero THEN No Change.
- If Error is Negative (Ar < Ao) and Error-dot is Zero THEN Increase throttle.
And so on. It is best to use a matrix to make things even clearer. Let us label Negative as N, Zero as Z and Positive as P. “Increase throttle” as ID,”-“ as no change and “Decrease throttle” as DT
We can see all of membership functions and the outputs in one block. The columns represent the Error and the rows represent Error-dot. So for example the cell in the middle has a “-” which means no change. So if Error was Zero (Z) and Error-dot was also Zero (0) then no change (-) to happen to the throttle.
Membership functions have magnitudes ranging between 0–1, which also can be represented as 0–100%. Think of magnitudes as weights. Usually it is represented in a graph. The graphs for the membership function sets (error, error-dot and output) looks like:
And for the output we get:
Assuming we got Altitude-error of -1 degrees and the change rate of 2.5 degrees.
We track path in graph per input. For altitude error:
If we follow the line from -1 upwards we reach an intersection where both Zero line as well as Negative line (keep in mind we will always go upwards to reach the last line on top. Meaning if say error was -1.5 in case the first line we will encounter is the Zero (dark blue) which will map to around 25, we keep going upwards we will encounter the negative line (green) which will map to about 75).For our example both line we intersected at 50. That tell us that degree of membership for the negative set is 50 and for the zero set is 50 (or 0.5)
Now we consult the matrix we established earlier and highlight the rules where input I (Altitude error) is either negative or zero as:
The above matrix shows that for Input I (Altitude error) we only got values for the Negative (N) and Zero (Z) columns. We have seen in the graph that the value for both Negative and Zero columns is 50. For the Positive (P) column the value is 0s.
Now for the second input where error-dot was +2.5 degrees. Before we proceed we will treat the magnitude of 0–100 as 0–1; so for the first input (Altitude error) we got 50 for both negative and zero, we will treat that as 0.5.
We will do what we did with Altitude error and first get the degree of membership (also called magnitude, percentage, ...etc)
Similarly we obtain 0.5 for the error-dot of +2.5. Now we highlight corresponding matrix rules. For the second input (rows) we get the second and third row:
In the the above matrix we can see that we only got values for Zero (Z) and Positive (P) and it is 0.5. The Negative row (N) would be all 0s.
Now we need a way to combine the rules into something meaningful. We start by overlaying both the Attitude error and error-dot results we obtained using the logical AND. Don’t be alarmed, it is a simple process.
In the matrix we obtained we highlighted the concerning cells or rules; we colored the Altitude error output in orange and error-dot in violet. We will implement the AND operator on Input I (Altitude-error) and Input II (error-dot).
Recall from the matrices that for Input I we only had the Negative and Zero which was 0.5, the Positive was 0.
For Input II we only had the Zero and the Positive which was 0.5 for both. Negative was 0.
By overlaying the regions performing the logical AND operator we get:
When Input I is Negative we got the value 0.5
For Input II Negative was 0.
So 0.5 AND 0.0 = 0.0
Input I is Zero = 0.5
Input II is Negative = 0.
So 0.5 AND 0.0 = 0.0
0.0 AND 0.0 = 0.0
0.5 AND 0.5 = 0.5
0.5 AND 0.5 = 0.5
0.0 AND 0.5 = 0.0
0.5 AND 0.5 = 0.5
0.5 AND 0.5 = 0.5
0.0 AND 0.5 = 0.0
We will assign the green color to where we got an answer > 0.
The green colored 2X2 matrix of rules would have magnitudes; this means we are left with decrease throttle (DT) and No Change (-) outputs. We will combine them to produce a single output (this process is called defuzzification).
The way defuzzification works is by using several methods. One of which is called the root-sum-squared. Root-sum-squared considers the weight of each rule. Which is a great approach if weights are important in your systems.
So far the rules that were not equal to 0 fell under the Negative and Zero
We need to calculate the strength of each output membership function, Decrease Throttle, No Change and Increase Throttle.
Decrease Throttle strength= SQRT(Rule 1² + Rule 4² + Rule 7² + Rule 8²)
= SQRT(0.00² + 0.50² + 0.50² + 0.50²) =
No Change strength= SQRT(Rule 5²)
= SQRT(0.50²)=
Increase Throttle strength= SQRT(Rule 2² + Rule 3² + Rule 6² + Rule 9²)
= SQRT(0.00² + 0.00² + 0.00² + 0.00²) =
Now that we have the strength of each output we multiply it by its center and we sum them together. The sum will be divided by total output strengths
Numerator= (decrease_throttle_center * decrease_throttle_strength + no_change_center * no_change_strength + increase_throttle_center * increase_throttle_strength)
Denominator(total output strengths) = (decrease_throttle_strength + no_change_strength+ increase_throttle_strength)
We have the strength so let us calculate its sum per equation above:
Denominator(total output strengths) = (0.866 + 0.500 + 0.000)= 1.366
Now let us calculate the Numerator; We need the centers of each output multiplied by its strength. Recall the graph where we drew our outputs and their ranges?
The center of the No Change output is 0, the center of Decrease throttle is -50 and the center of increase throttle is +50. So putting those numbers in the equation:
Numerator = (decrease_throttle_center * decrease_throttle_strength +
no_change_center * no_change_strength + increase_throttle_center *
increase_throttle_strength)
we get:
-50 * 0.866 + 0 * 0.500 + 50 * 0.000 = -43.3
The graph reflects the strengths of both the Decrease throttle (0.866 ~0.87) and No change outputs (0.5). The result of defuzzification is -32. So in layman’s terms, the plane was at -1 difference from optimal altitude and with change of +2.5 meaning it is inclining to get it back to optimal altitude the cruise control will decrease throttle 32%
One domain where fuzzy logic comes in handy is reputation systems. It can be used to decide whether a user is trusted or somewhat trusted or not to be trusted at all. Multiple systems could be utilized at once. For example one fuzzy system that takes in different data of a transaction:say the amount, the date the quality and shipping details and accordingly decide on a score for that single transaction. This would be fed to another system than in turn aggregates previous transactions and the time of last transaction to decide on a final output.
Verify.as
Verify is a Reputation Protocol for buying and selling things using
cryptocurrencies → https://verify.as/