I recently worked on a project for representation learning on 3D shapes using their point clouds and meshes – specifically, 3D scans of teeth. The problem was straitforward: given a 3D point cloud from a scan of a single tooth in a manufacturing facility that makes crowns, determine which CAD design mesh, among tens of thousands of possible designs, it belongs to. The scan and the designs are not in the same orientation/pose, and do not have the same number of points.

One of the core open questions in neuroscience is: How is a piece of information represented and memories stored inside human brains? This is a question I’ve been casually pondering over for a while. I strongly suspect that each individual has a different representation of ideas in their brain, and these differences explain a numer of psychological phenomena we see in daily life. This is a stream of consciousness post, with no links to academic research, mainly so I can catalog my thinking and build upon it later, and use this piece as a launching piece to discover futher refinements and corrections from friends that know more about these topics.

Real world perceptual data (images, language, audio, 3D shapes) has a large amount of redundancy. In other words, the number of bits needed to perfectly represent a sample in one of these data modalities is very high, but a large percentage of those bits are actually spent in representing very fine, minute details. If we were to find a way to compress the information needed to represent an data sample in one of these modalities, then relatively few bits would suffice to capture the high level perceptual detail. For example, high-fidelity audio is about 9 Mbps but MP3 audio is only about 200-300 kbps and telephone voice is just 64 kbps. The drop in telephonic voice audio quality is obvious. This tradeoff between the number of bits used to represent data, and the distortion (which is loss in information, and in a practical system it is typically the reconstruction error) is formally captured in classical information theory using a rate-distortion curve. This is typically a convex curve with rate on the Y axis and distortion on the X axis:

Denoising Diffusion Probabilistic Models (DDPMs) are a fascinating way to do generative modeling. In essence, the idea is to construct a forward Markov chain that gradually adds noise starting with a clean sample of your data, and going all the way to pure noise. The reverse process recovers successively denoised versions of the data starting with pure noise, and ending with a generated data sample that is from the same distribution as the data the model was trained on. This simple-sounding method showed striking reuslts on generating natural images with this 2020 paper, although the idea of using diffusion processes in machine learning is from way back in this 2015 paper. In the last 5 years, the use of DDPMs has grown well beyond computer vision – it is a central workhorse in generative modeling of molecules for de novo protein based drug design.

EDIT: After writing the summary below of the current state of humanoid robotics below, I cam across a couple of great posts recently written by roboticists:

I recently had the opportunity to read a number of machine learning papers on the problem of designing a good motion planner in robotics. Many of these papers came from the autonomous vehicle industry, especially Waymo. The set of problems that arise in the design of a good planner seems quite distinctive, and in many respects different from other machine learning problems. This note summarizes what I learned.

This is a working list of areas at the internsection of economics and technology that I would like to see more work in. If you work in this space, or if you have ideas, or even if you just want to chat over a coffee (or a zoom call), hit me up!

A positive externality is when an economic actor A works to add value, but the benefits of this work are mostly captured by other economic actors B. The following tidbit from Marginal Revolution caught my eye:

I’ve written before about products and services that have the following properties:

Several years ago, I posted a question to friends and acquitainces: why is it that professionals such as teachers and nurses are paid low despite the fact that they add a lot of value, while there are seemingly professionals that do not add a lot of value to society but earn many times more? Several theories and opinions poured in. One of them happened to be from an MBA friend - it has since taught me a lot about economics. It is simply this:

I feel modern curriculum for children lack education in basic concepts of economics – these basic ideas as so basic that we need not wait till college to teach them formally – I’m talking about things like:

For the past few years I’ve been trying to trying to put into words the idea of the difference between two different types of people. The closest I came to expressing this difference was enterpreneurs versus non-enterpreneurs, but the difference is more subtle.

Two things that I would really like to see:

