---
title: "A Composite Kernel to Extract Relations between Entities with"
description: "The authors build a composite kernel with two parts. 17 references, cited by 64 papers here."
authors: ["Min Zhang", "Jie Zhang", "Jian Su", "GuoDong Zhou"]
year: 2006
venue: "Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics"
source: "https://aclanthology.org/P06-1104/"
doi: "10.3115/1220175.1220279"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/zhang-2006-composite-kernel-extract-relations-between/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/zhang-2006-composite-kernel-extract-relations-between/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / A Composite Kernel to Extract Relations between Entities with Both Flat and Structured Features

# A Composite Kernel to Extract Relations between Entities with Both Flat and Structured Features

**Authors:** [Min Zhang](https://md.research.elamur.ai/free/en/authors/min-zhang/), [Jie Zhang](https://md.research.elamur.ai/free/en/authors/jie-zhang/), [Jian Su](https://md.research.elamur.ai/free/en/authors/jian-su/) and [GuoDong Zhou](https://md.research.elamur.ai/free/en/authors/guodong-zhou/) · **Year:** 2006 · **Venue:** [Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2006](https://md.research.elamur.ai/free/en/venues/acl/2006/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/P06-1104/) · [PDF](https://aclanthology.org/P06-1104.pdf) · [DOI 10.3115/1220175.1220279](https://doi.org/10.3115/1220175.1220279) · [OpenAlex](https://openalex.org/W2152269015)

**Citations:** 242 citations (OpenAlex, 2026-10-14) · [64](https://md.research.elamur.ai/free/en/papers/zhang-2006-composite-kernel-extract-relations-between/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary

The paper tackles relation extraction, which means deciding which predefined semantic relation, if any, links a pair of entity mentions in a sentence. The authors build a composite kernel with two parts. The first is a linear entity kernel that counts shared entity attributes: headword, type, subtype and mention type, plus LDC mention type for ACE 2004. The second is the Collins and Duffy convolution parse tree kernel, which scores syntactic similarity by implicitly counting common sub-trees. They join the two by a weighted sum of normalized kernels, or by first applying a degree-2 polynomial expansion to the entity kernel. They also compare five ways of cutting a relation instance out of a full parse tree.

Experiments on the ACE 2003 and ACE 2004 corpora show that the composite kernel beats the best previously reported feature-based systems. It also clearly outperforms two earlier dependency tree kernels, which suffered from low recall. The work matters because it shows that rich syntactic structure can be used with little manual feature engineering, and that more knowledge sources can be added simply by adding more kernels.

## Key points

- The entity kernel counts identical feature values between corresponding entities. The tree kernel uses a decay factor λ and runs in O(|N1|·|N2|) worst case, though in practice it behaves nearly linearly.
- Weights tuned on the development set:
  - linear combination: α = 0.4;
  - polynomial version: α = 0.23, with K_p = (K + 1)².
- Five relation instance spaces were studied, including the Minimum Complete Tree (MCT). The smaller PT portion represented instances well and sped up training considerably.
- Training on a P4 3.0 GHz machine with 2 GB RAM took roughly:
  - 110 minutes on ACE 2003 (about 77k instances);
  - 30 minutes on ACE 2004 (about 33k instances).
- Error analysis of the polynomial kernel:
  - about 83.5% (2004) and 85.8% (2003) of errors came from relation detection rather than relation typing;
  - negative training examples outnumbered positives roughly 8 to 1.

## Interesting ideas
- **Combine kernels instead of hand-merging features.** Sums, products, normalization and polynomial expansion of valid kernels remain valid kernels. This makes it straightforward to fuse heterogeneous evidence, such as flat attributes and tree structure, in other classification tasks.
- **Normalize each kernel before combining.** Normalizing every component prevents one kernel with larger raw values from swamping the other. This is a cheap safeguard whenever similarity scores on different scales are merged.
- **Use polynomial expansion to get feature conjunctions for free.** Squaring the entity kernel implicitly creates pairwise features across the two entities without enumerating them. The same trick could model feature interactions in other pairwise tasks.
- **Treat the choice of tree region as a design variable.** Testing which part of the parse tree to feed the kernel improved both accuracy and speed. Pruning input structures this way is worth trying for any structure-based model.
- **Split errors by stage.** Separating detection errors from type-classification errors showed that detection and class imbalance were the real bottleneck. This kind of breakdown helps decide where future effort should go.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Institute for Infocomm Research](https://md.research.elamur.ai/free/en/labs/institute-for-infocomm-research/) — Research institute, Singapore, Singapore · 33 works · 14,373 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

## Cite

Cite as: Min Zhang, Jie Zhang, Jian Su and GuoDong Zhou. 2006. A Composite Kernel to Extract Relations between Entities with Both Flat and Structured Features. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{zhang2006composite,
  title = {{A Composite Kernel to Extract Relations between Entities with Both Flat and Structured Features}},
  author = {Min Zhang, Jie Zhang, Jian Su and GuoDong Zhou},
  booktitle = {Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  doi = {10.3115/1220175.1220279},
  url = {https://doi.org/10.3115/1220175.1220279}
}
```

- [← previous Get out the vote: Determining support or opposition from Congressional floor-debate transcripts](https://md.research.elamur.ai/free/en/papers/thomas-2006-get-out-vote-determining-support/)
- [next → Broad-Coverage Sense Disambiguation and Information Extraction with a Supersense Sequence Tagger](https://md.research.elamur.ai/free/en/papers/ciaramita-2006-broad-coverage-sense-disambiguation-information/)
- [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/)

## References

17 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. ACE. 2002-2005. The Automatic Content Extraction Projects. [http://www.ldc.upenn.edu/Projects/ACE/](http://www.ldc.upenn.edu/Projects/ACE/) Basili R., Cammisa M. and Moschitti A. 2005. A Semantic Kernel to classify text with very few training examples. ICML-2005 [↗](http://www.ldc.upenn.edu/Projects/ACE/)
2. Bunescu R. C. and Mooney R. J. 2005. [A Shortest Path Dependency Kernel for Relation Extraction](https://md.research.elamur.ai/free/en/papers/bunescu-2005-shortest-path-dependency-kernel-relation/). EMNLP-2005
3. Charniak E. 2001. [Immediate-head Parsing for Language Models](https://md.research.elamur.ai/free/en/papers/charniak-2001-immediate-head-parsing-language-models/). ACL-2001
4. Collins M. and Duffy N. 2001. Convolution Kernels for Natural Language. NIPS-2001 [find](https://scholar.google.com/scholar?q=Collins+M%2E+and+Duffy+N%2E+2001%2E+Convolution+Kernels+for+Natural+Language%2E+NIPS%2D2001)
5. Culotta A. and Sorensen J. 2004. Dependency Tree Kernel for Relation Extraction. ACL-2004 [find](https://scholar.google.com/scholar?q=Culotta+A%2E+and+Sorensen+J%2E+2004%2E+Dependency+Tree+Kernel+for+Relation+Extraction%2E+ACL%2D2004)
6. Haussler D. 1999. Convolution Kernels on Discrete Structures. Technical Report UCS-CRL-99-10, University of California, Santa Cruz. [find](https://scholar.google.com/scholar?q=Haussler+D%2E+1999%2E+Convolution+Kernels+on+Discrete+Structures%2E+Technical+Report+UCS%2DCRL%2D99%2D10%2C+University+of+California%2C+Santa+Cruz%2E)
7. Joachims T. 1998. Text Categorization with Support Vecor Machine: learning with many relevant features. ECML-1998 [find](https://scholar.google.com/scholar?q=Joachims+T%2E+1998%2E+Text+Categorization+with+Support+Vecor+Machine%3A+learning+with+many+relevant+features%2E+ECML%2D1998)
8. Kambhatla N. 2004. Combining lexical, syntactic and semantic features with Maximum Entropy models for extracting relations. ACL-2004 (poster) [find](https://scholar.google.com/scholar?q=Kambhatla+N%2E+2004%2E+Combining+lexical%2C+syntactic+and+semantic+features+with+Maximum+Entropy+models+for+extracting+relations%2E+ACL%2D2004+%28poster%29)
9. Lodhi H., Saunders C., Shawe-Taylor J., Cristianini N. and Watkins C. 2002. Text classification using string kernel. Journal of Machine Learning Research, 2002(2):419-444 [find](https://scholar.google.com/scholar?q=Lodhi+H%2E%2C+Saunders+C%2E%2C+Shawe%2DTaylor+J%2E%2C+Cristianini+N%2E+and+Watkins+C%2E+2002%2E+Text+classification+using+string+kernel%2E+Journal+of+Machine+Learning+Research%2C+2002%282%29%3A419%2D444)
10. Miller S., Fox H., Ramshaw L. and Weischedel R. 2000. A novel use of statistical parsing to extract information from text. NAACL-2000 [find](https://scholar.google.com/scholar?q=Miller+S%2E%2C+Fox+H%2E%2C+Ramshaw+L%2E+and+Weischedel+R%2E+2000%2E+A+novel+use+of+statistical+parsing+to+extract+information+from+text%2E+NAACL%2D2000)
11. Moschitti A. 2004. A Study on Convolution Kernels for Shallow Semantic Parsing. ACL-2004 [find](https://scholar.google.com/scholar?q=Moschitti+A%2E+2004%2E+A+Study+on+Convolution+Kernels+for+Shallow+Semantic+Parsing%2E+ACL%2D2004)
12. MUC. 1987-1998. [http://www.itl.nist.gov/iaui/894.02/related_projects/muc/](http://www.itl.nist.gov/iaui/894.02/related_projects/muc/) [↗](http://www.itl.nist.gov/iaui/894.02/related_projects/muc/)
13. Schölkopf B. and Smola A. J. 2001. Learning with Kernels: SVM, Regularization, Optimization and Beyond. MIT Press, Cambridge, MA 407-423 [find](https://scholar.google.com/scholar?q=Sch%C3%B6lkopf+B%2E+and+Smola+A%2E+J%2E+2001%2E+Learning+with+Kernels%3A+SVM%2C+Regularization%2C+Optimization+and+Beyond%2E+MIT+Press%2C+Cambridge%2C+MA+407%2D423)
14. Suzuki J., Hirao T., Sasaki Y. and Maeda E. 2003. Hierarchical Directed Acyclic Graph Kernel: Methods for Structured Natural Language Data. ACL-2003 [find](https://scholar.google.com/scholar?q=Suzuki+J%2E%2C+Hirao+T%2E%2C+Sasaki+Y%2E+and+Maeda+E%2E+2003%2E+Hierarchical+Directed+Acyclic+Graph+Kernel%3A+Methods+for+Structured+Natural+Language+Data%2E+ACL%2D2003)
15. Zelenko D., Aone C. and Richardella A. 2003. [Kernel Methods for Relation Extraction](https://md.research.elamur.ai/free/en/papers/zelenko-2002-kernel-methods-relation-extraction/). Journal of Machine Learning Research. 2003(2):1083-1106
16. Zhao S.B. and Grishman R. 2005. [Extracting Relations with Integrated Information Using Kernel Methods](https://md.research.elamur.ai/free/en/papers/zhao-2005-extracting-relations-integrated-information-kernel/). ACL-2005
17. Zhou G.D., Su J, Zhang J. and Zhang M. 2005. [Exploring Various Knowledge in Relation Extraction](https://md.research.elamur.ai/free/en/papers/zhou-2005-exploring-various-knowledge-relation-extraction/). ACL-2005

*Updated 24 October 2026*