A Logic that Urinates

It is said, in North Korea, children are taught that their loving ex-leader Kim Jong Il did not even have to urinate because he was so pure. No excrement generated in his body due to his super-human purity. As a software engineer I think that most of our code behaves also like Kim Jong Il. Our code is ultra pure so that it surpasses every contingency in general human discourse occurring due to imprecision and vagueness. For instance, the statement start_time = 3 in a computer program literally means it while in human conversation “The event starts at 3” does not imply a rigid spontaneity. In a statement like the later, we humans implicitly agree that the start time can fall within an acceptable time window centered around 3. In any society, a deviation of few seconds will be accepted. However, the program would not accept 3.0001 or 2.998. This behavior with programs generally works. If you are developing accounting software, you probably don’t want to jeopardize your program logic with vagueness in human thinking. In fact lot of practices are involved in software delivery (such as manual testing, unit testing and code quality analysis) to cut the crap introduced by humanness and make the software as pure as Kim Jong Il. However, there are cases that a programmer is left with no other option but to stretch boundaries of his thinking a little further than the psychotic notion of purity and to get along with the real world while encountering its inevitable vagueness. Following is an example from a recent programming experience of mine.

Recently we implemented an iPad navigation app for a leading Norwegian GIS (Geographic Information Systems) company. The app is intended to help people when going on boat rides by providing specialized maps. In addition to this main purpose it is bundled with lot of other useful features such as path tracking, geo-fencing, geo-coding, social media sharing, etc. Not surprisingly the app needs to determine user’s current location to enable most of its features. For this, we employed location services API that ships with iOS. It uses various sources such as GPS, access tower data and crowd-sourced location data when determining the geo-coordinates of the device location. Each of these location sources has different implications on accuracy and battery consumption. For instance, GPS is by far the most accurate method, but drains the battery faster. On the other hand, wifi iPads that amount to a significant fraction of the iPads that are currently in use, do not have GPS receivers. The only accessible location information for them comes from crowd sourced location data from wifi hot spots that agree to share their location. Inevitably these location coordinates are less reliable. One nice thing with iOS location API is that, along with every location coordinate it also provides information on how accurate (or how inaccurate) the reading can be. This is called the tolerance value. For example, when we see a location coordinate (in the form latitude – longitude) 35.45^o, 4.87^o with tolerance 20 meters, we know that the user’s actual location can be anywhere inside a circle of radius 20 meters centered at the point (35.45^o, 4.87^o). With our experiments we figured out that when GPS is used to determine the location, tolerance level is as low as 5 meters. However, with wifi iPads, the best we observed was 65 meters. To make things more complicated, even the iPads with GPS receivers, at times, can go low down in accuracy (with tolerance levels as high as several hundreds of meters). This particularly happens when the device is in the vicinity of objects like huge concrete structures or large trees that effectively blocks GPS signals.

Need to determine location accuracy mode

Experimentation clearly suggested that there are two disparate modes that an iPad can be operating at a given moment with respect to location detection; high accuracy mode and low accuracy mode. These two modes are characterized by the following behaviors.

High Accuracy Mode (HAM)	Low Accuracy Mode (LAM)
Tolerance value is low for most location readings	Tolerance value is high for most readings
Location readings are received in regular intervals (can be as frequent as once in a second)	Location readings are received less frequently (usually only few times in a minute)

When in high accuracy mode we can treat received location coordinates as the actual location. In addition we can happily ignore intermittent low accuracy readings (readings with high tolerance values – these can occur even in high accuracy mode occasionally). In contrast, the programmer has to make every attempt to use all acceptable readings (readings without crazily high tolerance, such as more than 1 km) when in low accuracy mode since only few location readings are typically received during 1 minute. Also, corrections may need to be applied (depending on the purpose) since the accuracy level is low. Because the developer has to apply two kinds of logics depending on the accuracy mode, it’s necessary to determine the mode that the device is operating at a given moment. One should also note that the mode could change with time; for instance, when a person is moving with a GPS iPad, the device can be operating in high accuracy mode mostly, but can also switch to low accuracy mode when it is close to a big building.

Difficulty in drawing the line between two modes

The first (and probably the toughest) challenge is to correctly figure out whether the device is operating in HAM or LAM. It doesn’t take much thinking to identify that one can use both tolerance value and location reading frequency to determine the mode. If most tolerance values are low and the device is receiving location readings in regular intervals, it should be in high accuracy mode. However, formulating the logic is not as simple as it sounds because it needs explicit manifestation of numeric boundaries between the two modes. For example, let’s say that we decide to conclude the operating mode as HAM when the best tolerance is less than 20 meters and 15 readings or more are received within a period of 30 seconds. It’s not difficult to illustrate the problem associated with this approach. Consider the following 3 cases.

