You are currently browsing the category archive for the ‘politics’ category.

A few weeks ago, the Proceedings of the National Academy of Science published an article on a study conducted by a group of Cornell researchers at Facebook. They picked about 600,000 users and then, for a week, a subset of them saw fewer “negative” posts (up to 90% were filtered) than they would otherwise see, a subset saw fewer “positive” posts (same), and a control group got a random subset.

After the week, the users in the “negative” group posted fewer, and more negative, posts, and those in the “positive” group posted more, and more positive, posts.

Posts were classified according to an algorithm called LIWC2007.

The study run contrary to a conventional wisdom that people find it depressing to see on Facebook good things happening to their friends.

The paper has caused considerable controversy for being a study with human subjects conducted without explicit consent. Every university, including of course Cornell, requires experiments involving people to be approved by a special committee, and participants must sign informed consent forms. Facebook maintains that the study is consistent with its terms of service. The highly respected privacy organization EPIC has filed a complaint with the FTC. (And they have been concerned with Facebook’s term of service for a long time.)

Here I would like to explore a different angle: almost everybody thinks that observational studies about human behavior can be done without informed consent. This means that if the Cornell scientists had run an analysis on old Facebook data, with no manipulation of the feed generation algorithm, there would not have been such a concern.

At the same time, the number of posts that are fit for the feed of a typical user vastly exceed what can fit in one screen, and so there are algorithms that pick a rather small subset of posts that are evaluated to be of higher relevance, according to some scoring function. Now suppose that, if N posts fit on the screen, the algorithm picks the 2N highest scoring posts, and then randomly picks half of them. This seems rather reasonable because the scoring function is going to be an approximation of relevance anyway.

The United States has roughly 130 million Facebook subscriber. Suppose that the typical user looks, in a week, at 200 posts, which seems reasonable (in our case, those would be a random subset of roughly 400 posts). According to the PNAS study, roughly 50% of the posts are positive and 25% are negative, so of the initial 400, roughly 200 are positive and 100 are negative. Let’s look at the 100,000 users for which the random sampling picked the fewest positive posts: we would be expecting roughly 3 standard deviations below the mean, so about 80 positive posts instead of the expected 100; the 100,000 users with the fewest negative posts would get about 35 instead of the expected 50.

This is much less variance than in the PNAS study, where they would have got, respectively, only 10 positive and only 5 negative, but it may have been enough to pick up a signal.

Apart from the calculations, which I probably got wrong anyway, what we have is that in the PNAS study they picked a subset of people and then they varied the distribution of posts, while in the second case you pick random posts for everybody and then you select the users with the most variance.

If you could arrange distributions so that the distributions of posts seen by each users are the same, would it really be correct to view one study as experimental and one as observational? If the PNAS study had filtered 20% instead of 90% of the positive/negative posts, would it have been ethical? Does it matter what is the intention when designing the randomized algorithm that selects posts? If Facebook were to introduce randomness in the scoring algorithm with the goal of later running observational studies would it be ethical? Would they need to let people opt out? I genuinely don’t know the answer to these questions, but I haven’t seen them discussed elsewhere.

“I may have the genetic coding that I’m inclined to be an alcoholic, but I have the desire not to do that – and I look at the homosexual issue the same way”

(Rick Perry, Governor of Texas)

So, if I understand Perry’s point, he may have a genetic inclination to be gay but he forces himself “not to do that”?

Judge Rolf Treu has ruled that teachers’ tenure violates California students’ constitutional right to an education.

The California Constitution, which I am now reading for the first time, has an entire section on education (also, an entire section on water), it specifically mandates state funding for the University of California, and it states, right at the beginning, a fundamental right to privacy. (Using the word “privacy,” which does not occur in the US constitution.) Yay California Constitution!

Back to Judge Treu, he has found that the right to an education implies a right to good teachers, and that tenure causes students to have bad teachers. Hence tenure is unconstitutional. Also the bad teachers disproportionally end up in districts with poor and minority students, so tenure is unconstitutional also on equal protection grounds. I am now looking forward to conservative California judges striking down other laws and regulations that affect the educational opportunities of poor and minority students, including prop 209.

As you may remember, a few months ago Dieter van Melkebeek, the steering committee chair of the conference on computational complexity, started a discussion on the future of the conference and on its relation to IEEE.

A poll among CCC former participants showed that 97% of respondents favored change, and a majority wanted the conference to be independent of both IEEE and ACM. The steering committee, subsequently, voted unanimously to make the conference independent.

The steering committee is now working out the logistics, and volunteers are needed to help. Already several people have pledged to contribute in various forms, and if you are interested there will be organizational meetings in Vancouver during CCC 2014. (By the way, today is the deadline for early registration.)

