Opinions and How They Change

An individual forms opinions based on how he can himself assimilate the facts around him and also based on what opinions his friends and other people he interacts with hold. This makes things complicated and intriguing enough that this has been an active area of research since decades.

One question is, can we formulate simple enough models that match with the data we get from real life experiments? If we could, then we would get some insight into human behavior and a tool for making useful predictions.

The simplest model that has been studied is this:

An opinion is just a real number. Each person starts with an initial opinion. Next, in each time step, he looks at the opinions held by his friends and updates his own opinion to the average of his old opinion and the opinions of his friends. It doesn’t have to be a simple average. A person may have different trusts for different friends and thus he might want to take a weighted average instead. However the model doesn’t allow individuals to change the weights at any step. The weights chosen in the beginning have to be the weights always.

Using simple linear algebra tricks and borrowing known results from the Markov Chain literature, it can be shown that this kind of system converges to an equilibrium in most natural cases. An equilibrium here means a set of opinions for which the averaging step doesn’t lead to any change, i.e., for all individuals, the new opinion remains the same as the old one. In fact, it can be proved that the equilibrium that’s reached is a consensus, i.e., every individual has the same opinion.

An objection to this model that one might have is the simple representation of an opinion. Can it really be represented by just a single real number?

Anyway, DeGroot, the person who introduced this model also showed that the same thing happens if the opinions are drawn from any vector space and in each time step a person updates his opinion to some convex combination of the opinions of his friends (including himself).

That’s something.

The only issue is that in real life, people don’t reach consensus. So what’s going on?

Of course, the model seems too simple to resemble real life accurately. For one, the weights (or trust) we assign to people changes over time depending on various factors. For example, if a person seems to be changing his mind every minute, we will probably assign a lesser weight to his opinion.

Also, even though this process of repeated averaging has been shown to always converge to a consensus, we don’t really know the amount of time it takes to reach there. From what I know by quickly glancing through Bernard Chazelle’s new work on bird flocking, the time taken by a community whose size is close to the population of a country to reach a consensus is probably way more than the age of the universe.

Anyway. Friedkin and Johnsen modified this model a bit to make it more realistic. In their model, an individual has a fixed internal opinion that doesn’t change with time and during an averaging step, he takes a weighted average of the opinions of his friends (including himself) and the fixed internal opinion. Because the internal opinion can be different for different people, this system will obviously not reach a consensus always.

The system does have an equilibrium though and Friedkin and Johnsen proved that the equilibrium is almost always reached.

However, their model is different from DeGroot’s simpler model in a fundamental way. Let me explain.

Given a set of numbers , the mean is the number that minimizes the function . Thus the averaging step above can be seen as a step where a person is trying to minimize the cost incurred with respect to the cost function . Here represents the neighborhood of , i.e., the set of friends of .

With the above definition of cost, we can measure the quality of a certain opinion vector. For example, we can say that the sum of costs incurred by each person is the social cost of the whole group. And then given an opinion vector, we can decide how good it is by measuring how far it is from the opinion vector that minimizes the social cost. In particular, we can measure the quality of the opinion vector that the group converges to in equilibrium.

The fundamental difference between DeGroot’s model and Friedkin and Johnsen’s model is that in DeGroot’s model, the equilibrium reached also minimizes the total social cost but in Friedkin and Johnsen’s model, it does not necessarily.

David Bindel, Jon Kleinberg and Sigal Oren prove in their FOCS ’11 paper that the situation is not that bad. Even though the total cost at equilibrium may not minimize the total social cost, it can be worse at most by a factor of 9/8. That’s pretty cool.

Building the perfect world in four extremely difficult steps

(I had written this for Goodblogs a long time ago.)

A perfect world would be one where everyone just did whatever they wanted to and lived happily doing that.

If tomorrow, everyone just decides to do whatever they want to, the world will turn into a chaos. For example, no one will want to clean the garbage and as a result, we will eventually rot in our own filth. To keep the world working, it is necessary that at least some people do things that they don’t particularly like doing. Can we repair this? In general, can we design a perfect world, a world where you never have to feel guilty, a world where you can just do whatever you feel like at any given moment and that will be the best thing to do for you and for the society? If yes, then what are the steps we need to take?

To understand this, we first need to understand what is the best thing for the society. There are things that are good for some people and bad for the others and there are things, that are good for the society right now, but in the long run, will lead to the decay of mankind. Let’s, for the time being, define ‘best’ as the thing that has the best average over people and over time. That is, we take the average happiness level of the world at this time and then take the average of this average over time. The best thing then, would be the thing that maximizes this average.