Case 1: Best tolerance is 18 meters and 15 readings are received within 30 seconds.

Case 2: Best tolerance is 21 meters and 15 readings are received within 30 seconds.

Case 3: Best tolerance is 18 meters and 13 readings are received within 30 seconds.

Intuition suggests that most probably the device should have been operating in the same mode in all 3 cases. However, our previous logic with stubborn numeric boundaries results in case 1 being identified as high accuracy mode, while the other two being recognized as low accuracy. Can you see the problem here? The problem is not about using numeric boundaries (we have to do that as long as we program for a Von Neumann computer). However, the problem lies in selection of the numeric boundary. What justifies selection of 20 meters as the tolerance boundary? Similarly, how confident are we, that the frequency boundary should be 15? A sufficient probe into the problem would reveal that it’s almost impossible to develop a sound heuristic that determines these boundary values “accurately”.

Where exactly is the problem?

The problem really lies on the discrepancy between skills of humans and computers. Humans are clever in dealing with concepts than with numbers while computers are better in handling numbers. This is evident in that we could distinguish between the two modes easily when we were talking in terms of concepts (to reiterate our previous statement -> ‘If most tolerance values are low and the device is receiving location readings in regular intervals, it should be in high accuracy mode’). The moment we try to put this logic in terms of numbers, we run into chaos. This is a clear case where ‘pure logic’ leaves us in a desperate abyss. 

Fuzzy logic brings in a solution

The brilliant intellectual Lotfi Zadeh introduced Fuzzy Logic in 1973, which constitutes a beautiful solution to problems like the one articulated above. Fuzzy Logic, in its core, builds a sophisticated mathematical framework that can translate semantics expressed in vague human terms into crisp numeric form. This enables us, humans, to express our knowledge in a particular domain using a language familiar to us, but still make that knowledge solve concrete numeric problems. For example, our knowledge can be expressed like the following rules that are used to determine whether a candidate should be chosen for a job depending on his experience, education and salary expectation levels.

If Experience is High, Education level is Medium and Salary expectation is Low, then hire the guy.

If Experience is Medium, Education level is High and Salary expectation is High then do not hire the guy.

If Experience is High, Education level is Somewhat High and Salary Expectation is Very High then do not hire the guy.

Rules like above can be formed using our knowledge, experience, gut feeling, etc about the domain. The collection of rules is typically termed Fuzzy Rulebase. We feed the rulebase into a Fuzzy Logic System (FLS), which aggregates and stores this knowledge. Most notably, the FLS stores the knowledge in a numerical logic that can be processed by a computer. After that FLS is capable of answering questions like the following.

If the Experience level is 4 (out of 5), Education level is 3 and Salary Expectation is 4, should we hire the guy?

No need to mention that, the richer the rulebase is, the more accurate is the outcome.

A Little further insight into Fuzzy Logic

How does Zadeh’s new logic perform its wonders under the hood? If fuzzy logic is a complex and amazing structure, the magic brick it is built by is the concept termed possibility. Zadeh’s genius is to identify that, in human discourse, likeliness does not refer to likelihood, but to membership. Let me exercise my teaching guts to describe this in a more digestible form. When we humans are confronted with a question like “How hot is 25^oC?” we do not think it like “What is the likelihood that 25^oC can be considered hot?” (Do we?). We rather think it like “Up to which degree does 25^oC belong to the notion ‘hot’?”. To put the same thing in different terms, it’s about “the degree of belongingness to something” but not ”the probability of being something”. You might now be thinking of giving up the idea of becoming Zadeh’s follower, but I suggest you to hold on and give it a second thought.

I believe that Zadeh touches the real nerve in the problem when he makes this distinction between likelihood and membership. After understanding this by heart it’s an easy ride into the rest of the theory. As the next step we can introduce a term for concepts like ‘hot’, ‘beautiful’ or ‘high’. Fuzzy logic calls them fuzzy sets. A fuzzy set is an association between a number and a possibility value (Possibility is a number between 0 and 1 – just like probability, but at the same time radically deviating from it conceptually). Following figures provide examples. First one defines the fuzzy set “LOW” when input values are given from 1 to 5. For instance, if an examiner evaluates a student’s proficiency in a subject with a number between 1 and 5, how much will each mark mean to be ‘LOW’? We know that 1 is absolutely low. Therefore we consider the possibility of mark 1 being in the fuzzy set ‘LOW’ as 1.0 (maximum possibility). Also we can agree that mark 5 cannot be considered ‘LOW’ at all. So its possibility of being ‘LOW’ is zero. Marks between these two have varying degrees of membership in the fuzzy set ‘LOW’. For example, if the examiner gives mark 4 we consider student’s proficiency to be ‘LOW’ only with a degree of 0.25. The fuzzy set ‘HIGH’ (last plot) is defined in a similar way. What about the middle one though? It’s not a fuzzy set that stands for a brand new concept, but one that stands for a modification of a previously defined concept. The modifier ‘VERY’ is applied to the concept ‘LOW’. Noting that the modifier is an intensifying modifier (one that further strengthens the concept) we square each possibility in ‘LOW’ to get possibilities in ‘VERY LOW’. Gut feeling says that membership of mark 4 in fuzzy set ‘VERY LOW’ should be less than its membership in ‘LOW’. And the numbers resemble that notion.
                         Possibility [4 is VERY LOW] = 0.25 * 0.25 = 0.0625

