The Transformed View - Part I

During my travel during the last few days, a lot of discussions happened about the KTU and its impact on the technical education. Many people from the teaching community feel that it is a ill-planned set up and exists only in news and hype. Let us not build a discussion here, but take some useful positives from the idea of unifying the local universities.

Many philosophers agree to the fact that the universe exists on a absolute "truth" and everything that we deal with are just its manifestation. Even the partitions that we build on religion, science, arts or any such streams actually are the same. In a united approach we see them as one. The learning in one stream does not in any way contradict the other.

Imagine you are in front of a white board and are gazing at it. Now you look the same screen with a yellow glass. The entire screen now becomes yellow. In reality the screen has remained white, and only the glass had made a difference. So are the different things that happen around us. Let us take this discussion to the subject of signal processing. Most of us are familiar with the natural time domain for the electrical signal. We are also aware that the power line signal that provides electricity has a sinusoidal fundamental frequency. We express the same thing here in different viewpoint. One viewpoint is the time and the other is the frequency. Nature imposes duality in the time-frequency, which brings about a conflict. Engineering solutions are nothing but a compromise on this duality. We shall build some interesting compromises in part II of this post.

Dynamic Programming Decision Making

All of us set certain goals and try to achieve them. What is the best way to keep track if you have taken the right decision?  Here is a quick method to keep track of your progress. Consider that you set a goal today, and you are trying to optimize all the actions in order to reduce the total cost. The cost here can be due to time, money, effort, social costs and others.

The idea is to incorporate a method to reach the optimum in a step by step manner that uses only the local information. We query that : "If I assume that I am optimal in the future, what action needs to be taken today to ensure a global optimum". This leads us to the answer that, the best way is to determine the best that you can do today, with the assumption that from tomorrow we are going to be optimal. This seems to be very suited to our current practice also. While we drive a car we put the gear to the right speed, so that we can endure the local roads and the nearby traffic. The goal might be distant but we always have to act optimally to reach there.  While spending we ensure that the basic needs for today is met. The savings also are done accordingly. Take the simple game of tic-tac-toe, here we are trying to see the local information in the game and trying to win or in most situations stop the opponent from winning !

Courtesy : http://experimental.designforfun.com

This approach of dynamic policy is widely employed in control systems and  communication. There are two things that we consider in this optimization problem, one is the value or the cost that is incurred due to our decision (actions)  and the second is the policy that we have come up with. So remember at the beginning of each day try to see that you are going to be optimum for 'today', because tomorrow will "take care for itself".

[Topic Courtesy :  Introduction to Stochastic Optimization, IITB]

On Decisions and Learning (Part II)

In the previous post, we have seen how the space and time constraints can affect the decision  making.  In this part, we extend the model to one of practical interest. Such a model should be robust across space and time variations. In effect we cover up the space and time and replace them by agents/players who affect our decision process. To illustrate with an example we take the case of a boy in say, Brazil and a similar aged boy in India. It is more probable that the Brazilian boy latches himself to football and the Indian boy would choose cricket with higher probability.

                     

The agents here is a representation of the culture and tradition - hence depends on the space. There can be agents representing time as well. For instance the decision on taking an umbrella before leaving the home depends on whether it is the rainy season or not. Rain is the agent here and hence represents time. Thus agents are the physical representation of the time-space (real) parameters. Another aspect of agents is that, there are certain agents that aid to the decision with more weight than certain other. Now there are decisions taken in accordance with logic, past experience, and predictions. Each of them has a correspondence with time - present, past and the future.