Once we have this out of our way, we can understand that the essential problem is to align what an individual feels like doing at a given moment and what’s the best thing to do for the society at that moment. Since our definition of ‘best’ depends on happiness levels of people, there are two extreme approaches to solving this problem. One extreme is to reprogramme the human brain so that it feels happy or sad in a more controlled way. This extreme is slightly trivial. All we need to do is to build the perfect mood enhancing drug and make it compulsory for everyone to take it. This will suddenly boost up the total happiness level of the world. The other extreme is to leave the human brain untouched and reengineer the world in such a way that whatever we want at this moment is made possible immediately. This is perhaps impossible. It’s easy to imagine an individual getting so angry at another person that he genuinely wants to kill him, or harm him severely in some other way. If then, this were made possible immediately for him, it would create more grief to the person being harmed than happiness to the person inflicting the harm. It’s similarly easy to imagine completely outrageous, or even physically impossible wishes that a person can make. One might have to break some laws of physcis to make that possible immediately. Since this approach seems impossible and the other extreme is kind of sad, the ideal should lie somewhere between the two extremes.

One possible midway approach is the following.

Step 1 – Build robots to do all the dirty work that no one in the world wants to do but is necessary to be done. This will leave out the kinds of work that at least some people in the world like doing. Let them do that work. But there might still be problems. The person who likes doing the work X might be living in Japan and the place where X needs to be done might be in Canada. Moreover, if we consider one person who likes doing X, then he may not want to do X all the time. The time when X needs to be done in Canada, he might be in a mood to go swimming with his kids.

Step 2 – Build a global work organizer. This will be some huge global device that will take the help of the internet. It will monitor what each person in the world is in the mood of doing right now and the things that need to be done at this moment in different parts of the world. Then, it will match the tasks to the suitable people. Since the world is such a large place, we can assume that what a random person wants to do at a given moment is useful for someone somewhere in the world and what’s useful for a given person is being wanted to be done by someone somewhere in the world. If there is some task, where this doesn’t happen, we already have step 1 to take care of it. Such things are already being done. There are several outsourcing services online for tasks that do not require physical presence. For example, Mechanical Turk and oDesk are websites that are designed exactly for this purpose. Even GoodBlogs is similar. The previous post I wrote was originally intended to be an email to my mother. But somehow somewhere in the world, there was a group of people who agreed to give me $20 for it. However, building this global work organizer will still not build the perfect world. For that, we will need the next step.

Step 3 – Upgrade the human mind so that its emotions are in control. For example, no one should ever feel like seriously inflicting any harm on anyone else. Not just this, but one will also need to make sure to not inflict any harm on the future self. Even if everyone is full of kindness and love towards others, one still might want to smoke a cigarette and thus suffer with lung cancer later in life. If not, then one may simultaneously want to learn how to play the piano and to not practise, or, to get a girl and to not develop the skills to woo women etc etc.

Step 4 – Make learning easy. Even if we are the masters of our own emotions, have robot servants and are never forced to do something that we don’t want to do, there might be a situation where we want to learn something quickly but we can’t. For example, one one may be craving good food, but not know how to cook. Then it will be good to have a plugin that they can install on their mind to give them that feature in a few seconds.

Pass My Will

Did you hear about the new website http://passmywill.com/ ? This is from a Lifefacker article describing the new service -

PassMyWill is a free service that will check in with Facebook and Twitter to see if you’re alive and posting updates, if you don’t appear to be active, it will send you an email to confirm your death, then it sends out emails to everyone on your list if you don’t respond

Even though the service might be genuinely useful for some, I can’t stop noticing the humor associated with it. For example, what exactly is the confirmation email going to say?

Hey,

We noticed your inactivity on Facebook and were worried that you might have died. Please reply to this email if you are still alive.

Regards,

PassMyWill

It’s a bit like asking a woman if she’s pregnant. It’s funny if it turns out that she’s just fat. Similarly, the reason why you haven’t visited Facebook in a while could be just that you were on vacation.

On the plus side, it will serve as a nice reminder to catch up with your friends. If someone’s started doubting that you might be dead, then it’s probably the right time to amp up your social life a bit.

Two simple questions

In how many ways can you distribute distinct objects into different bins?

