Skip to content
Tree-SVM
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
InterTree.fs
Kernel.fs
ListSet.fs
Main.fs
Makefile.Win
PartialTree.fs
README
SMO.fs
SkipNodeTree.fs
SubSetTree.fs
Tree.fs
Utils.fs

README

Tree-SVM: Tool for SVM optimization on tree data structures

-----------------------------------------------------------

OVERVIEW:

Tree-SVM implements SMO decomposition algorithm from Fan et al JMLR 2005.

Tree-SVM supports only binary classification by now. 
Input trees must be encoded in the bracket notation, e.g., "(A (B (C) (D)) (E (F)))" represents the following tree:

     A
    / \
   B   E
  / \   \
 C   D   F 

where "A", "B", "C", "D", "E", "F" are corresponding node labels.

Example of input file:
+1 (beats (clarity (on (#CAMERA))) (out) (easily) (clarity (on (#CAMERA))))
-1 (#CAMERA (is (2.5 (same (as (that (on (#CAMERA))))) (wide))))

Available kernels:
- Intersection kernel (counts the number of common labels for both input trees)
- Subtree kernel (Vishwanathan and Smola, 2001)
- Subset tree kernel (Collins and Duffy, 2002)
- Partial tree kernel (Moschitti, 2006)
- Skip-node kernel (Tkachenko and Lauw, 2015)
- Linear Skip-node kernel (Tkachenko and Lauw, 2015)
- Lookahead Skip-node kernel (Tkachenko and Lauw, 2015)

-----------------------------------------------------------

HOW TO CITE:

If you use Tree-SVM in your research, please cite the following paper:

Maksim Tkachenko and Hady W. Lauw. A Convolution Kernel Approach to Identifying Comparisons in Text, ACL 2015.

The bibtex format is

@inproceedings{tkachenko-lauw:2015,
  author    = {Maksim Tkachenko and Hady W. Lauw},
  title     = {A Convolution Kernel Approach to Identifying Comparisons in Text},
  booktitle = {Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics},
  year      = {2015},
  publisher = {Association for Computational Linguistics},
}

If you use Subtree kernel, Subset tree kernel, or Partial tree kernel, please cite the corresponding papers.

-----------------------------------------------------------

BIBLIOGRAPHY:

@article{fan:2005,
 author = {Fan, Rong-En and Chen, Pai-Hsuen and Lin, Chih-Jen},
 title = {Working Set Selection Using Second Order Information for Training Support Vector Machines},
 journal = {J. Mach. Learn. Res.},
 issue_date = {12/1/2005},
 volume = {6},
 month = dec,
 year = {2005},
 issn = {1532-4435},
 pages = {1889--1918},
 numpages = {30},
 url = {http://dl.acm.org/citation.cfm?id=1046920.1194907},
 acmid = {1194907},
 publisher = {JMLR.org},
} 

@inproceedings{collins-duffy:2002,
 author = {Michael Collins and Nigel Duffy},
 title = {New Ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures, and the Voted Perceptron},
 booktitle = {Proceedings of 40th Annual Meeting of the Association for Computational Linguistics},
 month = {July},
 year = {2002},
 address = {Philadelphia, Pennsylvania, USA},
 publisher = {Association for Computational Linguistics},
 pages = {263--270},
 url = {http://www.aclweb.org/anthology/P02-1034},
 doi = {10.3115/1073083.1073128}
}

@incollection{smola-vishwanathan:2003,
 title = {Fast Kernels for String and Tree Matching},
 author = {Alex J. Smola and S.v.n. Vishwanathan},
 booktitle = {Advances in Neural Information Processing Systems 15},
 editor = {S. Becker and S. Thrun and K. Obermayer},
 pages = {585--592},
 year = {2003},
 publisher = {MIT Press},
 url = {http://papers.nips.cc/paper/2272-fast-kernels-for-string-and-tree-matching.pdf}
}

@incollection{moschitti:2006,
 year={2006},
 isbn={978-3-540-45375-8},
 booktitle={Machine Learning: ECML 2006},
 volume={4212},
 series={Lecture Notes in Computer Science},
 editor={Fürnkranz, Johannes and Scheffer, Tobias and Spiliopoulou, Myra},
 doi={10.1007/11871842_32},
 title={Efficient Convolution Kernels for Dependency and Constituent Syntactic Trees},
 url={http://dx.doi.org/10.1007/11871842_32},
 publisher={Springer Berlin Heidelberg},
 author={Moschitti, Alessandro},
 pages={318-329},
 language={English}
}
You can’t perform that action at this time.