Week 27-28: Writing

Hello all.

The past two weeks since returning from spring break, I have been working with the grad student to write the vis paper. It is due next week on Friday. A couple of the undergraduates (along with my CREU peer, Diana) have stayed on to make changes to the RanKit application to make it better for publication.

Briefly, I'll share a couple things I wrote in the past two weeks that have gone into the paper. First, I'll share some equations that describe the amount of information collected from the different build tools for each unit of user effort. Second, I'll give three use cases that describe why these tools might be used.

Equations

The ranking algorithm is based on pairwise comparisons. We will assume that the user's input is meaningful and that there exist no cycles in their rank (e.g. user says Toy Story 1 > Toy Story 2, Toy Story 2 > Toy Story 3, and Toy Story 3 > Toy Story 1). The collection of all possible rankings is a directed acyclic graph. For n objects, this is (n^2 - n)/2 pairs. If there are 100 objects, this translates to 4950 pairs. For purposes of this argument, let's say that an "optimal" preference elicitation is one where n log(n) pairs are generated. (This can be thought of as the point at which the user's preferences start to "fight" the model. More information does not contribute to the model, and user preferences will be less reflected in the output model. Less information, however, and the model is uncertain. Multiple rankings could exist that explain the user's preferences). In a pool of 100 objects, this means 664 pairs must be generated.

Pairwise

Pairwise comparison is the most simple and directly related to the model. For every pair of objects the user specifies, 1 additional pair is known for the model. In other words, 664 unique pairs must be created in order to achieve the optimal amount of information. Some could be said about the transitive property: if a user says Toy Story 1 > Toy Story 2 and Toy Story 2 > Toy Story 3, then one can assume that Toy Story 1 > Toy Story 3. So in reality, the number of unique pairs might be slightly less.

List 

List comparison gives the most information for the least amount of user effort. For every object added to a preference list of n objects, n new pairs are learned. This grows at a rate of (n^2 - n)/2. In a pool of 100 objects, 37 must be ranked to acquire optimal information.

Categorical 

Categorical comparison might make sense to a user. It gathers more information from the user than pairwise, but not as much as in list. In fact, unlike pairwise and list, there is a restricted amount of information the model can learn. In a pool of 100 objects, if the user splits all 100 objects among the three categories, only 3267 pairs can be learned. This is because objects within the same category are unaware of each other (if two movies are in the Medium category, no pairs can be learned between them). For every object added, 2/9n^2 - 1/3n ranking pairs are generated. 55 objects must be ranked to achieve the optimal amount of information.

Use Cases

List

A major tech company is looking to expand by building a second headquarters. They want to know where to build in order to attract the most talent as well as save money with state business incentives. They use a publicly available dataset with information as to the number of tech employees, the average starting salary, as well as state tax rates and estimated discount rate for businesses. They use RanKit to input the top states in the US according to number of tech companies. When they calculate their rank, they notice that average starting salary is heavily weighted in the model and that border states are ranked higher than mid-country states.

Categorical

Beth is a high school junior with plans to attend college. She is trying to decide where to apply. She has had the opportunity to tour several schools around her hometown and feels confident making judgments on them. Beth uses the publicly available Scorecard dataset that contains diverse attributes about colleges across the US. She knows she really liked some of the colleges in her area, felt some were ok, and despised others. She ranks these colleges into the high, medium, and low categories using the Categorical view tool. When she clicks "Rank!" she finds that a major predictor of her preferences was the number of undergraduates. Upon further reflection, she decides that number of students doesn't really matter to her. She remembers a smaller university that she forgot to add to the ranking that she really liked, so she returns to the build view to add more preferences. The build view suggests several universities that would help the quality of the ranking for which Beth could add more information. Beth chooses to research these colleges in more depth to form her opinion.

Pairwise

Carl is an active member on a fantasy football league. He wants to make targeted predictions as to which team will be most successful over the season. He uses the Pairwise view on RanKit with a dataset on post-game statistics to encode which teams won and lost over the last week.

Comments

Post a Comment

Popular posts from this blog

Week 31: Datasets for fairness

This week, Diana and I looked for some datasets on which to evaluate our fairness criteria. This is no simple task. For one, the datasets need to be large enough to be split into training, calibration, and testing sets. Second, there needs to be some protected group attribute like sex, race, or age. Third, there needs to be some outcome ranking as well as some truth value. The truth is often the hardest attribute to find. In this post, I introduce some of the datsets we decided to use. I try to identify each of the necessary features that we need to properly test our fairness criteria. COMPAS The COMPAS dataset is an obvious choice because it is well ingrained in the literature about fairness. It has 18,000 observations (n=18000) and 1000 attributes (k=1000). Protected groups can be sex (81/19) or race (51/49). The outcome attribute can be the recidivism score, the score used in court that represents the risk that the accused will commit another crime. The truth attribute is a li...
Read more

Week 32-33: Wrapping up

Hi all. This is my last blog post for this project. The last few weeks, we spent little time working on the project and instead focused on finishing up our classes. To be honest, we lost some motivation after finishing the paper, and we've been reluctant to start up new tasks so close to the end of the year. In this post, I'd like to talk about some of the things I've learned in this project other than what we found in our research. This post is really more a service to myself; to help me reflect on this past year and what I've learned. When I started this project, I didn't understand how research in computing worked. My exposure to research had been more biology/clinical, in which research involved setting a hypothesis about some protein, designing an experiment with positive and negative controls, and then running the experiment repeatedly until confident in the results. In computing research, my experience has been of two varieties: reading papers and proce...
Read more

Week 30: Returning to Fairness

With the LineUp paper submitted, it's now time to return to the fairness problem we were working on before. As a bit of a refresher for you and for me, I'll review what we've done with fairness so far and what remains to be done. Fairness in Ranking Up until now, the literature regarding fairness has focused on fairness in classification. As an illustrative example, consider fairness in hiring practices with repect to applicant sex. A job opening might receive 100 applicants evenly split into 50 males and 50 females. If males and females are equally capable of doing the job, then you might be concerned to see the hiring company mostly interviewing male applicants. To evaluate fairness, you would compare each applicant's capability (capable of performing duties, not capable) to their outcome (interviewed, not interviewed). In a completely fair scenario, the same proportion of capable applicants from each sex group would receive an interview. Small deviances from this...
Read more