I believe obtaining and acting upon feedback from others is a crucial part of growth. Startups obtain feedback from their market, academics obtain feedback from conferences and journeals they publish their work in, restaurants get feedback in the form of restaurant critics and just plain foot traffic, and so on. However, in the world of ideas, there are a few places where feedback is prevented, because of a closed system. By ‘closed systems’ I mean collections of individuals in which the flow of information is deliberately restricted. Some examples are:

I have a pet theory that we humans are bad at anything that deviates sharply from what we evolved for. This is widely accepted when it comes to a number of physical aspects of our existence, documented below. This is a working document in which I will continually add evidence in support of this theory.

A ‘free market’ is an idealized mechnism wherein buyers and sellers come together to buy a sell a good or service, with little or no external control or regulation. For example, if you want to buy a cup of coffee in the United States, you, the buyer can simply go buy it at any seller, pay whatever a given coffee shop is charging, assuming you like the cost, and buy a cup of coffee. The price of a cup of coffee is not set by the government. On the other hand, the market for purchasing petrol/gasoline for your automobile in India is not a free market because the price per liter is set by the goverment of India.

In variable selection problems where the number of predictors is large relative to the number of data points, the optimization of penalized objective functions represents a convenient approach to regularization. The $L_2$-penalty (ridge regression), and $L_1$-penalty (Lasso regression) are most common. There is even a penalized regression called elasticnet regression, that combines the $L_1$ and $L_2$ penalties as a convex sum. Looked at from a Bayesian lens, the $L_2$-penalized regression solution is the mode of the posterior distribution if a Gaussian prior is placed on each of the linear regression coefficients, while the Lasso solution is the mode of the posterior if a Laplacian distribution is used as the prior instead. The Laplacian distribution, being non-differentiable at 0, is peakier than the Gaussian distribution, and as a result it results in a sparse solution.

Well. Finally got around to putting this old website together. Neat thing about it - powered by Jekyll and I can use Markdown to author my posts. It actually is a lot easier than I thought it was going to be.

The average age of first time mothers in the developed countries of the world has been rising for the last ~40 years.

During the recent 2016 summer olympics in Brazil, I found myself grumbling along with some friends about the historically poor performance of India at the Olympics. During the discussion, it was suggested that one of the reasons for India’s poor performance at the Olympics might be that Indians are genetically disadvantaged at competitive sport. This was an intriguing hypothesis, but one that was difficult to settle.

A positive integer can be visualized as a tree, structured by its prime factors. I wrote a little program which takes a positive integer as input, and creates a tree layout that shows its prime factors visually. Here’s the tree for 70:

I don’t seem to have very much influence on Walter. That is one of his strengths; no one has much influence on him.

Creativity is just connecting things. When you ask creative people how they did something, they feel a little guilty because they didn’t really do it, they just saw something. It seemed obvious to them after a while. That’s because they were able to connect experiences they’ve had and synthesize new things. And the reason they were able to do that was that they’ve had more experiences or they have thought more about their experiences than other people.

(…)

Unfortunately, that’s too rare a commodity. A lot of people in our industry haven’t had very diverse experiences. So they don’t have enough dots to connect, and they end up with very linear solutions without a broad perspective on the problem. The broader one’s understanding of the human experience, the better design we will have.

Price discovery is

The percentage of a country’s population that feels religion plays an important role in their lives (x-axis) seems negatively correlated with the GDP per capita (Y-axis, in log-scale):

Happiness is as hard to define as it is to achieve. Everybody wants to be happy. Even masochists. I think it is best to use  a non-constructive definition:

Intelligence is a slippery thing to define. The following definition recently struck me:

The average age of first time mothers in the developed countries of the world has been rising for the last ~40 years.

Perceived level of corruption in the public sector:

I have been posing this question to friends and acquaintances (and to myself) in one form or another for a while now. The answers I have received have varied significantly. I am not the first to pose this question of course. Here is one of several online polls, posing the same question, with 700+ responses so far. Here are some others. Some of the responses I have received personally and gathered from various online postings like the ones above, in no particular order include:

Why is the picture on the right more appealing than the one on the left?

