CLUSTERING BY TREE DISTANCE FOR PARSE TREE NORMALISATION:

CLUSTERING BY TREE DISTANCE FOR PARSE TREE NORMALISATION:

Writed by Martin Emms.

Notes by Hector Franco.

0 Abstract

Potential application: Transformation of interrogative to indicative sentences. -> is a step on question answering. | A tree distance is proposed -> find a pattern tree that summarizes the cluster. .

1 Introduction

Previous work:

Question-answering with tree-distance.

1 take a parse-structure from a question, 2 match it up to parse-structures of candidate answers.

Normalization: change passive structures to active structures: interrogative to indicative.

Popular parser: Collins probabilistic. Trained on Penn Treebank.

Trees are not assigned in accordance with any finite grammar.

…

Simple transformation -> mentally induction. (Very boring)

Method described:

Parse structures can be hierarchically clustered by tree-distance and kind of centroid tree for a chosen cluster can be generated which exemplifies typical traits of trees with the cluster.

 

2 Tree distance

Concepts:

Source and target trees

Preserve left to right order and ancestry.

Descendant.

(Not sense to summarize, just look the original).

2.1. question answering by tree distance.

Answers ranked according to the tree-distance from the questions.

QATD : question answering by tree distance.

Additional methods: query-expansion, query-type identification, named entity recognition.

Syntactic structures group items semantically related.

Syntactic structures might encode or represent a great deal that is not semantic in any sense.

 

Variances in tree distances:

Sub-tree: the cost of the least cost mapping from a sub-tree of the source.

Sub-traversal: the least cost mapping from a sub-traversal of the left-to-right post –order traversal of the source.

Structural weights: weights according to the syntactic structure.

Wild cards: can have zero cost matching, ???????????

Lexical Emphasis: leaf nodes have weights which are scaled up in comparison to nodes which are internal to the tree.

String Distance: if code source and target the string distance coincides with tree distance. ??????

Results:

Tree distance which uses sub-trees, weights , wild-cards and lexical emphasis, are better than sub-string distance and each parameter improve it.

???????

 

 

 

 

3 Clustering by tree distance

Used the agglomerative clustering algorithm: pic a pair of cluster with minimal distance and merge it into a single one.

Agglomerative coefficient: measure of overall quality.

S(q) cluster of q

Merge_dist(q) intercluster distance.

Agglomerative coefficient AC merge_dist/Df. 1 the best (0 to 1).

Giving different weight give a better results. (head/complement/adjunt/…)

4 Deriving a pattern tree form a cluster

How to seek the centre point of a cluster. (the one with minimal distance to the others).

Distance is Euclidean or cosine.

 

New function: aling_outcome( node I, paramb)

B =0 matched perfectly, b=1 substituted, b=2 deleted.

Used to derive an alignment summary tree, align_sum( c )

 

Final step:

Deletion nodes are deleted

Substitution nodes become wild-card trees.

 

5 conclusions and future work

Adaptations of tree distance improve question answering, and cluster quality.

 --finish--

Web Information Retrieval: Spam Detection and Named Entity Recognition

Spam detection

Linguistic features

Adds: web spam

Full search engines: for ranking it-self

Challenge:

Complexity

Scale

Co-adaptation.

 

 

 

Blog spam: blog of hide links

Attractive keywords

Linguistic analysis

Light-weight linguistic analysis

Air web – workshop

Attributes for ML.

Lexical diversity

Syntactical entropy

Labels

-          Hosts

-          Documents

 

String distance metrics

 

Name variations complicate the t…

Permutations, abbreviations, speling mistakes, declensions

 

Edit distance metrics:

Levenshtein

Bag distance

Needleman-wunsh

Smith-watermar

Smith-waterman with affine gaps.

Common character-level n-grams

q-grams, positional, q-grams, skip-grams

 

longest common substring LCS

 

string distance

jaro

jaro – winkler

jwm 

Web Information Retrieval: Spam Detection and Named Entity Recognition

2 hours seminar

by Marcin Sydow

Query decomposition

 

Topical query descomposition

 

Query in red

Do blue set

 

Quality of decomposition

Cost: low topical scattered