Of course, for each object, there are possible bins, so the total number of ways is .

Now, consider the same question, except, the objects are not distinct any more. Thus all that matters is how many of them go into each bin and not which ones in particular.

The answer to this can be slightly complicated to calculate, but if we simplify things a bit and look for a loose upper bound, we can argue as follows. The problem is equivalent to assigning one number between 0 and to each bin so that the sum of all assigned numbers is exactly . If we completely ignore the fact that the sum must be , then we get that the total number of ways of assigning numbers is .

I am certain that I knew both these things back in high school, but it was quite recently that I realized that the first one is exponential in and the second one is polynomial in . That’s a huge difference. Just making the objects distinct changes the total search space from polynomial to exponential.

How hard is NP-hard?

Assuming P NP, an NP-hard problem cannot be solved in polynomial time. This means that there cannot exist an algorithm that, for all possible inputs, computes the corresponding output in polynomial time. However, NP-harndess doesn’t prohibit the existence of an efficient algorithm for only a subset of the possible inputs. For example, there is a constant time algorithm for any problem that solves it for a constant number of instances. The algorithm just has a lookup table where the outputs of all the constant number of inputs are stored.

But this is an extreme case. Can there exist an algorithm for an NP-hard problem that solves it in polynomial time for a significantly large number of input instances? Or, more precisely, does there exist an algorithm, that, for all , solves the problem in polynomial time for inputs of size , where is some fast growing function of ?

How fast growing should be? One interesting choice for is something that makes the average case complexity of the algorithm polynomial, i.e., if inputs are chosen uniformly at random from the set of all inputs, then the algorithm takes polynomial time in expectation. Of course, will have to be fairly large for this to happen.

The interesting fact is that this is possible. For example, if you pick a graph on vertices randomly, with a distribution that is uniform over all graphs with vertices, then there exists an algorithm that decides whether the graph is hamiltonian or not in expected polynomial time.

Hamiltonian cycles in maximal planar graphs

Whitney proved long ago that every maximal planar graph with no separating triangles is Hamiltonian. However, the converse is not necessarily true, that is, there exist maximal planar graphs that are hamiltonian and have separating triangles. So what happens when a maximal planar graph has separating triangles? Is there still some condition under which we can say with certainty that it will be Hamiltonian as well?

One theorem of this kind was shown by Jackson and Yu.

Consider a maximal planar graph with a separating triangle . can be decomposed into two graphs and such that and . If or still has separating triangles, then decompose them similarly. Eventually, we will be left with a collection of maximal planar graphs without any separating triangles. Now, consider a graph whose nodes represent elements of the set and there is an edge between two nodes if they share a separating traingle in . Let’s call this graph . The theorem by Jackson and Yu states that if has maximum degree 3, then is Hamiltonian.

This way of decomposing maximal planar graphs has been popular. It was first used by William Cunningham and Jack Edmonds in 1980. They proved several interesting results about the decomposition graph .

Intelligence and How to Get it

Some time ago, I read a book called Intelligence and How to Get it: Why Schools and Cultures Count, written by Richard E. Nisbett.

That’s when I became intelligent.

The book has some very interesting research about intelligence. It basically tries to argue that intelligence is not completely in the genes.

Anyway, while I was reading the book, I started writing up some interesting stuff that I read, and emailing it to some friends. The idea was of course, to archive things so that, you know, when 10 years from now, I start writing my New York Times bestseller, I have access to all the material I was reading.

Now, I realized that the emails can actually be shared online. So here is a pdf that has all the emails in this series. When I was writing those emails, I was not trying to make them into well organized essays. Thus this pdf looks like a collection of various independent thoughts. I have separated those indpendent thoughts with a line made of asterisks.

I did the same thing with some other books that I read too. I will post their respective pdf’s here as well.

The New X-Men Movie

It’s annoying when someone who has never taken a Physics 101 course tries to make a sci-fi movie. Case in point is the new X-men movie – X-men first class. Let me explain.

My first problem is with Magneto. He is the superhero who can change himself into a magnet and pull or push things that are made of iron, or other magnetic materials at his will. All that is acceptable. What’s not acceptable is when he pulls a whole submarine out of the ocean. Even if we assume that somehow he is able to muster enough magnetic strength into his body to significantly move such a heavy object against the strong pull of gravitation, my problem is this – what happened to Newton’s third law of motion?

