Friday 16 September 2016

Information Theory, Khan Academy

Recently, I have been going through some interesting videos on information theory. I am posting the link here: Information Theory, Khan Academy, for the benefit of those who want to learn something new, fundamental and interesting. I will try to summarize what I understood from the lectures below.

1. Ancient Information Theory
It is interesting to note how humans started communicating with each other. Ancient humans used pictographs and ideograms engraved on rocks and in caves to share information. Later on, symbols and alphabets were devised for ease of communication.

With the passage of time, advanced communication technologies were developed. For instance, Greeks and Romans used torches, especially in battles, for quick long-distance communication. In the 17th century, shutter telegraphs were the norm. It could cover all the letters in English alphabet. With the help of a telescope, it was possible to send information across an incredible amount of distance. But still, these techniques were not sufficient for effective communication due to their low expressive powers and low speeds.

With the discovery of electricity, the information age had begun. The visual telegraphs were soon replaced by electrostatic telegraphs. It was possible to send large bits of information to long distances in short amounts of time.

2. Modern Information Theory
How fast can two parties communicate with each other? The limiting rate at which it is possible to send messages depends on symbol rate (baud) and difference. Symbol rate stands for the number of symbols which can be transferred per second. There is a fundamental limit on the distance between two pulses. Due to noise, a pulse may not be perfect. If two pulses are very close to each other, there is a very high chance for inter-pulse interference to occur between them. This makes it difficult for the receiver to decode the signal. The difference stands for the number of signaling events per symbol. Message space denotes the number of messages possible.

How is it possible to quantify information? A possible way solve this problem is by considering a scenario where the receiver asks a number of yes/no questions to the sender to receive information. Based on the minimum number of questions required to receive the complete message, it is possible to quantify information. This unit is called a binary digit or bit, in short. Mathematically, this is nothing but logarithm (to the base 2) of the size of the message space. For example, to pass the name of a book from the Bible, 6-7 bits are required. To pass the names of 2 books from the Bible, 12-14 bits are required.

Human communication is a mix of randomness and statistical dependencies. Claude Shannon uses a Markov model as the basis of how we can think about communication.  Given a message, a machine can be designed which generates a similar-looking text. As we progress from the zeroth-order approximation to first-order and second-order approximations, the similarity of the text generated by the machine with the message increases.

Entropy - Shannon gives a mathematical method to quantify information. He calls this quantity entropy H= -Σp. log2(p), where p is the probability of an outcome of the event. If all the outcomes are equally likely, then entropy is maximum. If there is some predictability in the outcomes, then entropy comes down. For example, a text with random words and letters will have higher Shannon's information than a text with "normal" letters. This seems counter-intuitive at first because information theory doesn't deal with the semantic information in the message but with the number of symbols required to communicate a message. The only way to regenerate the random text is to copy the text as is. However, it is possible to compress the "normal" test using rules due to its predictable nature.

Coding theory - If the entropy is not maximum, then it is possible to compress a message. But, what are the ways in which we can compress a message? David Huffman came up with the Huffman coding strategy to compress a message with the help of a binary tree by encoding symbols into bits. However, the limit of (lossless) compression is the entropy of the message source. The information in the message would be lost when the message needs to be compressed beyond the specified limit.

Error detection & correction - During communication, noise in the channel corrupts the message resulting in difficulty for the receiver to understand the message. How is it possible to deal with noise? Richard Hamming came up with the idea of parity bits built upon the concept of repetition. Thus, error correction is done by using more symbols to encode the same message resulting in an increase in the size of the message.

Reference
Shannon, Claude Elwood. "A mathematical theory of communication." ACM SIGMOBILE Mobile Computing and Communications Review 5.1 (2001): 3-55. 

Friday 15 July 2016

Animal Farm, A Fairy Story - George Orwell

Animal Farm is a nice political satire on the Soviet Union written by George Orwell in 1943-44. The story portrays the evil effects of Socialism in an intelligent manner.

An interesting feature of Animal Farm is that the book spans only 90 pages which makes it remain one of the favorites among the busy working class even today.

I gave my own title to each chapter in the book. Spoiler Alert!

Chapter I The Dream Proposition
Chapter II The Rebellion Theorem
Chapter III The Heydays Axiom
Chapter IV The Recapture Claim
Chapter V The Napoleon Prime
Chapter VI The Windmill Lemma
Chapter VII The Traitors Corollary
Chapter VIII The Frederick-Pilkington Conundrum
Chapter IX The Boxer-Glue Conjecture
Chapter X The Pig-Man Paradox

Tuesday 24 May 2016