I would like to publicly thank Dieter both for the effort that he put on making this change happen and for the transparency of the process. I hope that, if some big change is coming for STOC or FOCS, it will be the result of a similarly open discussion.

I was having dinner at Machne Yuda, that was recommended to me as one of the best places to eat in Jerusalem (although I liked Chakra much better), and I was sitting at the bar, cramped between the French gay couple and the drunk Israeli lady with the huge boyfriend.

At the same time that I got my dessert, the lady with the huge boyfriend stood up to leave and, with remarkable swiftness for a drunk lady, took a piece of my cake asking, while she was already doing so, if she could try it.

Now, between the fact of the ground that a piece of my cake was already on her fork, the size of the boyfriend, the fate of the last people who tried to fight with the Israeli about what is whose and, really, haven’t the Jewish people suffered enough already?, the only logical thing to say was, sure, help yourself.

A little bit later, the bartender presented me with another (different) dessert. “This is on the house,” the bartender said, “I saw what she did, and it wasn’t right.”

The second dessert was better.

Dieter van Melkebeek, the conference chair of the Computational Complexity Conference (CCC), has started a discussion on whether to end the IEEE “sponsorship” of CCC. This is, I realize, a supremely boring topic, which seemingly affects only the handful of people who are tasked with organizing the conference. It does, however, affect to some extent all who ever paid a registration fee or published a paper in CCC, and I would like to discuss why I am, in the strongest possible way, in favor of leaving IEEE.

First of all, the term “sponsoring” here is a bit misleading. IEEE sponsors CCC not in the way Coca Cola sponsors the Olympics, but more in the way pirates sponsor navigation, or Elsevier sponsors scholarly publications. That is, it’s not that IEEE subsidizes the conference in exchange for exposure and good will; IEEE takes a huge chunk of our registration money, in exchange for making the lives of the local organizers harder. (I don’t mean to single out IEEE, when a professional society sponsors a conference it always works this way, but IEEE is particularly skilled at making the lives of the organizers hard.)

Last year I was an organizer of the complexity conference at Stanford. We had 108 attendees, who paid a total of \$37,425 of registrations, or \$346.5 each on average. How did we spend this money?

IEEE charged a 20% overhead to all expenses; that’s about \$60 per person and about \$6,500 for the whole conference. This, I should emphasize, is for doing literally nothing, except creating problems. For example, our conference could not be “approved” until all the paperwork of the previous conference was closed; it wasn’t closed because they were expecting some banking documents from them and I don’t remember if the issue was that the document does not exist in Portugal, or that they had already received the document and they had lost it. We were not allowed to make the conference web site go live until this was resolved.

One of the perks of organizing the conference with IEEE is that they provide free banking in the United States. (If the conference were organized by a created-for-this-purpose non-profit, it could have its own permanent bank account for little or no fee.) Three weeks after we sent all the paperwork to have our IEEE bank account set up, we get an email from the person we paid \$6,500 to “assist” us, saying “URGENT, URGENT, you have to send us the paperwork for the bank account”. After we reminded them that they had had it for three weeks, they replied, “oh yes, we do,” no apology. (And it still took a while to get the checks.)

The free banking does not include free registration handling, however. Here I accept responsibility for being foolish enough, after all this, to trust IEEE with their registration service. At a cost of more than \$26 per person (that’s almost \$3,000) they produced a registration website that seemed put together by a high school intern, and which required filling up five pages of… well, if you attended the conference you remember it.

Finally, IEEE press charged almost \$2,000 (almost \$18 per person) for the proceedings. Which proceedings, you may ask, since the conference had no proceedings? That’s a very good question. The charge of \$1,925 was to take our papers, take the copyright, and then put the papers were it is impossible to find them, even if you subscribe to the IEEE digital library. (Seriously, try to google a paper appeared in an ACM conference and one appeared in an IEEE conference and see if you are able to get the IEEE paper. Say what you want about the ACM, at least they know how to build a web site.)

In summary, IEEE took \$6,500 for doing nothing but causing delays, \$3,000 for a terrible registration site, and \$2,000 to hide our papers. That’s more than \$100 per attendee, and about 30% of how we spent the registration fee. The rest went on food and room rent.

Why are we still doing this? One reason is that the only people that are really affected by this system are the local organizers, and once one is done with the job, one doesn’t want to hear of or talk about IEEE any more. The other reason is that there is a big initial effort that is needed to make the conference independent. One needs to start some kind of entity to own the conference (the IACR, for example, was founded pretty much for the purpose of running CRYPTO and the other crypto conferences), which needs to have a statute, officers, a bank account and all kind of paperwork needs to be done. After that, however, it’s smooth sailing and considerable savings.