In the aftermath of the Sandy Hurricane, many parts of the NY/NJ area have sustained power outages, and as a result, traffic lights in these areas are not functional. This requires drivers to approach a traffic junction as a multi-way stop-sign. This got me thinking: What if, in place of traffic lights, we had just stop signs everywhere, and the rule was: the next car to go should be the car at the head of the longest queue. I believe this is an optimal scheduling policy in a certain sense (it provides an optimal throughput x delay product — that is for a given average delay at the intersection, it would provide the highest rate number of cars going through [1] ). In this policy, each driver is trusted to follow the scheduling policy faithfully. For argument sake, I am ignoring (1) the time spent by each driver having to figure out which queue is the longest at each step, (2) how the driver at the head of each queue gets information about the length of each queue, and (3) the loss in efficiency incurred by slowing down and starting.

The climate change hypothesis is that global changes in climate leading to significantly higher number of severe weather events are predominantly man-made, and in particular, the release of greenhouse gases such as carbon-dioxide into the atmosphere is a leading cause. After conveniently escaping the national spotlight in the US during the presidential campaigns, climate change has once again appeared in the news, thanks to Hurricane Sandy. Munich-Re, the reinsurance giant released a report, somewhat presciently on Oct 17, that says:

I think T.V. Sucks the creative life out of you.

Conventional wisdom says that the marginal gains accrued per unit increase in effort are diminishing. In some cases this does not hold, and the gains seem to be super-linear, rather than sublinear in the amount of effort.

Optimal stopping problems frequently pop up in real life decision making. I have been collecting a bunch of stopping problems, with the aim of clustering similar problems together, and finding general solution strategies to specific flavors of problems. Here is my (growing) list:

This post builds upon an earlier post on modeling habit formation. To follow this post, please read this post first. Go on, I’ll wait.

A positive integer can be visualized as a tree, structured by its prime factors. I wrote a little program which takes a positive integer as input, and creates a tree layout that shows its prime factors visually.

Mathematical and logic puzzles are a great way to learn. I think they should be used to a greater extent in school and college education than they are, because they:

I have wanted to draw webcomics for at least the last 3 years, but never got around to figuring out an easy way to do it. Drawing on a computer with a mouse is a disaster. There are special tablets like Wacom‘s that artists use (I believe xkcd uses Wacom’s tablet). There are also some high-end, expensive iPad apps (e.g. brushes). But I wanted to do very simple drawing and without spending any money. I finally decided to put together a easy to use method for drawing simple black & white comics.

The problem with conventional text documents is that you cannot easily query them. Suppose I have a 20 page piece of text explaining various things, perhaps with mathematical equations, and plots, etc. In order to figure out something, I need to patiently read through the document till I have my answer. When time is short, and usually time is short, I will skip some parts in a hurry to get to what I need. The skipped parts might contain intermediate facts or definitions, making it impossible for me to understand what I am looking for even when I do find it.

“Many people choose a subject for their PhD and then continue the same subject until they retire. I despise this approach. I have changed my subject five times before I got my first tenured position and that helped me to learn different subjects.”

Tasks that require a high cognitive load, such as thinking about a problem, reading a research paper or writing C++ code,  are very sensitive to interruptions. I find that when I am interrupted during such activity, say by a phone call, or by a co-worker asking me something, the net cost of the interruption is not just the amount of time I spend attending to the call or person. It’s as if I have a short term RAM in my head, and I have to re-load the entire context of what I was doing when I get back to it. And this can take a lot of time. What I like are large chunks of uninterrupted time, not several small chunks, even if they add up to the big chunk.

I recently came across a surprisingly lucid model for time management. The model consists of just two variables that together categorize the tasks we do roughly into 4 bins. The two variables are ‘Importance’ and ‘Urgency’. That is, a task has an importance score, and an urgency score. To simplify even further, imagine that each of the two variables is just a binary variable: that is, a given task is either important or not, and either urgent or not.