A Brief History of Time, Stephen Hawking

The Uncertainty Principle
Laplace argued that universe was deterministic i.e. we can predict the changes in the state of the universe provided we know the current state of the universe. However, Heisenberg's uncertainty principle showed that the more accurate we try to measure the location of an object the less accurate the result would be. As a result, it is difficult to measure the state of the universe at any given point of time.

Plank's quantum hypothesis and Heisenberg's uncertainty principle led to the theory of quantum mechanism where position of an object is defined in terms of probabilities i.e. an object would be at position A in time B with some probability C.

The dual nature of light is an implication of quantum mechanics. Quantum hypothesis said that light energy, which was thought to be composed of waves, was dissipated in terms of particles called quanta. The uncertainty principle said that particles may seem to be occurring at multiple positions based on the measurement. Interference of waves as well as particles (double-slit experiment) was observed.

The interference of particles helped physicists in understanding the nature of orbits of electrons in an atom. There are only a finite number of valid orbits in an atom because of the positive interference of electrons around the nucleus. The negative interference of electrons leads to the unavailability of certain orbits around the nucleus.

Einstein's general theory of relativity (classical theory) does not take the theory of quantum mechanism into consideration. It is necessary to combine both the theories in order to have a general, unified, consistent theory.

Roger Schank Blog

Roger Schank Blog 

Roger Schank in the latest article in his blog argues the AI is way more than just keyword matching and that an AI program should be able to exchange thoughts, hypotheses and solutions with other programs/humans.
 
He was commenting on the current state of AI research in the context of the massive attention media is giving to the news about a Georgia Tech professor announcing at the end of his course that one of his TAs was actually an “AI”. In fact, the “AI” he was referring to was nothing better than programs such as MARGIE, ELIZA and PARRY which were written in the 1970s and performed simple keyword matching. 

He predicts of an impending AI winter 2.0 due to the skewed perception media and, in turn, people have about the real potential of AI. He says there are important questions to consider in the field of AI such as:
  • Can we build machines that think, wonder, remember, feel and understand?
  • Is it enough if we continue to build such machines which do not perform any of the above actions but are still useful in one way or the other?

Tuesday 29 March 2016

Plato and Platypus

This article is a summary of the book "Plato and a Platypus Walk into a Bar" by Thomas Cathcart and Daniel Klein. The authors argue that philosophy and jokes are two sides of the same coin. Both of them amuse us, tickle our minds and makes us think. The book is an attempt to explain philosophy through jokes. The authors call this approach philogagging.

Metaphysics - Does the universe have a purpose? What are the characteristics that define an object? Do human beings have free will?
  1. Teleology - What is purpose of our lives?
  2. Essentialism - What are the essential qualities that define an object?
  3. Rationalism - We acquire knowledge through reasoning.
  4. Infinity and Eternity - Is the universe going to last till eternity?
  5. Determinism versus Free Will - Do we have free will or are all our actions predetermined?
  6. Process Philosophy - Evolving God!
  7. The Principle of Parsimony
Logic - How to perform reasoning?
  1. Aristotle's Law of Non-contradiction - A statement cannot be true and not true simultaneously.
  2. Illogical Reasoning - Wrong reasoning!
  3. Inductive Logic - Reasoning is performed based on observation and generalization.
  4. Falsifiability - In order for a statement to be valid there should be some possible circumstance when the statement can be proved to be false.
  5. Deductive Logic - Reasoning is performed based on rules.
  6. Argument from Analogy- Conclusions are drawn from analogous entities or situations.
  7. Post Hoc Ergo Propter Hoc Fallacy - An event X succeeded by another event Y does not necessarily mean X is the cause of Y.
  8. Monte Carlo Fallacy - Each trial is independent of the other.
  9. Circular Argument - One of the premises of an argument is the conclusion itself.
  10. Respect for Authority Fallacy - False dependence on the veracity of a higher authority than verifying the accuracy of a statement.
  11. Zeno's Paradox - Achilles and the Tortoise
  12. Logical and Semantic Paradoxes - This following statement is false. The preceding statement in true.
Epistemology - What does it mean to say I know something? How do we gain knowledge?
  1. Reason versus Revelation - Is knowledge attained through human reasoning or through revelation from God?
  2. Empiricism - Knowledge is attained through sense data
  3. German Idealism (Immanuel Kant)
  4. Philosophy of Mathematics - Analytic versus Synthetic statement, A priori versus A posteriori statement
  5. Pragmatism - Truth of a statement lies in its practical consequences.
  6. Phenomenology