Red faction low `(small quantity of documents)

Inter-query overlap (well descompose)

Uncovered (try to cover all the query).

 

Annealing function

Solutions are neighbors if they differed by 1 query.  

 

Properties:

Quasi-transitive (temperature preference)

Utility function

Social preferences

Majority voting: is not transitive

Single peakedness

Arrows social welfare function

 

We like:

Arrow’s impossibility theorem.

Tree Kernels for semantic role labeling

reading paper

Tree Kernels for semantic role labeling

Tree Kernels for semantic role labeling (32 pages)

0.   Abstract

This paper is based on kernel functions to model parse tree properties in kernel based machines.

1.   Introduction

Recently attention: automatic labeling of semantic roles. It requires:

1. Detection of the target predicate

2. Detection and classification of constituting arguments.

Previous work:

-          Machine learning

-          Linking theories semantic and syntax

Tree kernel for:

-          Parsing re-ranking

-          Relation extraction

-          Name entity recognition.

Recent work with high labeling accuracy,

Joint inference on predicate-argument structure. For this -> extract features from sentence syntactic parse tree.

1-      Feature extraction.

2-      Combination with traditional attribute value models.

3-      Feature engineering using kernel combinations and marking strategies.

4-      Tree kernels….

5-      Identify the most important structured features: highest-weighted features -> better classifiers.

“Tree kernels should always be applied”.

Limitations:

a)      Poor impact on boundary detection.

b)      Limited contribution to overall accuracy.

Tree kernels for srl: types:

-          Canonical mappings

-          Feature extraction functions

Carefully engineered tree kernels always increase accuracy.

 

2.   Automatic shallow semantic parsing

3.   Tree kernels

4.   State of the art architecture for SRL

5.   Structured feature engineering

6.   Experiments

7.   Discursion and conclusions

Semantic Role Labeling: An Introduction to the Special Issue

®  Sentence + designated verb: SRL identify the arguments of the verb. And label them with semantic roles.

®  Steps:

¯  1 Pruning.

¯  2 Local scoring

¯  3 Joint scoring

(4) Fixing common errors

 

Pruning

®  Filtering the set of arguments for a given predicate.

¯  Any subsequence of words in the sentence is an argument candidate.

®  Xue and Palmer (2004)

Joint scoring      

®  Good structure of labeled arguments.

®  Arguments do not overlap,

®  Core arguments do not repeat, etc.

®  Re-ranking

®  Probabilistic methods.

Conditional random fields

SRL architecture:

®  Combination of systems and input annotations.

¯  Increase robustness,

¯  Gain coverage

¯  Reduce effects of parse errors

®  One my combine:

¯  Output of independents srl basic systems

¯  Outputs from same srl s. changing input annotations or parameters.

Gaing of 2-3 F1 points.  

®  Joint labeling…

®  Dependency parsing

®  Combine parsing and srl in a single step. …

®  Characterize candidate argument
phrase type, headword, …

®  Characterize verb predicate +cntx
lemma, voice,

®  Characterize the relation.
Syntactic + semantic.
Left/right position of the constituent  with respect to the verb…

®  Recall:

®  81% argument identification

®  95% assigned correct semantic role.

®  SemEval-2007

®  Disambiguation of 50 verbs.

®  FrameNet

®  40 frames

®  F1=92% asigning semantic roles

®  F1 83% segmenting and labeling arg.

®  Complete analysis of semantic roles on unseen texts,

®  Precision 60s

®  Recall 30s

®  SRL relies on syntactic structure.

®  Output by statistical parser 90% matching.

®  Is common to use parser trees.

®  Gold-standard trees.???

®  Most of the errors are by having incorrect syntactic constituents.

®  SRL relies on syntactic structure.

®  Output by statistical parser 90% matching.

®  Is common to use parser trees.

®  Gold-standard trees.???

®  Most of the errors are by having incorrect syntactic constituents.

®  CoNLL-2005 Brown corpus annotated

®  Performance drop below 70%

®  They clamed errors are in assigning the semantic roles rather than identification of argument boundaries.

®  Spanish and catalan, CESS-ECE corpus.

®  86% disambiguation predicates

®  83% labeling arguments.

®  chinese

®  semEval-2007 25K SENTENCE

®  80% core elements.

Top performing team use machine learning techniques

updating blog with keywords from the last two days conferences 

preprocessing samples before give them to the learning machines

There is a large work done on preprocessing samples before give them to the learning machines:

·         Remove noise

o   Algorithms for detecting noise samples based in knn algorithms.

·         Add noise

o   Small noise produces a better performance in neural networks (and maybe also in other algorithms).

·         Re-structure the dimensionality and distance metrix.

o   Nahanalobis distance.

o   Scaling the data: It give an improvement in SVM machines

o   Kernels: increase dimensions.

o   Genetic kernel (GK SVM)

o   Removing features:

§  removing dimensions (feature selection)

·         information gain (the best)

·         mutual information

·         x2 statistic chi (second best)

·         term strength

§  principal component analysis.

§  neighborhood component analysis

·         Re-sampling:

o   Under-sampling:

§  Randomly

§  Inconsistent data

§  Duplicate data

§  Removing noise (bis)

o   Over-sampling:

§  Randomly

§  SMOTE

§  Border SMOTE-1

§  Border SMOTE-2

§  Adding noise (bis)

§  Give more weight to hard samples.

·         Windowed data:

o   In some cases context information increases the accuracy.

Split features: in text categorization words can split using the morphology features: Morfesor.