An urn contain balls of two colors, white and black. A ball is drawn at random, and then put back in the urn along with a new ball of the same color. This process is repeated  many times. What is the ratio of white balls to black balls in the urn after tries? What is the ratio as ? The answer depends upon the initial number of white and black balls of course.

A word is not the same as the thing it represents, only a representation of it, meant to convey information about it. For e.g. the word ‘Castle’ is not the same as a Castle. This is obvious. Similarly, a map of a place is not the same as the place itself, it is only a map of it. This is also obvious.

The past few weeknights have been spent solving puzzles from Martin Gardner’s books, which I really enjoy. I just came across a book by Peter Winkler, whose name I had heard before in talks by Muthu. After reading a few of the puzzles on Amazon’s look inside preview, this book is too hard to resist buying. Also, here [PDF] is a beautiful set of 7 puzzles compiled by Peter Winkler on the occasion of a remembrance for Martin Gardner in 2006.  Other places I have found good puzzles recently include this page maintained by Gurmeet Singh Manku.

1. Both fields benefit from rigorous quantitative modeling for tasks such as detecting patterns and anomalies.
2. Both financial trading and security operate in an adversarial environment. In finance, the adversary is the ‘market’, i.e. the rest of the participants. In security, the adversary is the set of attackers.
3. Because of the adversarial environments, simple models do not work for very long, because the adversary evolves in response to actions taken by the other party, and it is hard for a model to capture the direction in which the adversary will evolve. Therefore both fields require that models be updated. Models are built using training data . The challenge therefore is to use the right mix of recent data and longer term historical data. How to do this is not obvious in both fields..
4. Game theory is a useful tool for modeling problems in both fields because of the adversarial nature of the field.
5. Modern financial instruments, apart from serving as investment vehicles, are designed for mitigating risk. The business of selling information security products or services is also one of mitigating risk — risk of information loss. There is no such thing as perfect security. Instead, organizations allocate an amount of money they consider appropriate to meet their risk appetite.
6. One difference is that trading in financial markets often has the ‘self fulfilling prophesy’ property, i.e. it can act as a positive feedback system (if a certain fraction of people with opinion that the price of a security is likely to fall, sell their holdings, the rest start thinking its probably a good idea to sell, and the end result is that the price does fall), whereas there doesn’t seem to be an equivalent in cybersecurity.

I have been thinking quite a bit about the best language to write machine learning algorithms in. While this depends on the exact algorithm in questions, there are certain constructs and tasks that show up in many algorithms. As I work through this, I’ll publish my notes here on this blog as I go along.

One of the problems for practitioners (as well as for researchers) of machine learning is that there is no well defined ‘frontier’ of machine learning algorithms that perform ‘best’ in a given problem domain. Even though there are some guidelines as to what is likely to work well in a given setting, this is not guaranteed, and often other approaches outperform well known approaches. In fact a large number of papers at machine learning conferences seem to be based on this kind of surprise (‘look, I tried an autoencoder on this problem and it outperforms the algorithms people have been using for decades!’). It is hard to have a universal frontier of this type because much of the ability of a machine learning algorithm depends upon the structure of the data it is run on. For this reason I was very happy to come across MLcomp.org, a website that allow people to upload algorithms (coded up in any language), and datasets, and compare the performance of their algorithm on all the datasets in their system, as well as the performance of any of the algorithms in their system on one’s dataset. This is immensely useful  because it serves as an empirical frontier of the performance of machine learning algorithms on different types of datasets. MLcomp connects to computational resources hosted on a standard Amazon EC2 linux instance, allowing users to test algorithms on datasets. And it is free.

Getting one’s hands dirty with applying machine learning theory to a real world dataset is really quite different from simply understanding the theory behind machine learning algorithms. Often, the experience of learning a regressor or a classifier from real a world dataset goes something like this: You have a nice big dataset. You have cleaned it up, normalized it and are ready to apply your chosen algorithm on the dataset in your chosen programming language/statistical computing framework. You find that the generalization error of the model you have learnt is really poor. What do you do next? You can chose a different learning algorithm, one that is more complex, one that is less complex. Or, you can try to supply more training data to the same algorithm in the hope that the generalization error performance improves. What you do next largely determines whether or not you are going to succeed in learning well from the dataset.