The process of making the decision can be summed up as \( f : (A_1,A_2, \cdots, A_k) \rightarrow  \mathcal{D} \). Here \(A|_1^k\) are the agents to be considered while taking the decision and the set \(\mathcal{D}  = d_1,d_2, \cdots, d_n\) are the decision choices. This model lacks the past learning that has been accumulated over time. To explain the learning in decision making, we can take the example of the man going out while it is raining (Agent = Rain). The man does not take the umbrella, and gets wet (Decision : No Umbrella). The next time he goes out in the rain he is reminded by the fact that he has got wet (which assumes a cost). Now it is possible to assign a cost of for the decision taken over a action set. Assume that the decision maker has learnt the decision taken over a set of agents till time \(T\). Now the system is opened and the learned costs are considered while taking the decision.

On Decisions and Learning (Part I)

An inquisitive mind always seeks the answer to this question, is the thing that I decide right? Has the trained mind in me educated enough to reach the "right" decision.

Decision making is a ever happening process in the world around us. Decisions may be taken for important as well as less important topics. The rightness of a decision is always debatable and often has a subjective element. So how does one take a decision, what elements are included in the process, and how the decision affects others. The three questions here has a strong theory in statistics. Let us parse each of them and look it in detail.

How does one take a decision?

Decision is a selection of a particular choice, from the given set of available choices. A decision may be prompted by a situation, which is both depending on space and time. So, deriving cues from the situation, any decision should particularly abide by time and space. Let us see a little example. Identically aged people live in a city and a village. Both fell ill (almost in the same time), and was taken to a doctor. The doctor in the city gave medicines in the form of tablets, while the doctor in the village asked the man to collect some herbs from the garden and have them. One can tell that space is the prominent factor in this example. The doctors decision complies with the locally available medicines. One may also expect in a closer analysis, that the domain of the doctor also plays a significant role in decision making. For this discussion we can avoid this possibility.

Now consider another example where time is the decision driver. A boy injured his knee while playing in the evening . Seeing the bleeding his parents took him to the local clinic for first aid. Imagine the same situation happening in the night. At this time, the parents have no access to the clinic, so they prefer to give whatever first aid is at home and later take up to the doctor if required. Time (and to an extend space) played the crucial role in this example.

We try to introduce some modelling. Consider a situation and \(n\) possible choices. A particular choice has to be picked. If one were to derive ideas from the examples presented, the decision \(D(S,t)\) is a function of the location and the time. Generally, space and time functions are difficult to generalize. So we somehow, avoid these by introducing a probability matrix over the choice. The simplification seems good, but did we handle the reality efficiently? Not really isn't it! What we did was to look into the decisions taken by us in the past and presented a distribution over those choices. From the point of view of an analyzer, this seems to be good. While the model seems to blind the decision makers view? One way to handle this is to bring in some dependence of space-time. The model should be robust to analyze and useful for the decision maker.

I leave this at a point for the reader to ponder a little :

Image Courtesy : olivergearing.com

Most of us act more or less according to this Importance vs Urgency model (logical planner!). We have a set of priority and the decision scheduling is performed by the urgency or the time requirement. Seems to convince why certain events require, us to wait in patience.

Get Puzzled!

As a continuation we will consider two more puzzle which motivates one or more applications in our day to day life.

Puzzle #1: A school  math teacher wants to teach geometry to her class 8 students. She collects 2 hemisphere shells and a cuboid, such that the cuboid can be inscribed inside the shell. She also bought paints -red and blue. One hemisphere was painted red, while only 80% of the second shell could be finished with the red paint.. So she decided to paint the remaining by blue paint. The teacher put the cuboid inside the sphere, and sees that all vertices fall on the red colour (assume that the shell is semi-transparent). Will her observation be true irrespective of the way she had painted.

The video solution of the puzzle above : - 

Solution:  If we consider the two hemispherical shells as a sphere, we understand that 10% of the sphere is painted in blue. Let us now denote, the vertices of the cube as \(v1\), \(v2\), \(v3\), \(v4\), \(v5\), \(v6\), \(v7\)  and \(v8\). The chance that a given vertex is placed in the blue part of the sphere, is given by:

\[\mathbb{P}(\cup_i v_i \in Blue)  = 0.1 \times 8 = 0.8\]