Ethics - What is good? What is right? Is there any absolute standard to distinguish between right and wrong?
  1. Divine Revelation - Ethics is decided by God.
  2. Platonic Virtue - Ethics is decided by human wisdom.
  3. Utilitarianism - The end justifies the means.
  4. Golden Rule - Do unto others what you want others to do unto you (as long it can be considered a universal law).
  5. Will to Power
  6. Emotivism - Ethics is decided by our emotional state.
  7. Applied Ethics - Professional ethics
  8. Psychoanalysis - Ethics is decided by our unconscious being.
  9. Situation Ethics - Ethics is decided by the situation under consideration.
Philosophy of Religion - Is there a God?
  1. Deism and Historical Religions - "The Force" versus Creator/Clockmaker
  2. Belief in God - Theism (God exists), Atheism (God does not exist), Agnosticism (Current evidences cannot prove existence of God)
  3. Theological Distinctions - Jewish; Catholic, Protestant, Baptist, Methodist, Jehovah's Witness; Buddhism, Zen
  4. Airhead Philosophy

Philosophy of Language - How do we communicate?
  1. Ordinary Language Philosophy - "I promise" versus "I paint", "nothing" seems to be a thing, "I love you" and "I love ya" occur in different contexts, "I believe in God" can have different connotations,
  2. The Linguistic Nature of Proper Names - Bertrand Russel (short descriptions),  Saul Kripke (rigid demonstrators)
  3. The Philosophy of Vagueness

Social and Political Philosophy - Do we need laws? Is it possible to have an ideal state?
  1. The State of Nature
  2. Might equals Right
  3. Feminism
  4. Economic Philosophies
  5. Philosophy of Law
Relativity - What are the things that are relative and things that are absolute?
  1. Relativity of Truth
  2. Relativity of Time
  3. Relativity of World-views
  4. Relativity of Views
  5. Absolute Relativity
Existentialism

Tuesday 22 March 2016

My Political Views

I am a center-left social moderate.
Left: 1.46, Libertarian: 0.65

Political Spectrum Quiz

Edit (02-05-2020): After 4 years, I took the quiz again:

I am now a left moderate social libertarian.
Left: 5.45, Libertarian: 1.46

 

Wednesday 22 April 2015

A Thousand Splendid Suns, Khaled Hosseini

This is a fascinating book, which changed my impression about Afghanistan altogether. It tells the story of two women, Mariam and Laila, against the backdrop of various tragic events that happened in Afghanistan over a course of three decades. Hosseini displays exemplary narrative style by changing the perspective from one character to another with each chapter.

It all starts with the Soviet invasion in the late 1970s, followed by the civil wars between rival factions and finally, the Taliban. Kabul, which was once a vibrant and cosmopolitan city, gets totally shattered by the constant fights. Millions of Afghans flee to neighbouring countries. The Buddha statues of Bamiyan, which were destroyed by the Taliban, is one of the many atrocities that took place during that time.

Mariam is the character I liked the most in the novel. Her father was ashamed of the daughter since she was born outside marriage. Her mother so jealous of her that she feared her own daughter might enjoy the luxuries of life which she herself was denied. Her husband had contempt for her since she did not give birth to a boy. But still, Mariam never complained and led a selfless life. The final moments of her life, when she evaluates her own life and feels that she has someone to care for in her life is very emotional.

In short, 'A Thousand Splendid Suns' is a must-read.

Monday 21 July 2014

Areas of Research in Computer Science

