Monthly Archives: June 2013

A poem in lieu of a post

Posted on by

I’ve not been posting because I have been visiting Japan for the last week (and for another week after this). I am teaching one week of a machine learning course at the Toyota Technological Institute (豊田工業大学, Toyota Kōgyō Daigaku), which is the main campus — TTI-Chicago is just a satellite campus. Between jet lag, sightseeing, and lesson prep I haven’t had much of a chance to post about anything.

My friend Celeste posted a link to the poem Telephone Repairman, by Joseph Millar.

Some people who read this blog work on communications. It’s worth taking a pause occasionally to contemplate, as the character in the poem does:

He thinks of the many signals
flying in the air around him
the syllables fluttering,
saying please love me,
from continent to continent
over the curve of the earth.

Advertisement

Open letter to the Urbana Free Library

Posted on by

I learned recently of a terrible tragedy at the Urbana Free Library, which was one of the formative institutions of my childhood. The Executive Director, Debra Lissak, authorized the removal of all books from the Adult Collection which were published after 2003. That was a mere 10 years ago. The collection of short stories by Hasan Saadat Manto, one of the most important chroniclers of partition, would have been summarily tossed. Why? Because the library didn’t own a newer edition of his work. Such decisions make me wonder if Lissak even reads books, or understands the function of a public library. I don’t think one needs a library science degree to understand that a terrible travesty has occurred here. I wrote a letter to Lissak, and if you read this and care about the UFL, I encourage you to do so as well.

I’ve also started a petition via change.org here.

The Library’s “official response” is here, and Lissak has been blaming “communication problems,” effectively blaming her staff when she should take responsibility for these acts. Her actions undermine the viability of the library and credibility of its leadership. It’s hard to be a Friend of a library whose administration is so deaf to the community it serves.

You can contact Debra Lissak, Executive Director, at 217-367-4058 or at dlissak@tufl.info. Because she is apparently disregarding the opinions of others, you may want to CC the administration of the library: dcassady@tufl.info, reference@tufl.info, lfegley@tufl.info, avoss@tufl.info, kwicks@tufl.info, foundation@tufl.info, administration@tufl.info, mfarrell@tufl.info, cscherer@tufl.info, bscheid@tufl.info, sbennett@tufl.info, aho@tufl.info, ejakobsson@tufl.info, jwilliams@tufl.info, amerritt@tufl.info, mnetter@tufl.info.

My letter to Lissak is below.
Continue reading →

ISIT notice from the organizers on the protest

Posted on by

Dear ISIT Participant,

As you may well be aware, there is an ongoing sit-in protest in Taksim Square, Istanbul. The protest is about a road construction and renovation project which calls for cutting down a large number of trees and demolishing a park. The protest has triggered street demonstrations in many cities around Turkey and has not yet subsided. Demonstrations continue to take place at Taksim Square especially in the late afternoon and evening hours. There are no clashes between the protesters and the police on or near Taksim Square. The shops are open and business runs as usual in the area. The Istanbul Conference and Exhibition Center (ICEC), where ISIT 2013 will take place, is about 1 km from Taksim Square and is safely away from the scene of the protests. The conference hotels which are at Talimhane district are 200-500 m away from the Taksim Square and there have been no reported cases of disturbance to the hotels or their guests. We are hoping that by the time of ISIT, the protests will come to an end. You may find the latest travel advisories issued by various governments here.

We will be updating you here as events develop.

Erdal Arıkan – Elza Erkip, ISIT 2013 Co-Chairs
Gerhard Kramer, President IT Society

Yet more skims from ArXiV

Posted on by