It’s not difficult to grasp the idea of fuzzy variables. They are fundamentally measurements or entities that can take fuzzy sets as their values. Example fuzzy variables can be temperature, student’s proficiency, candidate’s experience and so on. After that we can combine a fuzzy variable with a fuzzy set to construct a meaningful statement like “temperature is LOW”. These can be termed atomic statements. To express it formally, an atomic statement is of the form:
                                        <fuzzy variable> is <fuzzy set>

Now we walk the next step by combining several atomic statements into a compound statement. A compound statement would look something like “Student’s math proficiency is LOW, English proficiency is HIGH and music proficiency is MEDIUM”. These types of statements are useful when making judgments based on a combination of factors. For instance, a judge panel might want to make a final decision on whether to pass a student from the exam by looking at all his subject level proficiencies. Suppose that the judge panel decides this: “If there is a student whose math proficiency is MEDIUM, english proficiency is MORE OR LESS LOW and music proficiency is HIGH we will pass him”. This is termed a fuzzy rule. More appropriately, a fuzzy rule is a compound statement followed by an action. Another rule can be: “If the student’s math proficiency is VERY LOW, English proficiency is high and music proficiency is LOW we will fail him”. If the judge panel can compile a bunch of rules of this form it can be considered to be the policy when evaluating students. In fuzzy logic vocabulary we call it a fuzzy rulebase. It is important to note that a fuzzy rulebase need not be exhaustive (meaning that it does not have to cover all possible combinations of scenarios). It is sufficient to come up with a rulebase that covers the problem domain to  a satisfactory level. Once the rulebase is fed to a fuzzy logic system it is capable of answering questions such as “If the student’s math grade is 3 (in a scale of 1 to 5), English grade is 2 and music grade is 3, should we pass him?”. This is all one needs to understand to use a fuzzy logic library. Inner workings of the theory on how it really derives the answer based on rulebase are beyond the scope of a blog post. Also I think that 90% of readers would be happy to learn that the math bullshit is going to end from here.

Application of fuzzy logic into our location detection problem

Let me repeat our problem; we receive location coordinates in iPad with varying frequencies and tolerance levels. By looking at tolerance values and location coordinate frequency, we need to determine whether the device is in high accuracy or low accuracy location detection mode at a given time. We decided to determine the location detection mode every 30 seconds. At each 30 second boundary we used location coordinate values received within the last 30 seconds to determine the mode. All location related processing for the next 30 seconds are performed with respect to this newly figured out mode. For instance, if we decide that the device is operating in high accuracy location detection mode, we assume that the device operates in the same mode until we perform the evaluation after another 30 seconds. For this, we used following two parameters as inputs in the problem.

• Tolerance values for best two location coordinates (coordinates with lowest tolerance values) within past 30 seconds
• Number of location coordinate values received within past 30 seconds (highest possible value is 30 as we configure the device to receive location coordinates every second. However, when in low accuracy mode, number of coordinates received within 30 seconds is way less than 30).

We defined each of the 3 inputs to take values within a universe with 5 fuzzy sets: VERY LOW (VL), LOW (L), MEDIUM (M), HIGH (H) & VERY HIGH (VH). Then we worked out a bunch of fuzzy rules using these inputs and fuzzy sets. Rules are derived using gut feeling decisions on the domain. Following figure shows a part of the rulebase we constructed.

            

For instance, Rule No. 1 says that “If both best tolerance values are VERY HIGH and the reading count is LOW, decide location detection mode to be low accuracy mode. Rule No. 5 reads as “If the two best tolerance values are MEDIUM and VERY LOW while the reading count is MEDIUM, identify it as high accuracy mode, and so on.

At run time we determine numerical values of our 3 input parameters. An example input set can be:
                  tolerence1 = 10 meters, tolerence2 = 25 meters, reading count = 20

Using the rulebase, fuzzy logic system is capable of deriving an answer to the question “Which location detection mode the device is currently operating in?”. Our experimental results were exciting. With the aid of fuzzy logic we arrived at a sensible solution that provides accurate results to a problem that is almost unsolvable using conventional crisp logic. Our app is now in AppStore as the most popular navigation app in Norwegian market.