This is a list of some of the areas of research in the field of computer science. Computer science is a rapidly changing area of research. It is difficult to predict the future because of this tremendous growth. The amount of digital data being generated is doubling every day. Thus, there are many interesting problems around us and computer science can be used effectively to solve many of those problems.


  1. High Performance Computing - improve system performance through techniques like using GPU's for computing
  2. Database – store, manage and process data
  3. Data Warehousing – maintaining huge database with data integrated from many sources, usually many databases
  4. Data Mining (or KDD) – process huge amount of data and come up with interesting patterns (like cluster analysis, anomaly detection, association rule mining) in the data.
  5. Artificial Intelligence - Artificial Intelligence is a field of computer science which deals with the study of how machines can be imparted with intelligence so that they can think and act on their own with a given data set. It involves knowledge representation, reasoning, planning,  natural language processing, machine learning, computer vision, robotics and strong AI, so that a computer mimics a human being.
  6. Computer Graphics - representation of image and video data
  7. Image Processing - analyze and manipulate image through techniques like compression, noise removal, background removal
  8. Computer Vision - extract information through techniques like pattern detection and recognition
  9. Artificial Neural Networks – reproduce the nervous system
  10. Bioinformatics – store, manage, process biological data
  11. Cryptography – protection of data
  12. Semantic Web – convert entire data in the WWW into a standard format which can be read by machines, because traditionally web is designed to be read by humans and not machines
  13. Multi agent system - a system in which intelligent agents communicate with each other in order to solve a problem which is difficult for a single agent to solve. http://www.cs.iastate.edu/~honavar/Papers/power-ieee04.pdf MAS involve ongoing interaction without ongoing communication.
  14. Theoretical Computer Science – theory of computation (automata theory or formal language theory, complexity theory and computability theory)
  15. Cluster Computing - It is similar to distributed computing, but here the computers are connected in a specific way, for example, a LAN. Whereas distributed computing spans huge geographical areas. There may be huge difference between the hardware configurations of cluster and distributed computing. Cluster is tightly coupled while the other is lightly coupled.
  16. Distributed Computing – software components located on a distributed system, which involves many computers on a common network through which they communicate with each other. Few aspects of DC are CORBA, Socket Programming, RPC, RMI. The users perceive it as a single node. As opposed to a centralized system, a distributed system has multiple points of control/failure. Common characteristics are resource sharing, concurrency, scalability, fault tolerance, transparency.
  17. Grid Computing – sharing of hardware resources, grid is where interaction is with the system as a whole and not with any node(s) in particular.
  18. Cloud Computing – sharing of services, store, manage, process data on remote servers, it involves many services like SaaS(Gmail), PaaS, AaaS, Iaas and etc.
  19. Parallel Computing – divide same problem into small problems which can be solved simultaneously
  20. Crowdsourcing - it is the process of obtaining needed services, ideas, or content by soliciting contributions from a large group of people, and especially from an online community, rather than from traditional employees or suppliers.

Friday 23 May 2014

Save Congress!

General Election 2014 results were declared last week. Though not even BJP had expected that they would win with such a clear majority, the poll debacle for the UPA was sure to come. UPA-II has failed the people of India. The scams, 'gates', policy paralysis, 'mute' MMS, RSVP gang all contributed immensely to this excruciating defeat. Modi was successful in creating his own space in minds of the people, such that even stalwarts like Nitish Kumar had to face the ire of the people, for breaking away from the NDA. While, some shrewd politicians, like Chandrababu Naidu, took advantage of the Modi wave by contriving an alliance with the NDA at the last minute, which ultimately put him back into the political equation in Andra Pradesh.

With a person like Rahul Gandhi at the helm, Congress has touched new low. Everybody knows it, but I am just saying it. RaGa has to resign. He may be the great-grandson/grandson/son of previous Prime Ministers of India. But that does not make him capable enough to lead the Grand Old Party, founded by the our freedom-fighters, which led India to the Independence and has seen India through each and every milestone in the history of Independent India. But now, Congress has dwindled to a party even without a National Party status.

RaGa needs an introspection. He needs to understand his place and space. I wonder why there is nobody in Congress to talk boldly against him. Till now, the allegations have only reached Rahul Gandhi's 'advisers' and has successfully avoided him. Who were these advisers? Would somebody in the Congress party care to name at least a few of them? Praful Patel even went to the extend of blaming MMS, the Accidental Prime Minister.

Assembly elections in states like Delhi, Maharashtra are fast approaching and another string of defeats is looming over the party. 'It's now or never' situation for the Congress. The solution? Let Priyanka Gandhi step in, as being clamoured by some Congressmen. Her credentials? Well, for one, she is the great-granddaughter/granddaughter/daughter of previous Prime Ministers of India. She even looks like Indira Gandhi. As for me, the only potential I found in her is that she is at least better than her 'chotta bhai'. While RaGa always talks nonsense, Priyanka talks some sense sometimes. Let Pappu roam around with chocolates in his mouth, clutching the hands of his mother.

Nitish Kumar took responsibility for the defeat of JD(U) in Bihar and resigned his post the next day. Let this be an inspiration to RaGa, and may he leave the control of Congress party to someone with good credentials, experience and passion.

A funny message I received in Watsapp says, ' Forget Tigers, Save Congress, Only 44 of them left.' Yes, it is time to save Congress.

Save Congress!

Thursday 22 May 2014

GATE CS/IT Notes

Please use this only as a reference. I would recommend all aspiring GATE candidates to create their own notes, which I am sure, would help you in the long run.

GATE CS/IT Notes

Please let me know of any error or typo you encounter in the notes. Since I am no Donald Knuth, it is not feasible for me to send you any checks or monetary rewards in that respect.