|
|
| (20 intermediate revisions by the same user not shown) |
| Line 4: |
Line 4: |
| | == Online version == | | == Online version == |
| | | | |
| − | [http://aclweb.org/anthology-new/D/D12/D12-1136.pdf] | + | An online pdf version is here[http://aclweb.org/anthology-new/D/D12/D12-1136.pdf] |
| | | | |
| | == Summary == | | == Summary == |
| | | | |
| − | This paper poses two interesting social problems on [[bipartite graph]] named [[AddressesProblem::Neighborhood formation and Anomaly detection]]. They also propose solutions based on [[UsesMethod::Random walk with restart]]. | + | This paper proposed a method for automatic response completion in Social Media context by considering mainly two factors: |
| | | | |
| − | The experimented on 3 real world social graphs [[UsesDataset::Conference-Author dataset]], [[UsesDataset::Author-Paper dataset]] and [[UsesDataset::IMDB dataset]]
| |
| | | | |
| − | == Evaluation ==
| + | 1) The language used in responses (By using Language Model[LM] (bigram model & trigram model(both back-off to unigram))) |
| | | | |
| − | They evaluate their methods by asking following 4 questions :
| |
| − | - Does NF find out meaningful neighborhoods?
| |
| − | - How close is Approximate NF to exact NF?
| |
| − | - Can AD detect injected anomalies?
| |
| − | - How much time these methods take to run on graphs of varying sizes?
| |
| | | | |
| − | == Discussion ==
| + | 2) The specific context provided by the original message. |
| − | This paper poses two important social problems related to bipartite social graphs and explained how those problems can be solved efficiently using random walks.
| |
| | | | |
| − | They also claim that the neighborhoods over nodes can represent personalized clusters depending on different perspectives.
| + | The author used the following things to model the part. |
| | | | |
| − | During presentation one of the audiences raised question about is anomaly detection in this paper similar to betweenness of edges defined in Kleinber's text as discussed in [[Class Meeting for 10-802 01/26/2010]]. I think they are similar. In the texbook they propose, detecting edges with high betweenness and using them to partition the graph. In this paper they first try to create neighbourhood partitions based on random walk prbabilities and which as a by product gives us nodes and edges with high betweenness value.
| + | [TM] Methods In Ritter et. al 2010, Data-Driven Response Generation in Social Media, which is to use a translation model to do alignment between stimulus(source) and the response(target). [IBM-Model1] |
| | | | |
| − | == Related papers ==
| + | [Selection model] To select a token in stimulus uniformly at random. |
| − | There has been a lot of work on anomaly detection in graphs.
| |
| − | * The paper by [[RelatedPaper::Moonesinghe and Tan ICTAI06]] finds the clusters of outlier objects by doing random walk on the weighted graph.
| |
| − | * The paper by [[RelatedPaper::Aggarwal SIGMOD 2001]] proposes techniques for projecting high dimensional data on lower dimensions to detect outliers.
| |
| | | | |
| − | == Study plan ==
| + | [Topic model] First learn a topic model over conversations in the training data using LDA. Then identify the most likely topic of the conversation based on s, and expect responds to be generated from this topic. |
| − | * Article:Bipartite graph:[http://en.wikipedia.org/wiki/Bipartite_graph]
| |
| − | * Article:Anomaly detection:[http://en.wikipedia.org/wiki/Anomaly_detection]
| |
| − | * Paper:Topic sensitive pagerank:[http://dl.acm.org/citation.cfm?id=511513]
| |
| − | **Paper:The PageRank Citation Ranking: Bringing Order to the Web:[http://ilpubs.stanford.edu:8090/422/]
| |
| − | * Paper:Multilevel k-way Partitioning Scheme for Irregular Graphs:[http://glaros.dtc.umn.edu/gkhome/node/81]
| |
| | | | |
| − | == Citation ==
| |
| − | Revisiting the Predictability of Language: Response Completion in Social Media, Bo Pang Sujith Ravi, EMNLP 2012
| |
| | | | |
| − | == Online version ==
| + | The author used a '''linear''' combination to mixture these two factors (models). |
| | | | |
| − | [http://aclweb.org/anthology-new/D/D12/D12-1136.pdf]
| + | == Evaluation == |
| | | | |
| − | == Summary ==
| + | The author claims that translation-based approach is not well suited for this particular task and LDA suffers from the fact that the text is noisy (or too generic) therefore, not useful enough to help in the prediction task. |
| | | | |
| − | This paper poses two interesting social problems on [[bipartite graph]] named [[AddressesProblem::Neighborhood formation and Anomaly detection]]. They also propose solutions based on [[UsesMethod::Random walk with restart]].
| + | == Discussion == |
| | | | |
| − | The experimented on 3 real world social graphs [[UsesDataset::Conference-Author dataset]], [[UsesDataset::Author-Paper dataset]] and [[UsesDataset::IMDB dataset]] | + | The author provides an analysis (entropy estimates along with upper-bound numbers observed from experiments) and suggests that there can be interesting future work to explore the contextual information provided by the stimulus more effectively and further improve the response completion task. |
| | | | |
| − | == Evaluation == | + | == Related papers == |
| | | | |
| − | They evaluate their methods by asking following 4 questions :
| + | Ritter et. al 2010, Data-Driven Response Generation in Social Media |
| − | - Does NF find out meaningful neighborhoods?
| |
| − | - How close is Approximate NF to exact NF?
| |
| − | - Can AD detect injected anomalies?
| |
| − | - How much time these methods take to run on graphs of varying sizes?
| |
| | | | |
| − | == Discussion ==
| + | Regina Barzilay and Mirella Lapata. 2005, Modeling local coherence: An entity-based approach |
| − | This paper poses two important social problems related to bipartite social graphs and explained how those problems can be solved efficiently using random walks.
| |
| | | | |
| − | They also claim that the neighborhoods over nodes can represent personalized clusters depending on different perspectives.
| + | == Study plan == |
| | | | |
| − | During presentation one of the audiences raised question about is anomaly detection in this paper similar to betweenness of edges defined in Kleinber's text as discussed in [[Class Meeting for 10-802 01/26/2010]]. I think they are similar. In the texbook they propose, detecting edges with high betweenness and using them to partition the graph. In this paper they first try to create neighbourhood partitions based on random walk prbabilities and which as a by product gives us nodes and edges with high betweenness value.
| + | Language Model: [http://en.wikipedia.org/wiki/Language_model] |
| | | | |
| − | == Related papers ==
| + | Machine Translation, IBM Model-1 [http://acl.ldc.upenn.edu/J/J93/J93-2003.pdf] |
| − | There has been a lot of work on anomaly detection in graphs.
| |
| − | * The paper by [[RelatedPaper::Moonesinghe and Tan ICTAI06]] finds the clusters of outlier objects by doing random walk on the weighted graph.
| |
| − | * The paper by [[RelatedPaper::Aggarwal SIGMOD 2001]] proposes techniques for projecting high dimensional data on lower dimensions to detect outliers.
| |
| | | | |
| − | == Study plan ==
| + | LDA [http://en.wikipedia.org/wiki/Latent_Dirichlet_allocation] |
| − | * Article:Bipartite graph:[http://en.wikipedia.org/wiki/Bipartite_graph]
| |
| − | * Article:Anomaly detection:[http://en.wikipedia.org/wiki/Anomaly_detection]
| |
| − | * Paper:Topic sensitive pagerank:[http://dl.acm.org/citation.cfm?id=511513]
| |
| − | **Paper:The PageRank Citation Ranking: Bringing Order to the Web:[http://ilpubs.stanford.edu:8090/422/]
| |
| − | * Paper:Multilevel k-way Partitioning Scheme for Irregular Graphs:[http://glaros.dtc.umn.edu/gkhome/node/81]
| |
Citation
Revisiting the Predictability of Language: Response Completion in Social Media, Bo Pang Sujith Ravi, EMNLP 2012
Online version
An online pdf version is here[1]
Summary
This paper proposed a method for automatic response completion in Social Media context by considering mainly two factors:
1) The language used in responses (By using Language Model[LM] (bigram model & trigram model(both back-off to unigram)))
2) The specific context provided by the original message.
The author used the following things to model the part.
[TM] Methods In Ritter et. al 2010, Data-Driven Response Generation in Social Media, which is to use a translation model to do alignment between stimulus(source) and the response(target). [IBM-Model1]
[Selection model] To select a token in stimulus uniformly at random.
[Topic model] First learn a topic model over conversations in the training data using LDA. Then identify the most likely topic of the conversation based on s, and expect responds to be generated from this topic.
The author used a linear combination to mixture these two factors (models).
Evaluation
The author claims that translation-based approach is not well suited for this particular task and LDA suffers from the fact that the text is noisy (or too generic) therefore, not useful enough to help in the prediction task.
Discussion
The author provides an analysis (entropy estimates along with upper-bound numbers observed from experiments) and suggests that there can be interesting future work to explore the contextual information provided by the stimulus more effectively and further improve the response completion task.
Related papers
Ritter et. al 2010, Data-Driven Response Generation in Social Media
Regina Barzilay and Mirella Lapata. 2005, Modeling local coherence: An entity-based approach
Study plan
Language Model: [2]
Machine Translation, IBM Model-1 [3]
LDA [4]
