How to apply AdaBoost to more "complex" (non-binary) classifications/data fitting?

Question

In this article, Chris McKinlay says he used AdaBoost to choose the proper "importances" of questions he answered on okcupid.

If you haven't read and don't want to read the article, or are unfamiliar with okcupid and the question system, here's the data and problem he had: The goal is to "match" as highly as possible with as many users as possible, each of whom may have answered an arbitrary number of questions. These questions may have between 2 and 4 answers each, and for the sake of simplicity, let's pretend that the formula for a match% $\ M $ between you and another user is given by

$\ M = Q_a/Q_c $

Where $\ Q_c $ is the number of questions you and the other user have in common, and

$\ Q_a $ is the number of questions you both answered with the same value.

The real formula is slightly more complex, but the approach would be the same regarding "picking" a correct answer (he actually used boosting to find the ideal "importance" to place on a given question, rather than the right answer). In any case, the point is you want to pick a certain value for each question, such that you maximize your match% with as many users as possible - something you might quantify by the sum of $\ M $ over all users.

Now I've watched the MIT course on AI up to and including the lecture on boosting, but I don't understand how you would apply it to a problem like this. Honestly I don't even know where to begin with choosing rules for the weak learners. I don't have any "rules" about what values to choose for each question (if the user is under 5'5, choose A, etc) - I'm just trying to fit the data I have.

Is this not the way boosting is supposed to be used? Is there likely some other optimization left out of how he figured this out?

Answer 1

AdaBoost is a supervised learning method; it starts with a table of 'correct' answers and generates a predictive model for a target, which is known. It is then possible to inspect this model to figure out how it works, what it judged was more important. With that in mind, here is my guess for what he did:

First, he created a training dataset. The dataset was created, according to the article, like this:

Now he’d do the same for love. First he’d need data. While his dissertation work continued to run on the side, he set up 12 fake OkCupid accounts and wrote a Python script to manage them. The script would search his target demographic (heterosexual and bisexual women between the ages of 25 and 45), visit their pages, and scrape their profiles for every scrap of available information: ethnicity, height, smoker or nonsmoker, astrological sign—“all that crap,” he says.

To find the survey answers, he had to do a bit of extra sleuthing. OkCupid lets users see the responses of others, but only to questions they’ve answered themselves. McKinlay set up his bots to simply answer each question randomly—he wasn’t using the dummy profiles to attract any of the women, so the answers didn’t mat­ter—then scooped the women’s answers into a database. "

So he used python scripts to collect lots of information! At the end of this, he had a table of data, where each row had three pieces of information: - A bot's answer to all the questions, and their weights - A woman's answer to all the questions - Their match percentage.

On this, he could use AdaBoost to create a predictive model, predicting the match percentage from the available information. The weak learners were probably decision stumps, greedily choosing one variable at a time to split on, that's the standard that people refer to when talking about AdaBoost.

Once the predictive model, was in place, it could be used for optimization - determining which weights to put on the questions when holding all other variables constant, maximizing the average match percentage to women in his target audience.

Of course, this is just a guess. The article doesn't have much detail. But it's a potential way to use AdaBoost for that purpose.

Answer 2

My best guess:

After three weeks he’d harvested 6 million questions and answers from 20,000 women all over the country.

I assume that we could collect both what the women answered, what answers they would accept and the importance they attribute to the question. This is the training set.

He picked out the 500 questions that were most popular with both clusters.

This is the feature selection.

The loss function to be minimized is could be something like the negative sum of (logarithms of) the match percentages

$m(x,s,w, y_i, t_i, v_i)$

between his answers $x$ (a vector of length 500), the answers he accepts $s$, the importances $w$ he attributes to each questions, the $i$'th woman's answers $y_i$, the answers $t_i$ she would accept and the importances she assigns to them $v_i$.

He’d already decided he would fill out his answers honestly

meaning that $x$ and $s$ are fixed, only $w$ is adjusted to minimize the goal function.

If the match percentage were something simple like 'number of questions which both answered the same way times your importance assigned to the question', a simple 'give most importance to the question you answered the same way as women in your preferred cluster and zero importance to other questions' should maximize this. However, the match percentage function is more complicated.

One would start with equal importance assigned to all questions. Then calculate the contribution of each question to the overall loss function: questions $j$ for which his answers do not match many of the women's answers will get a reduced weight in the next round and the weight of well matching questions will be increased (I would have to think about how the weight update would look in detail though).

Note that the question relevances in the vector $w$ can only take on a discrete set of values (0, 1, 10, 50, 250) making it a discrete optimization problem and thus potentially NP-hard. In practice, I would allow the weights $w$ take on any real value between 0 and 250 and then round to the nearest allowed value in the end.

(Disclaimer: I have never used OkCupid)