Here is one thing that IEEE does: if the conference runs a deficit, they cover it. We did, in fact run a deficit last year, of about \$1,000; so IEEE “covered” it, but that just means that instead of \$6,500 for the “sponsorship” they got \$5,500. If, going forward, we budget with the intention of putting away \$5,000 to \$7,000 per year, the registration costs will go down slightly and over a few years we can put away, say \$20,000 that can be a cushion for any kind of unforeseen event, and from that point forward budget to a balanced budget, with notably lower registration fees, and with some years running a surplus and some years running a deficit. Plus, we own our papers, and people can find them!

Ok, this is as boring as could be expected. I thank all those that have read so far, and, for the sanity of future local organizers and the principle of keeping our hard-earned taxpayer money and our papers, please support making CCC an independent conference.

“I think we have some folks who believe that our job is to be college professors. Now college professors are fine I guess. Being a college professor, they basically spout out ideas that nobody does anything about.”

Chris Christie, Governor of New Jersey, in a recent speech in, of all places, Boston.

Click for full size

not backward!

Oh man, not another election! Why do we have to choose our leaders? Isn’t that what we have the Supreme Court for?
– Homer Simpson

Nate Silver is now putting Barak Obama’s chance of reelection at around 85%, and he has been on the receiving end of considerable criticism from supporters of Mitt Romney. Some have criticized his statistical analysis by pointing out that he has a soft voice and he is not fat (wait, what? read for yourself – presumably the point is that Silver is gay and that gay people cannot be trusted with such manly pursuits as statistics), but the main point seems to be: if Romney wins the election then Silver and his models are completely discredited. (E.g. here.) This is like someone saying that a die has approximately a 83% probability of not turning a 2, and others saying, if I roll a die and it turns a 2, this whole “probability” thing that you speak of is discredited.

But still, when someone offers predictions in terms of probability, rather than simply stating that a certain outcome is more likely, how can we evaluate the quality of such predictions?

In the following let us assume that we have a sequence of binary events, and that each event $i$ has a probability $p_i$ of occurring as a $1$ and $1-p_i$ of occurring as $0$. A predictor gives out predicted probabilities $q_i$, and then events $E_i$ happen. Now what? How would we score the predictions? Equivalently, how would we fairly compensate the predictor?

A simple way to “score” the prediction is to say that for each event we have a “penalty” that is $|E_i - p_i|$, or a score that is $1- |E_i - p_i|$. For example, the prediction that the correct event happens with 100% probability gets a score of 1, but the prediction that the correct event happens with 85% probability gets a score of .85.

Unfortunately this scoring system is not “truthful,” that is, it does not encourage the predictor to tell us the true probabilities. For example suppose that a predictor has computed the probability of an event as 85% and is very confident in the accuracy of the model. Then, if he publishes the accurate prediction he is going to get a score of .85 with probability .85 and a score .15 with probability .15. So he is worse off than if he had published the prediction of the event happening with probability 100%, in which case the expected score is .85. In general, the scheme makes it always advantageous to round the probability to 0% or 100%.

Is there a truthful scoring system? I am not sure what the answer is.

If one is scoring multiple predictions of independent events, one can look at all the cases in which the prediction was, say, in the range of 80% to 90%, and see if indeed the event happened, say, a fraction between 75% and 95% of the times, and so on.

One disadvantage of this approach is that it seems to require a discretization of the probabilities, which seems like an arbitrary choice and one that could affect the final score quite substantially. Is there a more elegant way to score multiple independent events without resorting to discretization? Can it be proved to be truthful?

Another observation is that such an approach is still not entirely truthful if it is applied to events that happen sequentially. Indeed, suppose that we have a series of, say, 10 events for which we predicted a 60% probability of a 1, and the event 1 happened 7 out of 10 times. Now we have to make a prediction of a new event, for which our model predicts a 10% probability. We may then want to publish a 60% prediction, because this will help even out the “bucket” of 60% predictions.

I don’t think that there is any way around the previous problem, though it seems clear that it would affect only a small fraction of the predictions. (The complexity theorists among the readers may remember similar ideas being used in a paper of Feigenbaum and Fortnow.)

Surely the task of scoring predictions must have been studied in countless papers, and the answers to the above questions must be well known, although I am not sure what are the right keywords to use to search for such work. In computer science, there are a lot of interesting results about using expert advice, but they are all concerned with how you score your own way of picking which expert to trust rather than the experts themselves. (This means that the predictions of the experts are not affected by the scoring system, unlike the setting discussed in this post.)