I read the paper -by Enrique Amigo´ Julio Gonzalo Javier Artiles Felisa Verdejo A comparison of Extrinsic Clustering Evaluation Metrics based on Formal Constraints
http://nlp.uned.es/docs/amigo2007a.pdf
The paper evaluates various metrics for clustering. The authors list down the following required criteria for the constraints that contribute in evaluating a metric - (1) Each constraint should address a limitation of the metric. (2) For any metric, there should be an analytical way to prove whether the metric satisfies the contraint and (3) The constraint should discriminate between metric families.
Based on these criteria, the author suggest four constraints - (1) Cluster Homogeneity - a coarser cluster containing heterogeneous items have a lower score than finer clusters of homogenous items. (2) Completeness - Homogenous items should feature in the same cluster. (3) Rag Bag - Disorder in a noisy (heterogeneous cluster) is favored than in a homogenous cluster and (4) Cluster size vs. quantity - Small error in big cluster is favored to large number of small errors in small clusters.
On the basis of these constraints, the author compare four types of measures - (1) Set matching - Purity, Inverse purity (2) Counting pairs - Rand statistic, Jaccard coef, Folkes and Mallow FM, (3) Entropy based measures and (4) B-cubed
Set matching metrics fail on cluster completeness and rag bag as the bias is towards small clusters. Entropy based methods fail generally fail on rag bag. Pair counting satisfy both homogeneity and completeness, but don't address rag bag and cluster size vs. quantity. The b-cubed family of metrics satisfy all the four kinds of constraints.
In the focus paper, the distance between two clusters is represented by the sum of different clusterings for a pair of items. It may seem that only homogeneity and completeness are addressed over here. However, since none of the clusterings represent true clustering, constraints (3) and (4) probably are not required.
Wednesday, March 16, 2011
Friday, March 11, 2011
Pre-meeting post from Weisi Duan
I read the paper “Meta Clustering” by Rich Caruana etc. in 2006 ICDM. The paper describes meta-clustering which is mentioned in the focus paper. It also has lots of similarities to the focus paper and it seems that focus paper has taken some from this paper, eg. the similarity metric between clusterings. The Meta clustering procedure has been decomposed into 3 steps: 1) generate the base level clusterings; 2) define the similarity metric between the base level clusterings; 3) conduct the meta-clustering on the base level clustering using some clustering methods such as agglomerative clustering. The goal is to represent a meta-clustering of the base level clusterings to the user, so the user would spend less time going through all the base level clusterings to find the best one. For 1), random feature weights are assigned for clustering and PCA are conducted to remove correlated features. For 2), the percentage of pairs of instances that are treated differently (the pair being in one cluster in one clustering, and in two different clusters in the other) in two clustering is used as the metric.The evaluation is done on several data sets with user labels to calculate compactness and accuracy as performance measure. The main lesson from experiments, as the authors suggest, is that when the correct clustering criteria is not specified in advance, searching a single, optimal compact clustering is not appropriate since correctness criteria might not correlate strongly the compactness. This also serves to be the one of main motivations of this paper and the focus paper.
Wednesday, March 9, 2011
Pre-meeting comment Dong
Pre-meeting (Dong Nguyen).
Related paper A Method of Automated Nonparametric Content Analysis for Social Science, Daniel J. Hopkins, Gary King
Focus paper: General Purpose Computer-Assisted Clustering and Conceptualization, Justin Grimmer and Gary King
The related paper focuses on estimating proportions of categories (classes), instead of doing individual classifications (what is mostly done in computer science). They first review two existing approaches to estimate proportions: 1) sample a subset and hand label them to estimate the category proportions, 2) Do individual classification, and aggregate the predictions to calculate a proportion. They explain why both approaches have problems, and then propose two new methods. The first one applies existing individual classification techniques, but then estimates the errors per category and corrects the aggregated category proportions. The second one estimates proportions directly without doing individual classification. The problem can be framed as a regression problem and the class proportions are the regression coefficients. Because of computational and sparsity issues, they sample subsets of words, and estimate it for each set. The results are then averaged.
I think the paper gave a nice explanation of the goals and alternatives. Furthermore, it was interesting because I've never thought about estimating proportions instead of individual classifications, and now know why you would want to use other methods instead of just aggregation individual classification predictions.
Related paper A Method of Automated Nonparametric Content Analysis for Social Science, Daniel J. Hopkins, Gary King
Focus paper: General Purpose Computer-Assisted Clustering and Conceptualization, Justin Grimmer and Gary King
The related paper focuses on estimating proportions of categories (classes), instead of doing individual classifications (what is mostly done in computer science). They first review two existing approaches to estimate proportions: 1) sample a subset and hand label them to estimate the category proportions, 2) Do individual classification, and aggregate the predictions to calculate a proportion. They explain why both approaches have problems, and then propose two new methods. The first one applies existing individual classification techniques, but then estimates the errors per category and corrects the aggregated category proportions. The second one estimates proportions directly without doing individual classification. The problem can be framed as a regression problem and the class proportions are the regression coefficients. Because of computational and sparsity issues, they sample subsets of words, and estimate it for each set. The results are then averaged.
I think the paper gave a nice explanation of the goals and alternatives. Furthermore, it was interesting because I've never thought about estimating proportions instead of individual classifications, and now know why you would want to use other methods instead of just aggregation individual classification predictions.
Friday, March 4, 2011
Reading for 3/17/11: Grimmer and King, PNAS 2011
Note: no meeting during spring break (3/10).
Author: Justin Grimmer and Gary King
Venue: EMNLP 2010
Leader: none - attend the Machine Learning/Google Distinguished Lecture by Gary King instead. GHC 6115, 4:30pm (during class)
Request: When you post to the blog, please include:
- Your name
- Which focus paper this post relates to
- Whether this is the pre-meeting review or the post-meeting summary
Reminders:
- Leave a comment on this post (non-anonymously) giving the details of the related paper you will read (include a URL), by Monday, March 14.
- Post your commentary (a paragraph) as a new blog post, by Wednesday, March 16.
Post-Meeting Commentary 3/4/11 - Alan
I will use this post-meeting commentary to try to clarify some things about the paper I read (Ye et. al, Coling-ACL '06)
The paper presents and tests a hypothesis about what additional information human translators use to determine the tenses to be used during translation (in this case between Chinese and English). Since human translators still outperform current automated systems, the idea behind this is to identify where effort should be focused for advancing automatic extraction methods.
The experiment consists of training both conditional random fields (CSFs) and classification trees on surface features and latent features (alone and together) and evaluating the accuracy by evaluating against the tenses from gold-standard/best-ranked human-generated English translations (Of course here we are only considering whether the classifier can correctly predict the verb tense to use for the translation, so for Chinese to English, the classifier predicts which tense of the English verb is best suited). The paper also details how these gold-standards are generated from all the human annotations they collected.
In terms of surface features versus latent features, it seems that surface features include those that can be easily extracted, i.e. whether the verb is inside a quote, the presence of signal adverbs either before or after the verb, the presence of signal markers between two verbs, distance between characters, whether the verbs are in the same clause, etc. When the paper talks about latent verbs it addresses mainly three features. One is telicity, which specifies whether the verb can be bound within a certain time frame. Another is punctuality, which says whether a verb can be associated with a single point event. The third is temporal ordering, which describes one of six relationships between two invents, namely precession, succession, inclusion, subsumation, overlap, and none. The idea is that latent variables require deeper semantic analysis of the source text that is generally only feasible by human processing.
So in the end, the results simply show that the classifiers trained only on latent features outperform those trained only on surface features, which provides support for their simple claim that if we were able to achieve some deeper semantic analysis, then we would definitely be able to improve our approach towards this problem and maybe tense/disambiguation problems in general.
In hindsight, maybe not the greatest of papers, but I thought I would try to clear some things up since it was pretty rough when I presented yesterday. It's very possible I may have misunderstood some part so please let me know if something seems off.
-Alan
Post meeting commentary
Dong Nguyen
Focus paper: Tense Sense Disambiguation: a New Syntactic Polysemy Task. Roi Reichart and Ari Rappoport. EMNLP 2010
Because the focus paper proposes a new task, it was less clear what work was going to be relevant. People read papers about a diverse set of topics, including WSD, Machine Learning and linguistics. Overall people seem to like a paper a lot, the most doubts people had was on the way the authors had sampled the data.
I think the work was interesting and I'm curious to see what other approaches people are going to take working on this problem. For my research, we have been looking at posts from users over time on a forum. We were interested in looking at the development of users over time. However, including all the text of users together gave very noisy results, because it was including a lot of text where users were talking about past experiences (for example often when they were talking in present form when they were telling a story). It was very difficult to seperate the current state of users with past/future. A good way to disambiguate tense could definitely help.
Focus paper: Tense Sense Disambiguation: a New Syntactic Polysemy Task. Roi Reichart and Ari Rappoport. EMNLP 2010
Because the focus paper proposes a new task, it was less clear what work was going to be relevant. People read papers about a diverse set of topics, including WSD, Machine Learning and linguistics. Overall people seem to like a paper a lot, the most doubts people had was on the way the authors had sampled the data.
I think the work was interesting and I'm curious to see what other approaches people are going to take working on this problem. For my research, we have been looking at posts from users over time on a forum. We were interested in looking at the development of users over time. However, including all the text of users together gave very noisy results, because it was including a lot of text where users were talking about past experiences (for example often when they were talking in present form when they were telling a story). It was very difficult to seperate the current state of users with past/future. A good way to disambiguate tense could definitely help.
Thursday, March 3, 2011
Post Meeting Summary 3-3-2011 by Weisi Duan
Besides the focused paper, people have read related papers including machine learning techniques, Word Sense Disambiguation methods, linguistics, translation, and temporal event ordering which is semantically related.
For the focused paper, the authors come up with the idea of tackling a smaller semantic problem which has not been tackled before. They formulated this problem of Tense Disambiguation, which is related to WSD but not exactly the same. The influence of the problem is manifold. It can be applied to help many other problem such as machine translation, text entailment and so on.
For machine learning techniques, I read a paper that discusses a cascading model where the model is a pipeline of classifiers and the output of the previous classifier is used to identify the next classifier, and then classify the instance by the next classifier. Dong read a paper that explore the combination of classifiers to address the WSD. The authors experimented 6 different classifiers and different ways to combine them.
For WSD methods, beside the paper Dong read, Daniel read a paper that exploits novel syntactic features to improve the precision of WSD. The authors use minipar to generate the dependencies to be used as features. For classifier, they used Decision List and AdaBoost.
For temporal model, Dhananjay read a paper about ordering events based on temporal relations. The justifications of superiority of Integer linear programming against Greedy methods are discussed. The authors used SVM based transitivity to obtain output as pairwise ordering of temporal events.
For linguistics, Brendan read the paper about construction grammars. The definition of construction is discussed as well as the tree substitution grammar and decision oriented parsing.
For translation, Alan read a paper on translating verbs in Chinese to English, regarding the difficulty of tense. The authors explore latent features (not exactly features involving hidden variables) such as temporal features to show the effectiveness of such features. Ablation and comparison with surface features are conducted.
For the focused paper, the authors come up with the idea of tackling a smaller semantic problem which has not been tackled before. They formulated this problem of Tense Disambiguation, which is related to WSD but not exactly the same. The influence of the problem is manifold. It can be applied to help many other problem such as machine translation, text entailment and so on.
For machine learning techniques, I read a paper that discusses a cascading model where the model is a pipeline of classifiers and the output of the previous classifier is used to identify the next classifier, and then classify the instance by the next classifier. Dong read a paper that explore the combination of classifiers to address the WSD. The authors experimented 6 different classifiers and different ways to combine them.
For WSD methods, beside the paper Dong read, Daniel read a paper that exploits novel syntactic features to improve the precision of WSD. The authors use minipar to generate the dependencies to be used as features. For classifier, they used Decision List and AdaBoost.
For temporal model, Dhananjay read a paper about ordering events based on temporal relations. The justifications of superiority of Integer linear programming against Greedy methods are discussed. The authors used SVM based transitivity to obtain output as pairwise ordering of temporal events.
For linguistics, Brendan read the paper about construction grammars. The definition of construction is discussed as well as the tree substitution grammar and decision oriented parsing.
For translation, Alan read a paper on translating verbs in Chinese to English, regarding the difficulty of tense. The authors explore latent features (not exactly features involving hidden variables) such as temporal features to show the effectiveness of such features. Ablation and comparison with surface features are conducted.
Subscribe to:
Posts (Atom)