I’m still catching up on my backlog of reading everything, but I’ve decided to set some time aside to take a look at a few papers from ArXiV.

  • Lecture Notes on Free Probability by Vladislav Kargin, which is 100 pages of notes from a course at Stanford. Pretty self-explanatory, except for the part where I don’t really know free probability. Maybe reading these will help.
  • Capturing the Drunk Robber on a Graph by Natasha Komarov and Peter Winkler. This is on a simple pursuit-evasion game in which the robber (evader) is moving according to a random walk. On a graph with n vertices:

    the drunk will be caught with probability one, even by a cop who oscillates on an edge, or moves about randomly; indeed, by any cop who isn’t actively trying to lose. The only issue is: how long does it take? The lazy cop will win in expected time at most 4 n^3/27 (plus lower-order terms), since that is the maximum possible expected hitting time for a random walk on an n-vertex graph [2]; the same bound applies to the random cop [4]. It is easy to see that the greedy cop who merely moves toward the drunk at every step can achieve O(n^2); in fact, we will show that the greedy cop cannot in general do better. Our smart cop, however, gets her man in expected time n + o(n).

    How do you make a smarter cop? In this model the cop can tell where the robber is but has to get there by walking along the graph. Strategies which try to constantly “retarget” are wasteful, so they propose a strategy wherein the cop periodically retargets to eventually meet the robber. I feel like there is a prediction/learning algorithm or idea embedded in here as well.

  • Normalized online learning by Stephane Ross, Paul Mineiro, John Langford. Normalization and data pre-processing is the source of many errors and frustrations in machine learning practice. When features are not normalized with respect to each other, procedures like gradient descent can behave poorly. This paper looks at dealing with data normalization in the algorithm itself, making it “unit free” in a sense. It’s the same kind of weights-update rule that we see in online learning but with a few lines changed. They do an adversarial analysis of the algorithm where the adversary gets to scale the features before the learning algorithm gets the data point. In particular, the adversary gets to choose the covariance of the data.
  • On the Optimality of Treating Interference as Noise, by Chunhua Geng, Navid Naderializadeh, A. Salman Avestimehr, and Syed A. Jafar. Suppose I have a K-user interference channel with gains \alpha_{ij} between transmitter i and receiver j. Then if
    \alpha_{ii} \ge \max_{j \ne i} \alpha_{ij} + \max_{k \ne i} \alpha_{ki}
    then treating interference as noise is optimal in terms of generalized degrees of freedom. I don’t really work on this kind of thing, but it’s so appealing from a sense of symmetry.
  • Online Learning under Delayed Feedback, byPooria Joulani, András György, Csaba Szepesvári. This paper is on forecasting algorithms which receive the feedback (e.g. the error) with a delay. Since I’ve been interested in communication with delayed feedback, this seems like a natural learning analogue. They provide ways of modifying existing algorithms to work with delayed feedback — one such method is to run a bunch of predictors in parallel and update them as the feedback is returned. They also propose methods which use partial monitoring and an approach to UCB for bandit problems in the delayed feedback setting.

Readings

Posted on by

The Fractal Prince [Hannu Rajaniemi] — the sequel to The Quantum Thief is a bit of an arabesque (fans of Grimwood or Effinger may like that aspect). There are some interesting ideas about stories/code/viruses in there but some of it felt more like poetic gesture. I rather liked the Oubliette as a setting, but Sirr has some interesting bits too. I found the sequel a bit thinner than the original. Recommended for those who have read the first book and who are fans of the Culture novels of Iain M. Banks.

One Red Bastard [Ed Lin] — Third in the series of police/detective novels about Robert Chow, NYC Chinatown cop. This one focuses on the murder of a mainland representative who was going to smooth the way for Li Na to defect to the US. A fun read, although you probably want to read the first two novels in the series first.

Kingdom’s End and Other Stories [Saadat Hasan Manto] — A collection of short stories by a Pakistani writer who lived through Partition (and hated it, more or less). The stories are often dark, and depict a sordid underlife of violence, sex, and drugs in post-Independence worlds of Bombay and Punjab. I had never encountered Manto before — his sour cynicism is a counterpoint to the kind of knowing parody typical of R.K. Narayan, for example. I also checked out a new book about Manto from the Chicago Public Library.