Gradient descent is used in a bewildering range of supervised machine learning areas as an optimization method to ‘fit’ a model to training data. Its use is obvious when the objective function being optimized (which is often some type of average error over the training set) is convex in the variables of optimization (which are usually the free parameters of the model one is trying to fit). However, gradient descent is (somewhat surprisingly) also used when the objective function surface is not convex! For example, in training a neural network using the back-propagation algorithm, the free parameters of the network are updated using a stochastic gradient descent over the error function surface, which is non-convex because of the non-linearities introduced by non-linear sigmoid/other neurons. Surprisingly, gradient descent seems to work fine. The reason for this is that when employing stochastic gradient descent, the weight updates are affected by noise in individual data points (this noise tends to get averaged out in batch (conventional) gradient descent), which provides the opportunity to escape from local optima wells in the objective-function surface. Due to the nonlinear sigmoid functions, the error surface typically contains many local minima wells, as in the figure below, and these minima as very close to each other. Therefore, even if one is ultimately stuck in a local minimum, it is often not too poor compared to the global minimum.

During the last 3 months, I have been constantly surprised and impressed by the recent achievements of neural networks. In particular, convolutional neural networks (see the work of Yann lecun) are currently the only technique that allow real-time object recognition using video input, with reasonable performance. Another piece of neural networks magic that I have been delighted by recently is autoencoders. In particular, a 2006 paper [PDF] in the journal Science by Ruslan Salakhutdinov and Geoffrey Hinton shows how multi-layer autoencoders (also called ‘deep autoencoders’) can be used to learn non-linear relationships. Yet another cool use of neural network that I recently came across is: paraphrase-detection on long sentences using recursive autoencoders — the problem here is to detect, given two sentences, whether they are the same (or close enough) in meaning or not — Here is the paper by Richard Socher, whose talk at NYU is where I first heard this stuff.

Peter Norvig is, by now, well known to have stressed in ‘The Unresonable Effectivenes of Data‘ that “a decent learning algorithm with tons of data can do much better than a very advanced learning algorithm and little data”.

With the words Steve, Jobs and Apple removed.

The IPv4-heatmap is an awesome little program created by Duane Wessels. It allows the visualization of the entire 32-bit IPv4 address space in 2-dimensions, using the idea of a Hilbert curve, a type of space-filling curve, which are fascinating constructs in and of themselves. Here is an image from Wikipedia showing an iterative process to create higher order Hilbert curves from lower order ones.

A research challenge on semi-supervised feature learning, posted by D. Sculley of Google Research and hosted on Kaggle just ended this past Monday. The goal of the competition was to learn a collection of 100 features from a small amount of labelled data (50K points) and a large amount of unlabeled data (1M points) in a 1M dimensional space. The data in the original 1M-dimensional space was very sparse. The winning entry didn’t use the unlabeled data at all! This was a surprise to me because I was convinced that it would be possible to better by learning a low dimensional feature representation at all. The winning strategy is described by one of its authors here.

I spent the day at the annual machine learning symposium organized by the NY academy of sciences. The keynotes were by Léon Bottou, Yoav Freund, and Stephen Boyd. In addition, there were ~30 posters and a number of short talks by some of the poster presenters. I enjoyed Stephen Boyd’s keynote the most. He talked about a method for decoupling convex optimization problems for performing distributed machine learning with data sets that have a very large number of features and/or training samples. This is particularly relevant to the cluster/parallel computing paradigm.  Although I used his textbook in grad school, it was the first time I head him speak. His talk was lucid, entertaining and seemed effortless.

