-
finish 100k SHC-MMMF MovieLens experiments -
head-to-head comparison vs. CR's code -
plot of regularization path (loss vs. regularization as C varies) -
make some plots with 100k ML data (see if this objective looks convex or not) -
prep 1M MovieLens data, run SHC-MMMF experiments - prep BookCrossing data, run SHC-MMMF experiments
- prep EachMovie data, run SHC-MMMF experiments
- write derivative code for rating/workshop experiments
- compare primal optimization results to csdp results (how many entries are predicted differently?)
- Background & Introduction
- Why? As in pro sports, we want to determine who is "best." Also, given a future matchup, we'd like to know who is going to win.
- Why is College special? In pro sports, the overall quality is more consistent, the number of teams is lower and there is good coverage in terms of contests. A very good way to rank teams would be to have one giant round robin. If you think of contests as entries in a matrix, this would be a dense matrix. In college sports, the contest matrix is very sparse. There are 332 Div I-A basketbal teams, but each team only plays only ~30 games, a majority of those within their own conference. There are over 100 Div I-A football teams; each team plays about 12 games. Many of those games are vs. teams with a significantly different level of skill. E.g. 12 out of Illinois' 33 games were played against teams out of the top 100. Win-loss records are somewaht irrelevant. It's very important who you play and where you play. College scheduled tend to be imbalanced both in terms of quality-of-opponent and home/away (some teams play all their difficult games away---a significant disadvantage).
- A Simple "Model"
- Possibly the simplest idea for ranking teams is alpha*(your winning percentage + (1-alpha)*(your opponents' winning percentage).
- Why is this a bad way to rank teams? Who you play can have as much influence on your score as how you play! A loss against a good team can help your score. A win against a bad team can hurt your score.
- SIAM Review
- James Keener published an article in the SIAM (industrial and applied math) Review on ranking football teams. His initial model: s_i = mean_j(A_{ij}s_j), or As = s, where A_{ij}=1 if team i beats team j, 0 otherwise. You get a score equal to the average of those teams you defaeat (with 0 averaged for a loss). This model minimizes squared loss. This shares similarities to the "simple model". A team's score is (winning percentage)*(average score of beaten teams). Same odd qualities as the simple model. Later in the paper, Keener adds regularization to his model, and effectively ends up with regularized least squares classification.
- Classification
- I think it's great when there are applications that are extremely ripe for Machine Learning. I think it's even more fun when there's such a keen interest from the general public, but no one has yet done it right. I think sports is a huge application area that is ripe for Machine Learning.
- Why Classification? Here's the simple answer: each game is an event with two possible outcomes. Rating teams is equivalent to trying to predict who will win.
- How do we set up the classification problem? I think this is the major insight---everything else follows like dominos. There is a feature for each team. For each game, the home team's feature is +1, the visiting team's feature is -1; the label is +1 if the home team wins, -1 if the visiting team wins. Home court advantage simply requires the addition of a "bias" feature (+1 for all games).
- The important question is: what classifier should we use?
- Loss Functions
- I'm going to take a "loss + regularization" approach here. No Naive Bayes, no Decision Trees, etc. I want to do stick to linear classification because that will give maximum clarity and understanding of how the teams compare to each other.
- In classification, we generally want to minimize the number of mistakes. Modern classification theory says that it works best if we bound the number of mistakes with a convex function. This guarantees that any local optima are global. Modern classification theory also applies a weight penalty. In the SVM separable framework, we want to maximize the margin between the decision boundary and the examples. Equivalently, minimize weight norm for a fixed margin.
- Support Vector Machine. Hinge Loss. (1-z)_+. Direct upper bound ton zero-one loss.
- Logistic Regression. Logistic Loss. 1/(1+exp(-z)). Smooth-derivative upper bound to zero-one loss.
- Least Squares Loss. (z-1)^2. Tries to push examples exactly distance 1 away from boundary.
- Smooth Hinge Loss. Just like Hinge, except (z-1)^2/2 within (0,1).
- Problem with Logistic: poorly rates undefeated teams and teams without any wins; such teams can easily get ratings much higher/lower than they really should.
- Problem with Squared loss: your score is average score of teams you play, modified by +1 for a win, -1 for a loss. i.e. average opponent ratings, add average outcome (+1 win, -1 loss).
- Hinge loss-like losses are best because they ignore games that are lop-sided and have the expected outcome (difference of at least 1). Also, a team's rating is well-defined and nicely bounded if they are undefeated/never-won-a-game: +1 or -1 difference from best/worst team played.
- Fun March Maddness Factoids
- Does any sub rank 12 team have a chance to make it to the Sweet 16? New Mexico (0.86/#39) has the best shot. They would need to defeat Villanova (1.16/#19) and Florida (1.20/#18).
- Who got screwed in the seeding?
- Louisville (#8) should have received the #3 Albuquerque seed. Gonzaga (#12) got it.
- Boston College (#6) should have received the #2 Chicago seed. Oklahoma State (#10) and Arizona (#9) were placed ahead of them.
- New Mexico (#39) should have received the #9 Syracuse seed. Iowa State (#39), NC State (#43) and N. Iowa (#45) were placed ahead of them.
- Cincinnati (#21) should have received the #6 Austin seed. Utah (#25) got it.
- Iowa (#24) received the #10 Austin seed. Utah (#25), Stanford (#35) and Miss. State (#38) were placed ahead of them.
- The #5-#11 Albuquerque seeds should have been (respecitvely) Pacific (#22), West Virginia (#26), Texas Tech (#28), Pittsburgh (#29), UCLA (#30), Georgia Tech (#31), and Creighton (#34). The real seeding was (respectively) Georgia Tech (#31), Texas Tech (#28), West Virginia (#26), Pacific (#22), Pittsburgh (#29), Creighton (#34) and UCLA (#30).
- S. Illinois (#23) should have recevied the #6 Chicago seed. LSU (#27) got it.
- Utah State should have received the #13 Chicago seed. Pennsylvania (#107) got it.
- What upsets does the model predict?
- Nevada (#36, #9 Chicago) will defeat Texas (#37, #8 Chicago)
- Arizona (#9, #3 Chicago) will defeat Oklahoma State (#10, #2 Chicago)
- Wake Forest (#2, #2 Albuquerque) will defeat Washington (#3, #1 Albuquerque)
- Kansas (#7, #3 Syracuse) will defeat Connecticut (#14, #2 Syracuse)
- Most competetive games (first 3 rounds, assuming games go
according to predictions):
- Texas (#37) vs. Nevada (#36) [Chicago]
- Pacific (#22) vs. Pittsburgh (#29) [Albuquerque]
- Cincinnati (#21) vs. Iowa (#24) [Austin]
- Stanford (#35) vs. Miss. State (#38) [Austin]
- Syracuse (#15) vs. Mich. State (#17) [Austin]
- Flordia (#18) vs. Villanova (#19) [Syracuse]
- Washington (#3) vs. Louisville (#8) [Albuquerque]
- Oklahoma State (#10) vs. Arizona (#9) [Chicago]
- Illinois (#1) vs. Boston College (#6) [Chicago]
- Kansas (#7) vs. Connecticut (#14) [Syracuse]
- Kentucky (#11) vs. Oklahoma (#13) [Austin]
| Optimizer | Line Search | Delta | Objective | Elapsed Time (secs) |
|---|---|---|---|---|
| GradDesc | Discrete | 6.681e+04 | 5.929e+03 | 5.5 |
| ConjGrad | Discrete | 1.430e+03 | 4.643e+03 | 6.5 |
| Optimizer | Line Search | Delta | Objective | Elapsed Time (secs) |
|---|---|---|---|---|
| GradDesc | Backtrack (obj) | 6.005e+04 | 5.929e+03 | 6.7 |
| GradDesc | Backtrack2 (grad) | 4.217e+02 | 4.802e+03 | 10.1 |
| GradDesc | Secant | 4.603e+04 | 4.710e+03 | 6.9 |
| ConjGrad | Backtrack (obj) | 1.309e+04 | 4.615e+03 | 7.7 |
| ConjGrad | Backtrack2 (grad) | 9.946e+03 | 1.203e+04 | 10.1 |
| ConjGrad | Secant | 1.418e+02 | 4.550e+03 | 7.3 |
- Backtracking - Start at alpha=1, do alpha/=gamma until point of objective/gradient decrease is found
- Discrete - Assume function convex along direction; find local minimum of objective/gradient among points: ..., gamma^2, gamma, 1, 1/gamma, 1/gamma^2, ...
- Secant - Use second order approximation
W*V'*x = b
V'*x = (W'*W)^{-1}*W'*b
x = (V*V')^{-1}*V*(W'*W)^{-1}*W'*b
But, this is not helpful b/c W'*W is a (# columns)^2 matrix and V*V'
is a (# rows)^2 matrix. i.e. we'll still have to invert a "big"
matrix.
- Write-up and implement log-quadratic frequency model (what about document length?)
- Work out math for infinite binomial mixture model
- Run Alex's code using movie lens data (4-CV), figure out the formula to go between t and C, see if results match up (compare resulting matrices and/or compare errors)
- Iterative MMMF. Implement approximate SVM like in the Zhang/Oles (2001) paper; use MMMF rating loss function.
- Revise writing to indicate that idea of mixtures is old; our innovations: (1) use informativeness score for NED, (2) new type of score (log-odds ratio), (3) IDF/mixture score combination.
- Compare against z-measure (parameters of trained mixture), x^I-measure (doc/freq stats only) and Residual-IDF (doc/freq stats only; RIDF is IDF minus (freq. rate times # documents (=expected IDF)))
- Idea of using burstiness/mixture model to identify topic-centric words needs to be put in context of past work (e.g. Church/Gale, Bookstein/Swanson, Harter).
- First reviewer doesn't like the fact that classification threshold is chosen on test data. I should let classifier chose threshold, or set it based on the training data. Optimal might be to compare the two methods (classifier setting vs. min training error setting).
- Need to use a good classifier, e.g. CRF or Cohen's semi-markov CRF
- First reviewer thinks that fact that an informativeness measure may help with identifying named entities needs motivation.
- First reviewer notes that IDF also does substantially better than baseline (is mixture score really providing any benefit?)
- Reviewer #3 wants better intuition for equations (2) and (3)
- Reviewer #3 wants to see TF included with IDF
- Reviewer #3 concerned that we did not use words as features for NEE; seems (s)he is confused (many of the comments indicate a lack of understanding)
- Need to make clear that ^2 for IDF and Mixture is squared, not a footnote.
 |
- m_{x_i \to f_j}(x_i) = \frac{P(x_i)}{m_{f_j \to x_i}(x_i)}
- m_{f_j \to x_i}(x_i) = \sum_{x_k \not = x_i} \prod_{l \not = i} m_{x_l \to f_j}(x_l) f(x_1,\dots,x_n)
- P(x_i) = \prod_{f_j|e(i,j)} m_{f_j \to x_i}(x_i)
- Iterate over the examples (for co-ref resolution, each document is an example)
- For each example, determine the best labeling according to the model with current parameters
- If true label and predicted label differ, update parameter vector according to differences in feature values. In the case of co-ref resolution, we'd sum over feature differences for all edges that are labeled incorrectly.
- Handout
- To give audience idea of the problem of co-reference resolution. I've underlined some of the noun phrases relating to people.
- Audience should note that resolving proper nouns vs. resolving pronouns are somewhat distinct tasks. Proper nouns largely resolve according to string similarity. Pronouns depend much more on local sentence structure.
- Introduction/Outline: movitavion for hybrid model, why we want a full probabilistic model (marginal objective), sorry, no results to report.
- Co-reference Resolution is composed of (1) Clustering noun phrases, and (2) determining the entity to which each cluster refers. Most work (including ours) simply deals with #1 and assumes that #2 is easy.
- Two main frameworks for grouping noun phrases
- Spectral clustering---maximize internal similarity, minimize similarity to other clusters.
- Classification---determine the antecedent (if any) for each noun phrase.
- Classification is best suited to resolving pronouns. Pronouns almost always refer to another noun phrase in the text. Most important resolution issue is to which NP is this pronoun most closely associated? Appropriate question: to which NP does this pronoun refer?
- Clustering is best suited to resolving proper nouns. Internal consistency is highly important for proper nouns. Consistency can't be achieved only by looking at pairwise relations.
- McCallum/Wellner provide an excellent consistency exmaple: "Mr. Powell" -> "Powell" -> "she". They use a clustering-based model that yields excellent performance for proper noun phases. Model enforces consistency among cluster members by requiring that each member be compared to all others. But, overall performance is no better than state-of-the-art, indicating mediocre performance on non-proper NPs.
- Our claim: hybrid model would work best. Enforce intra-cluster consistency for proper nouns, use single antecedent to classify pronouns. How to do this?
- Simple approach. Train McCallum/Wellner model on proper noun data. Train decision tree on non-proper noun data. Use McCallum/Wellner model to group proper nouns. Use decision tree to determine resolution chains for non-proper nouns (which link with proper noun clusters). Viola! But, doesn't this seem a bit ad hoc?
- Our contribution: a new classifier that integrates with a fully probabilistic model of the problem.
- We use a mixture of experts to model the label for each
non-proper NP. Each NP that appears earlier in the text is an
expert. We use a softmax model (think multi-class Logistic
Regression) to determine which expert to select. The distribution
of a non-proper NP is a convex combination of the distributions of
NPs that come before it. That is:
P(y_i|y_{B_i},y_A,\vec x) = \frac{1}{Z_i} \sum_{j \in B_i} \exp(\vec w \cdot \vec f(x_i,x_j)) P(y_j|y_{B_j},y_A)Normalization constant is sum of softmax terms. Maybe one slide introduction to Logistic Regression? - Recall McCallum/Wellner model:
P(\vec y|\vec x) = \frac{1}{Z_{\vec x}} \prod_{i,j} \psi(x_i,x_j,y_{ij})This defines a joint model on the labels using pairwise potentials. Each pairwise potential is log-linear: \exp(y_{ij} \vec w \cdot f(x_i,x_j)). Include explanation of McCallum/Wellner? - Using Bayes Law, we can write joint as product of
McCallum/Wellner model and non-proper conditional/mixture
distributions (A = set of proper nodes, B = set of non-proper nodes):
P(y_i|y_{B_i},y_A,\vec x) = \frac{1}{Z_i} \sum_{j \in B_i} \exp(\vec w \cdot \vec f(x_i,x_j)) P(y_j|y_{B_j},y_A) - The good: assumptions we make for learning/inference are clear; we can use a single set of parameters between proper and non-proper NPs; stepping stone for max-margin approach; clear how to extend to marginal objective (joint optimization makes bad assumptions); how to use training examples for mixture of experts is clear (decision tree work tried many different ad hoc choices)
- The bad: learning mixture of experts is non-convex (non-convexity impossible to avoid for classification approach due to missing information); inference is non-convex (though, so is the McCallum/Wellner model)
- Need to include a slide on missing information---we don't know the "path" of antecedents. Decision tree work makes the assumption that link is always to most recent w/ same label.
- Learning: maximize joint or maximize product of marginals; either way, this can be done via gradient descent; EM could be used to recover antecedent information for non-proper NPs (though this would be learned implicitly via gradient descent anyway)
- Inference: again, non-convex, but mixture of expert distributions are likely to be highly skewed; any expert with 50% or more of the probability mass can be chosen w/o need to consider other assignments;
- referent -- something referred to; the object of a reference
- antecedent -- the referent of an anaphor; a phrase or clause that is referred to by an anaphoric pronoun
- denotatum -- an actual object referred to by a linguistic expression
- designatum -- something (whether existing or not) that is referred to by a linguistic expression
- anaphor -- a word (such as a pronoun) used to avoid repetition; the referent of an anaphor is determined by its antecedent
- x_1,...,x_n are the NP; y_1,...,y_n are the entity/cluster labels
- Model is fully connected, undirected graph, one vertex per NP.
- We use a Markov Random Field model where there is one potential per edge---one potential per pair of NPs. For nodes i and j, the potential is: \phi(x_i,x_j,\delta(y_i,y_j)).
- The joint probability of a set of labels is a product of all
the pairwise potentials:
p(y_1,...,y_n) = \sum_{i,j} \phi(x_i,x_j,\delta(y_i,y_j))
- Let the vertices be ordered: v_1,v_2,...,v_n
- Let there be a directed edge from each vertex to every other vertex with a higher index (e.g. v_3->v_4 exists, but v_4->v_3 does not)
- Distribution for a vertex is weighted sum of distributions of parents, plus constant delta probability of a new state. Weight on each parent distribution is exponentiated similarity.
- NP - noun phrase
- data - a set of documents with delimited NPs
- cluster - an exclusive set of NPs
- labeled data - data such that each NP is marked as belonging to a single cluster
- terminal - an NP that refers directly to an entity; it does not refer to another NP; we assume that, in the training data, the first NP in each cluster is the terminal.
- path - a sequence of NPs such that, except for the last NP, each NP refers to the next NP in the sequence
- tail - first NP in a path
- head - last NP in a path
- reference chain (RC) - a path such that the head is a terminal; each reference chain has a unique tail
- Framework
- Coreference resolution involves two separable tasks: (1) NP clustering, and (2) determining the entity to which each NP cluster refers. We are mainly interested in the first task.
- A terminal NP refers to an entity directly; a non-terminal NP refers to an entity via a reference chain.
- Our model is designed to make task #2 easier as it attempts to identify NPs that most directly refer to an entity (terminals). However, a drawback to our model is that if the training data does not designate terminals, they must be somehow inferred.
- Since forward refernces are rare in English, we make the assumption that non-terminal NPs refer to earlier NPs. This assumption identifies terminals in training data: the first NP in each cluster is the terminal for that cluster. This assumption can easily be relaxed; learning and inference simply become more computationally complex.
- We incorporate graph terminology to aid intiution. Each NP is a node; each reference is a directed edge. The entire graph is a forest; each cluster is a tree. A node is a terminal iff it has no outgoing edges.
- Each terminal serves as a cluster identifier; the head of each RC is a terminal, which identifies associates that NP with a cluster.
- Learning and Inference
- We use training data to learn parameters of a similarity score; this similarity score is used to infer a reference graph on unlabeled data.
- We define a similarity score between two NPs as a dot product of a feature vector and a weight vector; the feature vector is a function of the NP pair; the weight vector is constant.
- The unnormalized probability that an NP, $x_1$, refers to another NP, $x_2$ (that comes earlier in the text) is the exponentiated similarity. The unnormalized probability that $x_1$ is a terminal is constant.
- To learn the weight vector for the similarity function, we maximize the joint probability that the RC tails correspond to cluster anchors. We assume that an NP's distribution over RC tails is independent of other RC tails. [Herein lies a major difference between our work and DT work---we maximize the probability that each NP is more likely to refer to its cluster's anchor than other cluster's anchors.]
- Learning is a hidden information problem---we only know head and tail of each RC; we don't know how long RC is and we don't know the full path (though there some constraints). We use EM to simultaneously learn the parameters and fill-in the missing information.
- Once parameters are learned, we associate each NP according to its most likely reference chain. [Herein lies another major difference between our work and the DT work---our inference is not locally greedy]