Railsea [China Miéville] — A young adult book set in a world in which the sea is made up of traintracks and instead of hunting whales people hunt giant moles (moldywarpes). Captains have philosophies — everyone is out to hunt for their Moby Dick. The narrator, Sham ap Soorap, is a well-intentioned but somewhat immature fellow, and the world is just-enough-imagined to make you want to go along with it. A fun read.

No One Makes You Shop at Wal-Mart: The Surprising Deceptions of Individual Choice [Tom Slee] — A popular non-fiction book about how the rhetoric of “individual choice” is woefully misleading. Slee uses simple game-theoretic models to show how information asymmetries, power relationships, externalities, free-riding, herding, and other factors can make rational (and reasonable) individual choices result in (very) poor social outcomes. It’s a nice and accessible description of these results and a useful reminder of how dangerous it is to accept as an axiom that more individual choice is preferable. Collective action is also a choice. Recommended!

Eisen’s comments on the future of scholarly publishing

Posted on by

Michael Eisen gave a talk at the Commonwealth Club in San Francisco recently. Eisen is the founder of the Public Library of Science (PLoS), which publishes a large number of open-access journals in the biosciences, including the amazingly named PLoS Neglected Tropical Diseases. His remarks begin with the background on the “stranglehold existing journals have on academic publishing.” But he also has this throwaway remark:

One last bit of introduction. I am a scientist, and so, for the rest of this talk, I am going to focus on the scientific literature. But everything I will say holds equally true for other areas of scholarship.

This is simply not true — one cannot generalize from one domain of scholarship to all areas of scholarship. In fact, it is in the differences between dysfunctions of academic communication across areas that we can understand what to do about it. It’s not just that this is a lazy generalization, but rather that the as Eisen paints it, in science the journals are more or less separate from the researchers and parasitic entities. As such, there are no reasons that people should publish with academic publishers except for some kind of Stockholm syndrome.

In electrical engineering and computer science the situation is a bit different. IEEE and ACM are not just publishing conglomerates, but are supposed to be the professional societies for their respective fields. People gain professional brownie points for winning IEEE or ACM awards, they can “level up” by becoming Senior Members, and so on. Because disciplinary boundaries are a little more fluid, there are several different Transactions in which a given researcher may publish. At least on paper, IEEE and ACM are not-for-profit corporations. This is not to say that engineering researchers are not suffering from a Stockholm syndrome effect with these professional societies. It’s just that the nature of the beast is different, and when we talk about how IEEExplore or ACM Digital Library is overpriced, that critique should be coupled with one of IEEE’s policy requiring conferences to have a certain profit level. These things are related.

The second issue I had is with Eisen’s proposed solution:

There should be no journal hierarchy, only broad journals like PLOS ONE. When papers are submitted to these journals, they should be immediately made available for free online – clearly marked to indicate that they have not yet been reviewed, but there to be used by people in the field capable of deciding on their own if the work is sound and important.

So… this already exists for large portions of mathematics and mathematical sciences and engineering in the form of ArXiV. The added suggestion is a layer of peer-review on top, so maybe ArXiV plus a StackExchange thing. Perhaps this notion is a radical shift for life sciences where Science and Nature are so dominant, but what I learn myself from looking at the ArXiV RSS feed is that the first drafts of papers that get put up there are usually not the clearest exposition of the work, and without some kind of community sanction (in the form of rejection), there is little incentive for authors to actually go back and make a cleaner version of their proof. If someone has a good idea or result but a confusing presentation they are not going to get downvoted. If someone is famous they are unlikely to get downvoted.

In the end what PLoS ONE and the ArXiV-only model for publishing does is reify and retrench the existing tit-for-tat “clubbiness” that exists in smaller academic communities. In a lot of CS conferences reviewing is double-blind as a way to address this very issue. When someone says “all academic publishing has the same problems” this misses the point, because the problems is not always with publishing but with communication. We need to understand the how the way we communicate the products scholarly knowledge is broken. In some fields, I bet you could argue that papers are inefficient and bad ways of communicating results. In this sense, academic publishing and its rapacious nature are just symptoms of a larger problem.