A research challenge on semi-supervised feature learning, posted by D. Sculley of Google Research and hosted on Kaggle just ended this past Monday. The goal of the competition was to learn a collection of 100 features from a small amount of labelled data (50K points) and a large amount of unlabeled data (1M points) in a 1M dimensional space. The data in the original 1M-dimensional space was very sparse. The winning entry didn’t use the unlabeled data at all! This was a surprise to me because I was convinced that it would be possible to better by learning a low dimensional feature representation at all. The winning strategy is described by one of its authors here. Although I didn’t participate, I wanted to try building a deep autoencoder to lower the dimensionality. This Science 2006 paper by Hinton and Salakhutdinov addresses this very problem. This paper came up with a method for better training of deep autoencoder architectures, by training each RBM layer-by-layer, instead of doing backprop on the entire network end to end. The paper has a number of neat examples of high dimensional data with low inherent dimensionality, and the authors show how nicely their autoencoders manage to recover the low dimensional features better than other popular methods such as PCA, locally linear embedding and multi-dimensional scaling.

1. Intel has decided to shut down its lablets in Seattle, Pittsburgh and Berkeley! This is old news apparently, but I just learnt of it.
2. I have been a lot of thinking about the best model for workspaces. Some of the models individual offices, cubicles, and clusters of desks. At WINLAB, we had low-walled cubes. Richard Hamming famously stressed on the importance of having one’s office-door open if working in a research lab with individual offices. Here is a nice post on the subject from Matt Welsh who recently moved from being a professor at Harvard to working at Google. At the AT&T security research group where I work, we use a open collaborative workspace with clusters of desks and I can see that it is more productive than the cubicles at my erstwhile grad school lab.
3. A set of math puzzles, courtesy Gurmeet Singh Manku.

My paper titled ‘ProxiMate: Proximity-based Secure Pairing using Ambient Wireless Signals’ has been accepted at the 9th Annual International Conference on Mobile Systems, Applications and Services (ACM Mobisys) to be held at Washington D.C.. The paper is about how existing wireless signals, such as FM radio and TV signals, can be used by radios in close proximity to generate a shared secret, and then use that secret to communicate securely. By building a shared key in this manner, it is hoped that the problem of identity spoofing and eavesdropping on wireless links can be addressed. The principles at work in ProxiMate are: (i) Small-scale fading: the wireless channel between a distance RF source (such as an FM radio tower) and a receiver, behaves as a random process, thereby serving as a source of randomness, and (ii) receivers that are within half a wavelength of each other can observe highly correlated (but not identical) versions of these random processes, allowing wireless devices in proximity access to a shared source of common randomness that is not available to any sufficiently distant adversary. ProxiMate is a proof of concept system built on software-defined radio and evaluated using ambient FM and TV signals. It is intended to be information-theoretically secure — meaning, the key generation phase does not need to assume a computationally bounded adversary — as opposed to say, Diffie Hellman, which must assume a computationally bounded adversary in order to guarantee that the observations available to the adversary will not allow it to compute the key.

My paper titled ‘ProxiMate: Proximity-based Secure Pairing using Ambient Wireless Signals’ has been accepted at the 9th Annual International Conference on Mobile Systems, Applications and Services (ACM Mobisys) to be held at Washington D.C.. The paper is about how existing wireless signals, such as FM radio and TV signals, can be used by radios in close proximity to generate a shared secret, and then use that secret to communicate securely. By building a shared key in this manner, it is hoped that the problem of identity spoofing and eavesdropping on wireless links can be addressed. The principles at work in ProxiMate are: (i) Small-scale fading: the wireless channel between a distance RF source (such as an FM radio tower) and a receiver, behaves as a random process, thereby serving as a source of randomness, and (ii) receivers that are within half a wavelength of each other can observe highly correlated (but not identical) versions of these random processes, allowing wireless devices in proximity access to a shared source of common randomness that is not available to any sufficiently distant adversary. ProxiMate is a proof of concept system built on software-defined radio and evaluated using ambient FM and TV signals. It is intended to be information-theoretically secure – meaning, the key generation phase does not need to assume a computationally bounded adversary – as opposed to say, Diffie Hellman, which must assume a computationally bounded adversary in order to guarantee that the observations available to the adversary will not allow it to compute the key. On a side note, D.C. is one of the more boring cities to have a conference once you have done the museums circuit. Anyhow, looking forward to it!

