sharadsinha

Archive for the ‘Mathematics’ Category

Chasing Numbers

In Education, Engineering Principles, Mathematics, Research and Development on September 28, 2014 at 8:35 PM

In his book The Tyranny of Numbers: Mismeasurement and MisruleNicholas Eberstadt says, “Although he may not always recognize his bondage, modern man lives under a tyranny of numbers.” Other writers have also commented on how and why numbers alone cannot make us happy and how numbers can be both enlightening as well as confusing if not presented with the right kind of background information. This is very true with research literature, specially those pertaining to engineering and science disciplines where measurement plays a very important role in conveying one’s ideas to convince someone of their importance. I see this everyday when I read research papers. Sometimes I even see numbers and graphs which seemingly do not have any major relation to the central idea of the paper. Such numbers, graphs and tables are byproducts of primary measurement but are probably included with the hope that more numbers, graphs etc. make the papers not only look good but also appear convincing. Given the very short amount of time that most reviewers spend on a paper, it is only sometimes that one finds reviewers commenting on the unnecessary usage of such secondary artifacts. However, a cursory glance does make the paper look good and does give the impression that the authors have spent time analyzing their results (though this may not be the case).

When I see such papers I am reminded of Eberstadt’s statement. It makes me wonder if engineering and science people read papers and books from the field of social science or history or say English literature. Research is conducted even in these disciplines and data is also collected and analysed where needed. However, the force of the argument generally comes from rigorous analysis and reasoning. It is not always driven by the logic that since this paper achieves number X compared to number Y (where say Y is less than X), the proposed methodology is better than the one related to number Y. I have read Diffusion of Innovation by Everett M. Rogers and I have found it to be immensely enlightening. It not only uses numbers but also the force of reasoning. This is so strong that you begin to see what the author is trying to say. I wonder how, say a computer engineering scientist would review a sociology research paper.

Have you ever tried reviewing a paper or a book outside of your major discipline and trying to understand its logical progression?

Advertisements

The Curious Case of Algorithms

In Education, Interdisciplinary Science, Mathematics on October 31, 2013 at 2:40 PM

I finished reading “The Golden Ticket: P, NP and The Search for The Impossible” some time back. It is a very nice book that introduces one to complexity theory. Essentially, it describes, without too much of Mathematics, what kinds of problems can be solved and what other kinds will take forever to solve. However, if these – the forever to solve ones– were to get solved one day, what would be the impact. P  refers to the problems that can be solved quickly using computers to get the best solution. On the other hand NP refers to problems whose best solution cannot be found quickly using computers. I have deliberately simplified things for your understanding. This field is vastly complex!

The word “quickly” is used here with reference to a time span which is acceptable to the seeker of the solution. It could be a few seconds, or a few weeks.  Going by the nature of humans, any solution (best or otherwise) that might be delivered in months or years will probably be unacceptable. The search of any solution is accomplished using algorithms. It is these algorithms that can either give us a solution “quickly” or might take ages to finish their task. It is believed that if we could find algorithms that could solve any problem in the class of NP problemswe could solve many challenges facing us. These problems can be found in varied fields like biology, cancer research, mathematics, computer science, economics etc. However, some of the modern day systems which we feel very secure and safe about will lose these strengths if an NP problem is solved. This is because they rely on the fact that NP problems are extremely hard to solve quickly. For instance, your secure online bank transaction won’t be secure anymore. The public-key cryptography, on which it relies, would be broken by then.

Another technologically interesting aspect of algorithms is their ability to provide information based on someone’s taste in color, clothes, books, music etc. In fact, it is this type of algorithms which is used by eBay, Amazon etc. to recommend to users items for purchase. They track their actions: which items they click on, which items they buy etc. to create an “algorithmic profile” of users. While all this sounds interesting and potentially time saving for someone who knows what to buy, this also has a negative side effect. As a regular user of such platforms, you end up getting information that is tailored to your existing taste. Therefore, you cannot easily get information that is not relevant to your taste. Effectively, your ability to explore ( if you are also someone who likes to explore) becomes limited. Of course there are ways to overcome this, simplest of them being not to sign in when performing a search!! You can argue that many prefer automatic sign-ins to save time and the need to remember passwords. True, but then you have to decide whether you want to work/live like a frog in a well or like a whale exploring an ocean! 🙂

The World as a State Machine

In Design Methodologies, Education, Engineering Principles, Mathematics on April 29, 2013 at 9:46 PM

A state machine is basically a model of computation which helps one analyze the effects of input on a system. This system can remain in different states throughout its life cycle though in only one state at a time. It can transition from one state to another depending on some input. Every state machine has a start state and it progresses from there to other states eventually leading to an end state. Note that it is possible to reach the end state from any intermediate state as well as the start state. It depends on the system being modeled. Also, the output of each state may depend on the current state as well the inputs to that state.  Thus state machines model reactive systems i.e. systems which react. A good description of state machines can be found here. Note that the description there is related to finite state machines, which are so called because they have finite number of states. State machines are used in different fields of study not just electrical or computer engineering. They are used in biology, mathematics, linguistics etc. They also have different variants each trying to capture some additional parameters of a system which I would not go into. You can read about them at the link mentioned earlier.