We were taught in high school that forces exist only in pairs called action-reaction pairs. That is to say, you cannot apply a force on another object independently. Whenever you try to do that, the other object will apply an equal and opposite force on you. For example, when the earth pulls us down, we pull the earth up with the same force. It’s just that since our mass is so insignificant compared to the mass of the earth, the force has a visible effect on us but very close to zero effect on the earth. And since we are distributed all over the surface, these already negligible effects cancel each other out to a large extent.

Now if we look at Magneto pulling the submarine out of the ocean with the sheer pull of his magnetic body, Newton’s third law would suggest that the submarine should also pull Magneto downwards with the same force. And since Magneto’s own mass is negligible compared to the mass of the submarine, the effect that you see on the submarine should be negligible compared to the effect you see on Magneto. What I am trying to say is that if Magneto can apply a force enough to pull the submarine out, he himself should fly at an enormous velocity towards the submarine and die within milliseconds of the impact.

You might argue that come on, he’s a superhero and so he can do everything. But the problem with this argument is that he actually has clearly defined powers. His power is to turn himself into a magnet. Honestly, if a superhero could violate Newton’s third law, then this power would be way more impressive than being able to turn himself into a magnet. He should have been called the third law violato or something, instead of Magneto.

My second problem is that dude who could fly simply by wearing wing-shaped clothes and screaming in an ultrasonic voice. In fact, I can’t fathom a reasonable scenario that could lead someone into thinking that these two things were related. The only thing that comes to mind is this – bats emit ultrasonic sounds and they can fly. But really? Is that all that you need to be convinced that you can fly by producing ultrasonic sounds? Human history is full of incidences where someone died because of an attempt at flying without thinking things through. Is this really all they were missing? Scream at the top of your voice while flying? I wonder why inspite of so much advancement in flying technologies, there does not exist a single aircraft that works on this ultra-sonic sound princple. It should be way easier than all that stuff the Wright brothers did! All we really need is a loose sweater and a sonographic equipment from the nearest hospital!

What I hate about the way people do research

I agree with this article from Daniel Lemire’s blog so much that I thought I should post a link to it on my blog.

To quote from the article -

In the conventional peer review system, you seek to please the reviewers who in turn try to please the editor who in turn is trying to guess what the readers want. It should not be a surprise that the papers are optimized for peer review, not for the reader. While you will eventually get your work published, you may have to drastically alter it to make it pass peer review. A common theme is that you will need to make it look more complicated. In a paper I published a few years ago, I had to use R*-trees, not because I needed them, but because other authors had done so. When I privately asked them why they had used R*-trees, while it was easy to check experimentally that they did not help, the answer was “it was the only way to get our paper in a major conference”. So my work has been made more complicated for the sole purpose of impressing the reviewers: “look, I know about R*-trees too!” Several times, during the course of peer review, I was asked to remove material which was judged to be “textbook material”: didactic material is frowned upon in many circles (hint: it is not fancy enough).  Be warned: if you find an easy way to prove a result, and it ends up looking trivial in retrospect, your work may become unpublishable. You will need to invent all sorts for complex related problems to pass peer review. It explains why several  important results appear as remarks in long and complicated papers. Either purposefully, or by habit, people will write in a way to make their paper pass peer review even if it makes the work inaccessible. Do you think research papers have to be boring? If so, you have been brainwashed.

Also,

You know how you succeed in science these days? Take a few ideas, then try every small variation of these ideas and make a research paper out of each one of them. Each paper will look good and be written quickly, but your body of work will be highly redundant. Instead of working toward deep contributions, we encourage people to repeat themselves more and more and collect many shallow contributions. We sacrifice scholarship for vanity.

This is all very true. This kind of attitude is so prevalent in the research community that it cannot go unnoticed. You will find well respected researchers taking up a problem that’s already solved, finding a variation that’s completely meaningless and devoid of motivation and then solving it, because as long as the solution turns out to be complicated enough there will be a respected conference or journal to accept it as a paper. New researchers are encouraged to jump into this rat race. Most people are always on a lookout for problems to solve. It doesn’t really matter if the problem is going to bring new insight into the way we think about the field in which they are working. It doesn’t really matter if the problem doesn’t fit into any of the three categories I listed in an earlier post. All that matters is that it fits into the fourth one – that you can get a paper out of it.

Interesting fact #5

Richard Dawkins can’t roll his tongue into a tube.

(He says this in a book. I am not sure if he was just cooking up an example or he really meant this.)