I suspect one of the problems in the health care system in America is information asymmetry. The moment a customer hands over an insurance ID to a doctor or hospital, the clinic knows a significant amount of information about the patient. The clinic knows the patients health history, financial situation and the type of insurance plan he has. The average patient knows almost nothing about the internal working of the hospital. Try to think about how many bits of information the clinic possess about the patient, and how many bits the patient possess about the clinic. From a purely rational point of view, it may be in the best interest of the clinic to overcharge the patient for services he doesn’t really need, knowing that his insurance will cover it. Even if the clinic gets caught doing this once in a while, the odds of getting caught may be low enough that the clinic may decide to pursue such a policy in the long run.
One simple change that can be made is: do not provide insurance information about individual patients to the healthcare provider. This can be done by placing a government body as a liaison between the health care provide and the insurance companies. In this model, the hospital submit the bill to the government body and this body follows up with the insurance company. The hospital/clinic and the insurance company never interact directly.
Another way to disincentivize misbehavior on the part of clinics might be to create a public, review-supported, ratings service, ala Yelp, for medical clinics and individual doctors. The problem with this is potential for false reviews and sybil attacks, which makes me wonder why apartmentratings.com seems to have so many fake reviews, while yelp seems relatively cleaner.Update: A large amount of medical records data has just been released by the Heritage Health Prize via Kaggle. While the intended purpose of this data is to host a competition to predict which patients are admitted to a hospital within 1 year of the time frame of the data, I wonder whether it could be used for other interesting investigations and verification of theories, such as the one above.

In the problem of communicating information from point A to point B, we are faced with the task of dealing with a noisy channel that sits between A and B and corrupts or distorts the signal fed into it. A and B can be points in time intend of points in space – for e.g. recording data on some medium, such as a compact disk. Our goal is to take information produced by a source, and map it to a signal that can be carried by our intended channel, in such a way that when this signal is fed into the channel at point A, the distorted version produced by the channel at point B can be used by us to faithfully recover the original information with little or no change in meaning of the original information. In solving this problem, we first try to understand the nature of distortion that the channel creates, and based on this knowledge, we design an appropriate mapping between the original information emitted by the information source, and the signal that is fed into the channel. This process is called encoding. Using the knowledge of the type of distortion produced by the channel, we can then use the distorted signal at B and map it to our guess of the original information emitted by the source. This process is called decoding. The study of how to create efficient encoding and decoding strategies for specific types of channels is called coding theory.
In machine learning, we are placed at point B and at point A is a source of information that is not under our control. There is no entity sitting at point A creating a mapping from the original information to a signal appropriate for the channel in order to better withstand the distortions the channel will produce. The channel between A and B is ‘nature’. We are faced without the task of figuring out the original information at the information source by observing the signal emitted by the channel at B. To do this, we attempt to learn a function that can correctly map the signal output by the channel at B to the original information at A.  In terms of the communication problem, we are attempting to learn the decoding rule in the communication problem above, even though we do not have prior knowledge about the nature of distortion produced by the channel. In supervised learning, we are given several input-output pairs of the channel, and we attempt to learn this function that correctly maps the output to the input. Once we have estimated this function, we apply it to estimate the original information for instances where only the output of the channel is known.

“Whenever I start working on a new problem, I never look a the literature in the area first.. that baises the mind. I try to attack the problem myself and then see the literature, only to discover that half of what I worked out has already been published. But that’s okay, there is still the other half!” – Godfried Toussaint at colloqium lecture at NYU.

Attended a meeting of the NY ML meetup. The speakers presented on the BIG DATA work happening at foursquare. I noticed that the speakers as well as the audience is heavily tilted towards programming rather than statistics/ml. Most questions were about hadoop, hive and mongo db. Hardly any questions about the statistical aspects. This could be because the audience understood the math behind recommendation systems quite well. One exception was the ‘cold start’ problem.