I was wondering if the world can be modeled as a state machineI think that the world in fact is a state machine except that its end state is unknown. Those with absolute faith in cosmological physics would state that the “Big Bang” can be considered as the start  state. Those with religious views might consider something else as the start state.  The beauty of this world being considered as a state machine lies in the fact that it does not matter whether you believe in science or not. It does not matter whether you have more of a religious bent of mind and would like to see the world from a religious or theological perspective or whether you want to see it only from a scientific standpoint. Either way, the world can be modeled as a state machine. You get to choose the start state depending on which viewpoint you are more comfortable with. In both the cases, the world is in fact a reactive system. It can even be considered as an aggregation of interacting state machines where each state machine can represent the economic, social, political, religious and scientific state of the world. And nobody would deny that all these concepts influence each other. Every electrical or computer engineering student studies about Moore and Mealy state machines. To them, the world is probably a Mealy state machine though not strictly so: the outputs in any state that this world resides in is dependent not only on the current inputs but also on the current state. If we look around us, it sounds so true,   does it not? However, this state machine is extremely complex!

What is optimization?

In Design Methodologies, Embedded Systems, Engineering Principles, Mathematics on April 15, 2013 at 12:04 AM

Perhaps optimization is the most abused word in all of research, engineering work or any task that seeks to maximize some intent. The Merriam-Webster dictionary defines it as “an act, process, or methodology of making something (as a design, system, or decision) as fully perfect, functional, or effective as possible; specifically : the mathematical procedures (as finding the maximum of a function) involved in this”. We can hear about optimizing power, area, a  performance metric like latency etc. Many people pass of every design decision as an optimization strategy. While such decisions may contribute to local optimization, they may fail in achieving global optimization. In fact such optimizations may actually degrade performance when the software or the design is used in a context which was not anticipated or thought of by the original developers. Read here about some insight into optimizing a memory allocator in C++.  You will find another debatable example of optimization to make software run faster here. And here is a nice article on efficiency versus intent. Typically optimization is associated with increasing the efficiency of a design (hardware or software) in some aspect. But such optimizations should not destroy the intent of the design. This requires a bit more analysis on part of the designer/developer to ensure that the intent is not lost. Here is another example.

The field of mathematical optimization, which is related to selecting the most appropriate choice (that satisfies a given set of criteria) from a set of alternatives, is vast and varied. There are numerous techniques suitable for different kinds of problems. You can see the list here. Frankly, it is a tough job to recommend one of these techniques for non-trivial problems. One needs to understand the nature of the problem in detail to make a just recommendation. Understanding the nature of such problems or modeling such problems in a way which is suitable for any of these techniques to be applicable is a non-trivial task. It requires a lot of theoretical and practical insight.

Relearning addition

In Design Methodologies, Education, Embedded Systems, Mathematics on March 22, 2013 at 7:13 PM

Alvin Toffler in his book “Future Shock” says that  “The illiterate of the 21st century will not be those who cannot read or write; they will be those who cannot learn, unlearn, and relearn“. Taking this quote a little out of context in which Alvin used it, I would say that the process of learning, unlearning and relearning basically embodies the principles of evolution and adaptation. And these are equally applicable to education. Are these emphasized enough in universities and schools? Can they be taught? May be yes, may be no. I will give one simple example here. Every electronics or computer engineer would have done some basic C programming. To add two numbers, A and B, one just needs to use the expression ‘A+B’. Does it always work? Not in the world of computers where one has to deal with overflows and underflows. And there is always a limit to the biggest number that a computer or a computing platform can support.

So, how are we going to add two arbitrarily sized positive integers. Examples of positive integers are 123456, 90913456 etc. I will use positive integers to illustrate ‘learn, unlearn and relearn’. The example can easily be extended to other data types. In C language, the integer data type can only support a maximum value of 2,147,483,647 when adding two numbers. So there is an overflow if sum exceeds this value and addition is not possible if either A or B is bigger than this value. To avoid this, one can use other data types supporting greater number of bits until one hits yet another ceiling. After a point, you hit the final ceiling. If the numbers are really so big, one way to deal with them is to go back to our old school days when we learned to add numbers: 2 digits at a time with a carry propagated. Yes, that is all you need to do! And this does not require in-depth of knowledge of various IEEE methods to represent numbers. It is simple and good old school method. Of course, the old school method may not have a very wide application, but it does help where possible and makes it clear that  the symbol for addition “+” (or the add operator as it is referred to in programming languages) should not make us forget how addition is done. We “learn” to add 2 digits at a time in school, then we learn to use the “+” operator in programming languages. Thereafter we have to unlearn this concept to relearn (or recall) the school method.  I have written a reference implementation in C which you can find here. You can also find its link under the software tools tab here.