Thus, the chance that all eight vertices fall on the red part of the sphere \(= 0.2\). This means that there is at least one way of arranging the vertices such that all will fall on the red paint. The assertion made by the teacher is right.

(Courtesy : NIT Lecture, IITB)

Another one from geometry

Puzzle #2: A statistician is interested in this particular geometrical issue to find a spectrum allotment. An equilateral triangle is inscribed in a circle. The altitude of the equilateral triangle is 3/2 r. Find the chance (probability) that a chord chosen at random will intersect with the interior of the equilateral triangle. 

Try to work this out using more than one method. Is the answer you get the same in all cases?

Solution: 

Method 1 :  Each chord of the circle is uniquely defined by its center. We can place the chord's center inside the equilateral triangle area, so that it always falls inside the interior of the triangle. Thus the chance of choosing a chord which is in the interior of the triangle is

\(\mathbb{P}(\text{chord} \in \Delta) = \frac{\text{Area of } \Delta}{\text{Area of Circle}} = \frac{3\sqrt{3}}{4 \pi}\)

Method 2 :  Another method to express the probability is as follows; Fix one of the end points of the chord at the vertex of the equilateral triangle.. The chords that can fall in the interior will fall in the angle range \(\frac{\pi}{3} \leq \theta \leq \frac{2 \pi}{3}\) . Thus the probability of the event of interest

\(\mathbb{P}(\text{chord} \in \Delta) =  \frac{\pi/3}{\pi} = \frac 13\)

Method 3 : The chord is defined by its distance from the center of the circle.Thus the chords with distance from the center less than \(r/2\) can be classified as the interior of  the triangle. Thus the chance that the chord chosen at random will fall in the interior of the triangle is given as:

\(\mathbb{P}(\text{chord} \in \Delta) = \frac{r/2}{r} = \frac 12 \)


Notice the three distinct answers we obtained. Can you think of a good reason to justify this.

If we look into the situation more clearly it is evident that the notion of uniformly random chord is not well defined. In that case all 3 methods are right . Unless a fixed notion(reference) has been foretold, there is no clear solution. Such class of problems (challenges!) are called ill-posed .

(Courtesy : Introduction to Probability Theory, IITB )

The Balancing Act

Lets us start with a puzzle somewhat common place. A shopkeeper gets a stock of dozen cricket balls out of which one is a cork ball (kookaburra) and the remaining are rubber balls.  He is asked not to touch balls with hands (as it has to be used for the match), but is given a "pan" balance which will show either equal, less than, or larger than for the weights on the pans.

Find the minimum number of uses of the balance to find out the heavy ball.

Hint: 1 >> Separate the balls

The extension to this puzzle is interesting, Let us say that we want to find the odd ball (which can be  heavy/light) from the lot of 12 cricket balls. 

Guess how?

The interesting fact is that the odd ball can be determined with its weight in three measures. The idea is very similar to the source coding - Huffman coding. We can form a coding tree and verify it easily.

Let Left pan be represented as L and right pan as R.

The stepwise solution is as follows,

1. Divide the 12 balls into groups of three.
2. Weight 2 groups (of three balls) --> 1st measure. There are three possibilities 
• L=R then discard both the group
• L>R , call case A
• L<R , call case B
3. (If case A or case B happened) In the cases L>R and L<R, replace the right set by any of the untouched group. --> 2nd measure Then, 
• L=R, then the balls removed from the right pan is the odd group and follows the case in the previous measure. (ie, if case A-- light, case B -- heavy)
• L!=R, the the case which happened in the previous measure follows(ie, if case A-- heavy, case B -- light)
4. From the odd group determined from 3, take any two balls and do the measure;  --> 3rd measure
• if L=R, the  odd ball is the unmeasured ball and follows the same weight as in point 3.
• if L!=R, then the odd ball is one which follows the case in point 3.

The reader now can try to generalize this for \(m\) measurements