http://mi.eng.cam.ac.uk/~hy216/VoiceMorphingPrj.html

http://mi.eng.cam.ac.uk/~hy216/VoiceMorphingPrj.html Why this is so cool (and dangerous): Imagine that I have a large enough sample of your voice (if I have access to some of your phone messages, or voice chats, this is easy). I can then go and build a model of your voice. Using the technique in the papers above, I can then transform my voice into your voice in real time. This means that I maybe able to defeat a speaker-recognition/speaker-verification system, thereby breaking biometric systems that rely on voice for authentication. For example, if the biometric system asks me to speak a particular random phrase or sentence, I speak into a computer, that modifies my voice to sound like your voice in software, and then plays it back to the biometric system. Biometric systems should have 2 or 3 factor authentication – biometric alone are broken!

My work on mobile sensing for automotive parking applications has just been accepted to ACM Mobisys 2010 and I will br presenting this work at Mobisys in San Francisco in June 2010. The paper is about the design, implementation and evaluation of a mobile sensing system called ParkNet, for the purpose of harvesting in as close to real time as possible, information about the availability street-parking spaces in urban areas. ParkNet was recently featured in the MIT Technology review. It has just been covered by Rutgers Today, an organization within Rutgers University that produces news articles about promising research efforts within Rutgers. ParkNet proposes that sensors for sensing vacant street side parking spaces be made mobile (see this project trial that uses stationary sensors installed in the asphalt road, one sensor per spot, presumably at a huge cost) by exploiting vehicles that regularly comb city environment, such as taxicabs. ParkNet can be thought of as a compressive sensing system because it drastically reduces the number of sensors needed [with a corresponding dramatic decrease in overall cost], with a very small loss in spatio-temporal accuracy.

My Mobicom paper has officially been accepted – now that the several rounds of changes and formatting issues have been fixed (I was both surprised and amazed as the painstaking detail with which ACM perused the paper; IEEE standards fall pale in comparison).

The cover story on the latest issue of Nature talks about a study that tracked the locations of 100,000 cellphone users for six months without their consent. The best part is the article doesn’t even mention the location privacy issue associated with the study, which was conducted for the purpose of inferring upon people’s movement patterns.

I came across a company named Path Intelligence that is selling equipment to track consumer’s locations passively using their cellphone signals inside shopping centers, malls, etc. ostensibly for the purpose of tracking consumer behavior. Apparently, their ‘equipment’ is centered around the GNUradio platform and uses triangulation based schemes for localization. What is interesting to me is that:

Anonymity is a big deal these days. And it should be, because the proliferation of personal computing devices with multiple radio interfaces places individual privacy in question. Consider the problem of de-anonymizing the Netflix database released for the Netflix prize project. A recent paper from U. Texas showed that the records released as part of the database were not anonymous at all and given a little bit of side information, allowed easy identification of individual records in a simple way.

Here is a story I just saw on Slashdot about how cellphone companies give away location information to the police without a warrant for persons reported missing (which means they log location information of course):

I attended some interesting talks at the 3rd Rutgers-Helsinki PhD Student Workshop on Spontaneous and Pervasive Networking (phew!) today. In particular, a talk by Marco Gruteser reviewing location privacy for various applications caught my eye. Location based services have been much talked about and are expected to take off (any moment now) in a big way. This introduces the problem of preserving user-privacy. Marco talked about an interesting class of problems that deal with preserving the privacy of location traces. The idea is as follows: Each mobile client periodically transmits its location to a central server, which then forwards this information on to a application service provider (ASP) that provides some location-based service to the user. (Think DASH!) However, the user wishes to conceal its identity to the ASP. Hence we would like to make it impossible (or very hard) to infer the user’s identity from observing location updates.

Here’s an interesting video from Joshua Wright showing how a bluetooth headset can be eavesdropped on from a distance. The interesting thing is you only need a high gain antenna at the attacker’s end.