What is there in the word “distance”?

In Education, Mathematics on February 6, 2013 at 9:32 PM

I fist learned about distances in school- class of classical geometry. Of course it was not called classical geometry in school but only geometry. The initial concepts were related to distances between points in a plane, between lines in a plane and between a line and a point in a plane. A plane, as you know, is a  2-dimensional (2D) space. In high school, this concept was extended to 3-dimensional space (3D). The concept of distance basically gives an idea of how far (or how close) are two things (lines, points) from (to) each other. What I learned was “2-norm distance” (the typical Euclidean distance):

2-norm distance = \sqrt{(\displaystyle\sum_{i=1}^{n} |{x_{i}}^2 - {y_{i}}^2|)}

I learned about Hamming Distance during my undergraduate courses on electronics communication. However, it is only during research that I learned a lot more about distances. My first surprise came when I heard about distances in a class on image processing. You can use distances to measure similarity between images! Of course the definitions and methods to calculate those distances were also different. Since then I have learned about distances being one major way of identifying similarities between objects or classes of objects. The central idea behind all these different kinds of distances (not just in image processing) remains the same: to measure  how far the objects are from each other in some respect. For instance, in psychoanalysis “Emotional Distance” is the degree of emotional detachment from some person or events; Czekanovski-Dice distance is used to compare two audio waveforms x and y in time domain etc. If your distance from the world of distances is not big ;), you might want to try reading the Dictionary of Distances.

Numerical Stability in Calculations

In Design Methodologies, Embedded Systems, Engineering Principles, Mathematics on January 24, 2013 at 11:44 PM

I did not have any course on algorithms in my undergraduate education. I studied about them (their properties, design etc.) during my research work. I now realize why their study is important for anyone who wants to be really good at designing algorithms or implementing them. After all, algorithms solve problems. I recently came across the subject of numerical stability of algorithms, numerical algorithms to be precise. While algorithms help solve problems, they need to be implemented on a digital machine (a computer for example) which has limited precision. Whatever number system we use, they cannot cover all the numbers present in exact  mathematics. This leads to approximations as well as upper and lower bounds on the numbers that can be represented. Also, approximations can be the source of errors and deviations from the exact numerical answer. For instance, on a machine with only 3 digit precision, numbers like 22, 2.22, 0.110, 100, 177 can be represented. Now if you try to add 2 and 1000 instances of 0.11 , your sum would be 112 on this machine and this matches with the exact answer. Similarly, if you try to add 9 and 9 instances of 0.11, the answer on this machine would be 9.99, which matches with the exact answer. However, if you try to add 10 and 9 instances of 0.11 in that order i.e 10+0.11+0.11…., the machine would return 10 as answer because the moment you try to add 0.11 to 10, you are going to exceed the precision of the machine. Now imagine doing the same calculation in the reverse order i.e adding all the nine 0.11’s first and then 10 i.e. 0.11+0.11+….+10, the machine would return an answer of 0.99 which is far off from the actual answer 10.99 and far worse than the previous approximation of 10 (for the other order of addition). This means that the way you arrange your numbers( in memory, for instance an array) to be added also may influence the sum!! I wish that embedded systems engineers read more on this subject so that the numerical errors that we see cropping up in such systems get reduced. A nice introduction is at wikipedia.

A Case of Two Means:Geometric & Arithmetic

In Engineering Principles, Mathematics on November 7, 2012 at 11:55 PM

Why is this post there? I have come across several examples of quoting results (numbers) in papers, reports etc. where the authors have used arithmetic mean. For instance, people would run an application on different computing platforms and then calculate the time taken on each platform. They would present their results in a table and the last column would have an entry titled “mean”. Often, it is the arithmetic mean (AM) that is quoted. How many times have you seen the geometric mean (GM) being quoted? Not many. The primary reason being that we are too comfortable with the arithmetic mean. This is what pops up in our heads generally when we think of a mean. But we forget in the process if AM is the right choice. It is important to understand when to use AM and GM . AM is biased towards large data points in a data set while that is not the case with GM. GM is generally used when several quantities multiply together to produce a result while AM is generally used when they add up to produce a result. Sometimes it is obvious when they add up and when they multiply. Sometimes,it is not so obvious. So you have to put extra effort in finding out which mean to use  and what message you are trying to drive home through that mean value. In the example cited in the beginning, GM should be used. Some nice references to read are : ref1, ref2, ref3, ref4. Similary, understanding when to use Harmonic Mean (HM) is also important. Whichever mean you choose,you have to understand your data points as well as be clear about the message you are trying to convey. Means and averages are very important in economics, mathematical finance etc.