diff --git a/docs/detailed-results/less/cnn-word.pdf b/docs/detailed-results/less/cnn-word.pdf
new file mode 100644
index 0000000..31fc593
Binary files /dev/null and b/docs/detailed-results/less/cnn-word.pdf differ
diff --git a/docs/detailed-results/less/cnn.pdf b/docs/detailed-results/less/cnn.pdf
new file mode 100644
index 0000000..b0a485e
Binary files /dev/null and b/docs/detailed-results/less/cnn.pdf differ
diff --git a/docs/detailed-results/less/comparison_less.pdf b/docs/detailed-results/less/comparison_less.pdf
new file mode 100644
index 0000000..3b776a7
Binary files /dev/null and b/docs/detailed-results/less/comparison_less.pdf differ
diff --git a/docs/detailed-results/less/naive-bayes.pdf b/docs/detailed-results/less/naive-bayes.pdf
new file mode 100644
index 0000000..9aee92f
Binary files /dev/null and b/docs/detailed-results/less/naive-bayes.pdf differ
diff --git a/docs/detailed-results/less/ngram-distance.pdf b/docs/detailed-results/less/ngram-distance.pdf
new file mode 100644
index 0000000..bc40145
Binary files /dev/null and b/docs/detailed-results/less/ngram-distance.pdf differ
diff --git a/docs/detailed-results/less/ngram-model.pdf b/docs/detailed-results/less/ngram-model.pdf
new file mode 100644
index 0000000..698d9e8
Binary files /dev/null and b/docs/detailed-results/less/ngram-model.pdf differ
diff --git a/scripts/comparison_extension.pdf b/docs/detailed-results/mini/cnn-word.pdf
similarity index 52%
copy from scripts/comparison_extension.pdf
copy to docs/detailed-results/mini/cnn-word.pdf
index 30e67a5..bd2a74e 100644
Binary files a/scripts/comparison_extension.pdf and b/docs/detailed-results/mini/cnn-word.pdf differ
diff --git a/scripts/comparison_extension.pdf b/docs/detailed-results/mini/cnn.pdf
similarity index 52%
copy from scripts/comparison_extension.pdf
copy to docs/detailed-results/mini/cnn.pdf
index 30e67a5..3266308 100644
Binary files a/scripts/comparison_extension.pdf and b/docs/detailed-results/mini/cnn.pdf differ
diff --git a/scripts/comparison_mini.pdf b/docs/detailed-results/mini/comparison_mini.pdf
similarity index 66%
rename from scripts/comparison_mini.pdf
rename to docs/detailed-results/mini/comparison_mini.pdf
index 78e90a6..bf65871 100644
Binary files a/scripts/comparison_mini.pdf and b/docs/detailed-results/mini/comparison_mini.pdf differ
diff --git a/scripts/comparison_extension.pdf b/docs/detailed-results/mini/naive-bayes.pdf
similarity index 52%
copy from scripts/comparison_extension.pdf
copy to docs/detailed-results/mini/naive-bayes.pdf
index 30e67a5..c588cc8 100644
Binary files a/scripts/comparison_extension.pdf and b/docs/detailed-results/mini/naive-bayes.pdf differ
diff --git a/scripts/comparison_extension.pdf b/docs/detailed-results/mini/ngram-distance.pdf
similarity index 52%
copy from scripts/comparison_extension.pdf
copy to docs/detailed-results/mini/ngram-distance.pdf
index 30e67a5..b7715ed 100644
Binary files a/scripts/comparison_extension.pdf and b/docs/detailed-results/mini/ngram-distance.pdf differ
diff --git a/scripts/comparison_extension.pdf b/docs/detailed-results/mini/ngram-model.pdf
similarity index 52%
rename from scripts/comparison_extension.pdf
rename to docs/detailed-results/mini/ngram-model.pdf
index 30e67a5..9be2c4b 100644
Binary files a/scripts/comparison_extension.pdf and b/docs/detailed-results/mini/ngram-model.pdf differ
diff --git a/scripts/results_cnn_word.pdf b/docs/detailed-results/total/cnn-word.pdf
similarity index 56%
copy from scripts/results_cnn_word.pdf
copy to docs/detailed-results/total/cnn-word.pdf
index f1b017c..5e83363 100644
Binary files a/scripts/results_cnn_word.pdf and b/docs/detailed-results/total/cnn-word.pdf differ
diff --git a/scripts/results_ngrams_naive_bayes.pdf b/docs/detailed-results/total/cnn.pdf
similarity index 53%
rename from scripts/results_ngrams_naive_bayes.pdf
rename to docs/detailed-results/total/cnn.pdf
index 427b08c..590537b 100644
Binary files a/scripts/results_ngrams_naive_bayes.pdf and b/docs/detailed-results/total/cnn.pdf differ
diff --git a/scripts/results_cnn_word.pdf b/docs/detailed-results/total/naive-bayes.pdf
similarity index 57%
copy from scripts/results_cnn_word.pdf
copy to docs/detailed-results/total/naive-bayes.pdf
index f1b017c..1a02d0a 100644
Binary files a/scripts/results_cnn_word.pdf and b/docs/detailed-results/total/naive-bayes.pdf differ
diff --git a/docs/detailed-results/total/ngram-distance.pdf b/docs/detailed-results/total/ngram-distance.pdf
new file mode 100644
index 0000000..3e8f01b
Binary files /dev/null and b/docs/detailed-results/total/ngram-distance.pdf differ
diff --git a/scripts/results_cnn_word.pdf b/docs/detailed-results/total/ngram-model.pdf
similarity index 56%
rename from scripts/results_cnn_word.pdf
rename to docs/detailed-results/total/ngram-model.pdf
index f1b017c..c62945e 100644
Binary files a/scripts/results_cnn_word.pdf and b/docs/detailed-results/total/ngram-model.pdf differ
diff --git a/docs/detailed-results/total/t1_comparison_total.pdf b/docs/detailed-results/total/t1_comparison_total.pdf
new file mode 100644
index 0000000..ec33439
Binary files /dev/null and b/docs/detailed-results/total/t1_comparison_total.pdf differ
diff --git a/docs/report/bib-rapport.bib b/docs/report/bib-rapport.bib
index ef8b62a..bc3949e 100644
--- a/docs/report/bib-rapport.bib
+++ b/docs/report/bib-rapport.bib
@@ -1,389 +1,414 @@
@misc{Aylien16,
Author = {Aylien},
Date-Added = {2018-02-17 20:56:11 +0000},
Date-Modified = {2018-02-17 21:00:33 +0000},
Howpublished = {\url{http://blog.aylien.com/source-code-classification-using-deep-learning/}},
Keywords = {data science, research},
Month = {August},
Title = {Source Code Classification Using Deep Learning [blog post]},
Year = {2016}}
@misc{universal-ctags,
Author = {Universal Ctags Team},
Date-Added = {2018-02-17 20:53:07 +0000},
Date-Modified = {2018-02-17 20:54:44 +0000},
Howpublished = {\url{http://ctags.io/}},
Title = {Universal Ctags},
Year = {2001--2018}}
@misc{sloccount,
Author = {David A. Wheeler},
Date-Added = {2018-02-17 20:47:15 +0000},
Date-Modified = {2018-02-17 20:51:51 +0000},
Howpublished = {\url{https://www.dwheeler.com/sloccount/}},
Title = {SLOCCount},
Year = {2004--2018}}
@misc{cloc,
Author = {Al Danial},
Date-Added = {2018-02-17 20:46:02 +0000},
Date-Modified = {2018-02-17 20:46:38 +0000},
Howpublished = {\url{https://github.com/AlDanial/cloc}},
Title = {cloc},
Year = {2006--2018}}
@misc{guesslang,
Author = {Y. Somda},
Date-Added = {2018-02-17 20:27:54 +0000},
Date-Modified = {2018-02-17 20:43:42 +0000},
Howpublished = {\url{http://guesslang.readthedocs.io/}},
Title = {Guesslang},
Year = {2017--2018}}
@misc{linguist,
Author = {Github},
Date-Added = {2018-02-17 20:21:27 +0000},
Date-Modified = {2018-02-17 20:26:46 +0000},
Howpublished = {\url{https://github.com/github/linguist}},
Title = {Linguist},
Year = {2011--2018}}
@misc{ohcount,
Author = {Black Duck Software},
Date-Added = {2018-02-17 20:11:31 +0000},
Date-Modified = {2018-02-17 21:03:52 +0000},
Title = {Ohcount},
Howpublished = {\url{https://github.com/blackducksoftware/ohcount}},
Year = {2008--2018}}
@inproceedings{vanDam16,
Author = {J. K. v. Dam and V. Zaytsev},
Booktitle = {2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER)},
Doi = {10.1109/SANER.2016.92},
Keywords = {meta data;natural language processing;pattern classification;program diagnostics;software maintenance;text analysis;embedded code fragments;file extensions;grammar-based text analysis;keyword search;legacy code analysis;multinominal naïve Bayes;n-grams;natural language classifiers;natural language processing field;normalised compression distance;skip-grams;software artefact metadata;software language identification;statistical language models;universal IDE support;Cascading style sheets;HTML;Java;Natural languages;Software;Training;Training data;language identification;natural language processing;software language engineering},
Month = {March},
Pages = {624-628},
Title = {Software Language Identification with Natural Language Classifiers},
Volume = {1},
Year = {2016},
Bdsk-Url-1 = {http://dx.doi.org/10.1109/SANER.2016.92}}
@article{Klein11,
Archiveprefix = {arXiv},
Author = {David Klein and Kyle Murray and Simon Weber},
Bibsource = {dblp computer science bibliography, http://dblp.org},
Biburl = {http://dblp.org/rec/bib/journals/corr/abs-1106-4064},
Eprint = {1106.4064},
Journal = {CoRR},
Timestamp = {Wed, 07 Jun 2017 14:41:07 +0200},
Title = {Algorithmic Programming Language Identification},
Url = {http://arxiv.org/abs/1106.4064},
Volume = {abs/1106.4064},
Year = {2011},
Bdsk-Url-1 = {http://arxiv.org/abs/1106.4064}}
@inproceedings{Gilda17,
Author = {S. Gilda},
Booktitle = {2017 14th International Joint Conference on Computer Science and Software Engineering (JCSSE)},
Doi = {10.1109/JCSSE.2017.8025917},
Keywords = {feature extraction;learning (artificial intelligence);neural nets;pattern classification;programming languages;software engineering;source code (software);artificial neural network;convolutional neural network;file extension;intelligent feature extraction;multilayer neural network;neural networks;programming languages;software development industry;source code classification;supervised learning;word embedding layers;Feature extraction;HTML;Syntactics;Training;Artificial neural network;Feature extraction;Multi-layer neural network;Supervised learning},
Month = {July},
Pages = {1-6},
Title = {Source code classification using Neural Networks},
Year = {2017},
Bdsk-Url-1 = {http://dx.doi.org/10.1109/JCSSE.2017.8025917}}
@article{Zevin17,
Archiveprefix = {arXiv},
Author = {Shaul Zevin and Catherine Holzem},
Bibsource = {dblp computer science bibliography, http://dblp.org},
Biburl = {http://dblp.org/rec/bib/journals/corr/ZevinH17},
Eprint = {1703.07638},
Journal = {CoRR},
Timestamp = {Wed, 07 Jun 2017 14:41:28 +0200},
Title = {Machine Learning Based Source Code Classification Using Syntax Oriented Features},
Url = {http://arxiv.org/abs/1703.07638},
Volume = {abs/1703.07638},
Year = {2017},
Bdsk-Url-1 = {http://arxiv.org/abs/1703.07638}}
@inproceedings{Ugurel02,
Acmid = {775141},
Address = {New York, NY, USA},
Author = {Ugurel, Secil and Krovetz, Robert and Giles, C. Lee},
Booktitle = {Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
Doi = {10.1145/775047.775141},
Isbn = {1-58113-567-X},
Location = {Edmonton, Alberta, Canada},
Numpages = {7},
Pages = {632--638},
Publisher = {ACM},
Series = {KDD '02},
Title = {What's the Code?: Automatic Classification of Source Code Archives},
Url = {http://doi.acm.org/10.1145/775047.775141},
Year = {2002},
Bdsk-Url-1 = {http://doi.acm.org/10.1145/775047.775141},
Bdsk-Url-2 = {http://dx.doi.org/10.1145/775047.775141}}
@inproceedings{Wang15,
author = {Peng Wang and
Jiaming Xu and
Bo Xu and
Cheng{-}Lin Liu and
Heng Zhang and
Fangyuan Wang and
Hongwei Hao},
title = {Semantic Clustering and Convolutional Neural Network for Short Text
Categorization},
booktitle = {Proceedings of the 53rd Annual Meeting of the Association for Computational
Linguistics and the 7th International Joint Conference on Natural
Language Processing of the Asian Federation of Natural Language Processing,
{ACL} 2015, July 26-31, 2015, Beijing, China, Volume 2: Short Papers},
pages = {352--357},
year = {2015},
url = {http://aclweb.org/anthology/P/P15/P15-2058.pdf},
timestamp = {Mon, 03 Aug 2015 08:13:34 +0200},
biburl = {http://dblp.org/rec/bib/conf/acl/WangXXLZWH15},
bibsource = {dblp computer science bibliography, http://dblp.org}
}
@inproceedings{Khasnabish14,
author = {Jyotiska Nath Khasnabish and
Mitali Sodhi and
Jayati Deshmukh and
G. Srinivasaraghavan},
title = {Detecting Programming Language from Source Code Using Bayesian Learning
Techniques},
booktitle = {Machine Learning and Data Mining in Pattern Recognition - 10th International
Conference, {MLDM} 2014, St. Petersburg, Russia, July 21-24, 2014.
Proceedings},
pages = {513--522},
year = {2014},
url = {https://doi.org/10.1007/978-3-319-08979-9_39},
doi = {10.1007/978-3-319-08979-9_39},
timestamp = {Wed, 17 May 2017 14:25:11 +0200},
biburl = {http://dblp.org/rec/bib/conf/mldm/KhasnabishSDS14},
bibsource = {dblp computer science bibliography, http://dblp.org}
}
@misc{Heres16,
Author = {Daniël Heres},
Howpublished = {\url{http://blog.aylien.com/source-code-classification-using-deep-learning/}},
Month = {July},
Title = {Detecting the Programming Language of Source Code Snippets using Machine Learning and Neural Networks [blog post]},
Year = {2016}}
@Inbook{Aggarwal12,
author={Aggarwal, Charu C.
and Zhai, ChengXiang},
editor={Aggarwal, Charu C.
and Zhai, ChengXiang},
title={A Survey of Text Classification Algorithms},
bookTitle={Mining Text Data},
year={2012},
publisher={Springer US},
address={Boston, MA},
pages={163--222},
abstract={The problem of classification has been widely studied in the data mining, machine learning, database, and information retrieval communities with applications in a number of diverse domains, such as target marketing, medical diagnosis, news group filtering, and document organization. In this paper we will provide a survey of a wide variety of text classification algorithms.},
isbn={978-1-4614-3223-4},
doi={10.1007/978-1-4614-3223-4_6},
url={https://doi.org/10.1007/978-1-4614-3223-4_6}
}
@article{Chen09,
title = {Feature selection for text classification with Naïve Bayes},
journal = {Expert Systems with Applications},
volume = {36},
number = {3, Part 1},
pages = {5432 - 5435},
year = {2009},
issn = {0957-4174},
doi = {https://doi.org/10.1016/j.eswa.2008.06.054},
url = {http://www.sciencedirect.com/science/article/pii/S0957417408003564},
author = {Jingnian Chen and Houkuan Huang and Shengfeng Tian and Youli Qu},
keywords = {Text classification, Feature selection, Text preprocessing, Naïve Bayes}
}
@misc{MLatB16,
Author = {Machine Learning at Berkeley},
Howpublished = {\url{https://ml.berkeley.edu/blog/2016/12/03/github/}},
Keywords = {data science, research},
Month = {December},
Title = {Github Programming Language Classification [blog post]},
Year = {2016}
}
@article{Cavnar94,
title={N-gram-based text categorization},
author={Cavnar, William B and Trenkle, John M and others},
journal={Ann arbor mi},
volume={48113},
number={2},
pages={161--175},
year={1994},
publisher={Citeseer}
}
@article{Kim15,
author = {Yoon Kim and
Yacine Jernite and
David Sontag and
Alexander M. Rush},
title = {Character-Aware Neural Language Models},
journal = {CoRR},
volume = {abs/1508.06615},
year = {2015},
url = {http://arxiv.org/abs/1508.06615},
archivePrefix = {arXiv},
eprint = {1508.06615},
timestamp = {Wed, 07 Jun 2017 14:41:17 +0200},
biburl = {https://dblp.org/rec/bib/journals/corr/KimJSR15},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{Kim14,
author = {Yoon Kim},
title = {Convolutional Neural Networks for Sentence Classification},
journal = {CoRR},
volume = {abs/1408.5882},
year = {2014},
url = {http://arxiv.org/abs/1408.5882},
archivePrefix = {arXiv},
eprint = {1408.5882},
timestamp = {Wed, 07 Jun 2017 14:40:07 +0200},
biburl = {https://dblp.org/rec/bib/journals/corr/Kim14f},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{kenlm,
author = {Kenneth Heafield},
title = {{KenLM:} Faster and Smaller Language Model Queries},
year = {2011},
month = {July},
booktitle = {Proceedings of the {EMNLP} 2011 Sixth Workshop on Statistical Machine Translation},
address = {Edinburgh, Scotland, United Kingdom},
pages = {187--197},
url = {https://kheafield.com/papers/avenue/kenlm.pdf},
}
@article{scikit-learn,
title={Scikit-learn: Machine Learning in {P}ython},
author={Pedregosa, F. and Varoquaux, G. and Gramfort, A. and Michel, V.
and Thirion, B. and Grisel, O. and Blondel, M. and Prettenhofer, P.
and Weiss, R. and Dubourg, V. and Vanderplas, J. and Passos, A. and
Cournapeau, D. and Brucher, M. and Perrot, M. and Duchesnay, E.},
journal={Journal of Machine Learning Research},
volume={12},
pages={2825--2830},
year={2011}
}
@misc{keras,
title={Keras},
author={Chollet, Fran\c{c}ois and others},
year={2015},
howpublished={\url{https://keras.io}},
}
@misc{tensorflow2015-whitepaper,
title={ {TensorFlow}: Large-Scale Machine Learning on Heterogeneous Systems},
howpublished={\url{https://www.tensorflow.org/}},
author={
Mart\'{\i}n~Abadi and
Ashish~Agarwal and
Paul~Barham and
Eugene~Brevdo and
Zhifeng~Chen and
Craig~Citro and
Greg~S.~Corrado and
Andy~Davis and
Jeffrey~Dean and
Matthieu~Devin and
Sanjay~Ghemawat and
Ian~Goodfellow and
Andrew~Harp and
Geoffrey~Irving and
Michael~Isard and
Yangqing Jia and
Rafal~Jozefowicz and
Lukasz~Kaiser and
Manjunath~Kudlur and
Josh~Levenberg and
Dandelion~Man\'{e} and
Rajat~Monga and
Sherry~Moore and
Derek~Murray and
Chris~Olah and
Mike~Schuster and
Jonathon~Shlens and
Benoit~Steiner and
Ilya~Sutskever and
Kunal~Talwar and
Paul~Tucker and
Vincent~Vanhoucke and
Vijay~Vasudevan and
Fernanda~Vi\'{e}gas and
Oriol~Vinyals and
Pete~Warden and
Martin~Wattenberg and
Martin~Wicke and
Yuan~Yu and
Xiaoqiang~Zheng},
year={2015},
}
@article{Gepperth16,
Abstract = {We present a biologically inspired architecture for incremental learning that remains resource-efficient even in the face of very high data dimensionalities (>1000) that are typically associated with perceptual problems. In particular, we investigate how a new perceptual (object) class can be added to a trained architecture without retraining, while avoiding the well-known catastrophic forgetting effects typically associated with such scenarios. At the heart of the presented architecture lies a generative description of the perceptual space by a self-organized approach which at the same time approximates the neighborhood relations in this space on a two-dimensional plane. This approximation, which closely imitates the topographic organization of the visual cortex, allows an efficient local update rule for incremental learning even in the face of very high dimensionalities, which we demonstrate by tests on the well-known MNIST benchmark. We complement the model by adding a biologically plausible short-term memory system, allowing it to retain excellent classification accuracy even under incremental learning in progress. The short-term memory is additionally used to reinforce new data statistics by replaying previously stored samples during dedicated ``sleep'' phases.},
Author = {Gepperth, Alexander and Karaoguz, Cem},
Day = {01},
Doi = {10.1007/s12559-016-9389-5},
Issn = {1866-9964},
Journal = {Cognitive Computation},
Month = {Oct},
Number = {5},
Pages = {924--934},
Title = {A Bio-Inspired Incremental Learning Architecture for Applied Perceptual Problems},
Url = {https://doi.org/10.1007/s12559-016-9389-5},
Volume = {8},
Year = {2016},
Bdsk-Url-1 = {https://doi.org/10.1007/s12559-016-9389-5}}
@article{RebuffiKL16,
author = {Sylvestre{-}Alvise Rebuffi and
Alexander Kolesnikov and
Christoph H. Lampert},
title = {iCaRL: Incremental Classifier and Representation Learning},
journal = {CoRR},
volume = {abs/1611.07725},
year = {2016},
url = {http://arxiv.org/abs/1611.07725},
archivePrefix = {arXiv},
eprint = {1611.07725},
timestamp = {Wed, 07 Jun 2017 14:42:11 +0200},
biburl = {https://dblp.org/rec/bib/journals/corr/RebuffiKL16},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{Kemker17,
author = {Ronald Kemker and
Christopher Kanan},
title = {FearNet: Brain-Inspired Model for Incremental Learning},
journal = {CoRR},
volume = {abs/1711.10563},
year = {2017},
url = {http://arxiv.org/abs/1711.10563},
archivePrefix = {arXiv},
eprint = {1711.10563},
timestamp = {Mon, 04 Dec 2017 18:34:59 +0100},
biburl = {https://dblp.org/rec/bib/journals/corr/abs-1711-10563},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DiCosmo17,
author = {Di Cosmo, Roberto and Stefano Zacchiroli},
title = {Software Heritage: Why and How to Preserve Software Source Code},
abstract = {Software is now a key component present in all aspects of our society. Its preservation has attracted growing attention over the past years within the digital preservation community. We claim that source code ``the only representation of software that contains human readable knowledge'' is a precious digital object that needs special handling: it must be a first class citizen in the preservation landscape and we need to take action immediately, given the increasingly more frequent incidents that result in permanent losses of source code collections. In this paper we present Software Heritage, an ambitious initiative to collect, preserve, and share the entire corpus of publicly accessible software source code. We discuss the archival goals of the project, its use cases and role as a participant in the broader digital preservation ecosystem, and detail its key design decisions. We also report on the project road map and the current status of the Software Heritage archive that, as of early 2017, has collected more than 3 billion unique source code files and 700 million commits coming from more than 50 million software development projects.},
year = {2017},
booktitle = {iPRES 2017: 14th International Conference on Digital Preservation},
}
+
+@article{Klein11,
+ author = {David Klein and
+ Kyle Murray and
+ Simon Weber},
+ title = {Algorithmic Programming Language Identification},
+ journal = {CoRR},
+ volume = {abs/1106.4064},
+ year = {2011},
+ url = {http://arxiv.org/abs/1106.4064},
+ archivePrefix = {arXiv},
+ eprint = {1106.4064},
+ timestamp = {Wed, 07 Jun 2017 14:41:07 +0200},
+ biburl = {https://dblp.org/rec/bib/journals/corr/abs-1106-4064},
+ bibsource = {dblp computer science bibliography, https://dblp.org}
+}
+
+
+@online{GitHub,
+ author = {GitHub},
+ title = {GitHub Facts},
+ year = 2018,
+ howpublished={\url{https://github.com/about/facts}},
+ urldate = {2018-06-20}
+}
\ No newline at end of file
diff --git a/docs/report/report-en.pdf b/docs/report/report-en.pdf
index 18883c0..e909f41 100644
Binary files a/docs/report/report-en.pdf and b/docs/report/report-en.pdf differ
diff --git a/docs/report/report-en.tex b/docs/report/report-en.tex
index b829ef5..40a148f 100644
--- a/docs/report/report-en.tex
+++ b/docs/report/report-en.tex
@@ -1,718 +1,728 @@
\documentclass[a4paper,12pt]{article}
\usepackage[a4paper,left=3cm,right=3cm,top=3cm,bottom=3cm]{geometry}
\usepackage[english]{babel}
\usepackage[parfill]{parskip}
\usepackage{graphicx}
\usepackage{xeCJK}
\setCJKmainfont{Songti SC Light}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{xunicode}
\usepackage[utf8]{inputenc}
\usepackage[charter]{mathdesign}
\usepackage{url}
\usepackage{hyperref}
\usepackage{multirow}
\usepackage[toc,page]{appendix}
\usepackage{tabularx}
\usepackage{longtable}
\usepackage{listings}
\lstset{basicstyle=\footnotesize\ttfamily,breaklines=true, upquote=true}
\usepackage{textcomp}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage[labelfont={small,sc}, font={small}]{caption}
\DeclareTextCommand{\nobreakspace}{T1}{\leavevmode\nobreak\ }
\title{Large-scale Programming Language Detection}
-\author{Yuan YIN \\ \small{Supervisors: Roberto Di Cosmo, Stefano Zacchiroli}}
+\author{Yuan YIN \\ \small{Supervisor: Stefano Zacchiroli}}
\begin{document}
\maketitle
\begin{abstract}
- In Software Heritage, it is significant to recognise the language of files in the archive for further application. However, the only available way to perceive the language in which a plain text document is written is to recognise from the document itself. Programming Language Detection is a problem aiming at building a function that calculates and decides which language is used in a document. In this report, we investigate current techniques and tools for the detection task then test several relevant approaches.
+ In large code bases, it is significant to recognise the language of files in the archive for further application. However, the only available way to detect the language in which a plain text document is written is to recognise from the document itself without filename and extension. Programming Language Detection is a problem aiming at building a function that calculates and decides which language is used in a document. In this report, we investigate current techniques and tools for the detection task then test several relevant approaches.
- For the evaluations of supervised learning methods, we build a dataset containing more than 5 millions files from GitHub, written in 374 languages. We then practice some of text categorisation methods in Natural Language Processing (NLP) in our experimentations, \emph{i.e.} $n$-gram frequency profile distance, Multinomial Naïve Bayes (MNB), $n$-gram model, word-level and byte-level convolution neural networks (ConvNet). The most performing method, byte-level ConvNet method, achieves an accuracy of 88.64\% in our test set with full language list. We then apply the classifier to a subset of the archive and check manually if document's inherent language corresponds to its projection by ConvNet. It reaches only around 66\% in the real world application due to the inequality between classes of the model and the impurity of the training set.
+ For the evaluations of supervised learning methods, we build a dataset containing more than 5 millions files from GitHub, written in 374 languages. We then practice some of text categorisation methods in Natural Language Processing (NLP) in our experimentations, \emph{i.e.} $n$-gram frequency profile distance, Multinomial Naïve Bayes (MNB), $n$-gram model, word-level and byte-level convolution neural networks (ConvNet). The most performing method, byte-level ConvNet method, achieves an accuracy of 88.64\% in our test Software Heritage set with full language list. We then apply the classifier to a subset of the archive and check manually if document's inherent language corresponds to its projection by ConvNet. It reaches only around 66\% in the real world application, allegedly due to the inequality between classes of the model and the impurity of the training set.
Besides, we investigate several further subjects for more complex demands of Software Heritage, \emph{e.g.} to discover newly incoming languages by unsupervised learning, to integrate these new languages (with or without regenerating the function from training set) to the model. We know that with current available techniques it is inevitable that the quality of models will degrade after adding new classes. Nevertheless, these possible development paths of our methods are still interesting for further discovery.
\end{abstract}
\clearpage
\tableofcontents
\clearpage
\section{Introduction}
-Programming Language Detection is a problem of identifying which programming language is a piece of source code written in. We here define the piece of source code as a textual sequential representation of an artefact, which is normally in the form of character sequence or, more generally, byte sequence. More precisely, the objective is to build a model that predicts the language of a given sequence.
+Programming Language Detection is the problem of identifying in which programming language a piece of source code is written. \cite{Klein11, vanDam16} We here define the piece of source code as a textual sequential representation of an artefact, which is normally in the form of character sequence or, more generally, byte sequence. More precisely, the objective is to build a model that predicts the language of a given sequence.
-The formal definition of the problem as follows: on the input, given a byte sequence $d$ and $n$ languages,
+The formal definition of the problem as follows: On the input, a byte sequence $d$ and a set of $n$ languages $\{l_1, ..., l_n\}$ is given. On the output,
\[l_d = \underset{l_i\in \{l_1, ..., l_n\}}{\arg \max}\ m(d, l_i),\]
-where $l_d$ is the projected language, model $m$ calculates a value indicating the likelihood of a document written in language $l_i$ and the most likely one is chosen as the recognised language of the document.
+where $l_d$ is the projected language, $m$ is a model that calculates a value indicating the likelihood of the document $d$ written in language $l_i$. The most likely language $l_d$ is chosen by $\arg \max$ and attributed to the document as its recognised language.
-In general, Programming Language Detection could be utilised in different situations, here are several example applications: language composition of software project in version control systems. For example, GitHub team is developing the project Linguist to return which languages are the project written in; code searching in plain text, in order to track the popularity of a language; language detection helps also IDEs to choose the language whose support functionalities, like syntax highlighting, are implemented.
+In general, Programming Language Detection could be utilised in different situations, here are several example applications: language composition of software project in version control systems. For instance, GitHub team is developing the project Linguist to return which languages are the project written in; code searching in plain text, in order to track the popularity of a language; language detection helps also IDEs to choose the language whose support functionalities, like syntax highlighting, are implemented.
-We dive into this problem in the context of Software Heritage\footnote{\url{https://www.softwareheritage.org/}}. Software Heritage, initiated by Inria, is an archive in which more than 4.5 billions source code files from over 83 millions projects are collected (June 2018). Its aim is to collect and preserve the precious but fragile source code containing human readable knowledge. \cite{DiCosmo17} The ``large scale'' profile of the problem is not only about the size of archive but also the scale of languages should be recoginised. The reason why the language detection is requested by Software Heritage is that the language of a file could not be found in its filename extension. In Software Heritage, every source code file is a blob which contains raw content of the file, that means a sequence of bytes without any extra information, such as filename (including filename extension), metadata, \emph{etc}. Since each blob could be represented by an intrinsic identifier generated from the blob itself, the duplication of files is avoided. For this reason, all existing tools depending on filenames fail in our context, and the methods for recognising the language from a sequence of bytes is strongly demanded.
+We dive into this problem in the context of Software Heritage\footnote{\url{https://www.softwareheritage.org/}}. Software Heritage, initiated by Inria, is an archive in which more than 4.5 billions unique source code files from over 83 millions projects are collected (June 2018). Its aim is to collect and preserve the precious but fragile source code containing human readable knowledge.~\cite{DiCosmo17} The ``large scale'' profile of the problem is not only about the size of the archive but also the amount of languages that should be recognised.
-In this report, we introduce briefly the state-of-the-art methods in Section 2. In Section 3, the procedure of making a feasible dataset is related. In Section 4, we explain the methods that we took in account for the evaluation. Experimental results including the comparison between methods and the observation on certain questions are described in Section 5. The best performing method is finally applied to a subset of Software Heritage, Section 6 gives a preview of its performance in the real world. Section 7 draws several possible tracks for the future amelioration of the tools.
+The fact that the language of a file could not be found from its filename extension in Software Heritage adds more extra challenge on such task. In Software Heritage, every source code file is a blob which contains raw content of the file, that means a sequence of bytes without any extra information, such as filename (including filename extension), metadata, \emph{etc}. Since each blob could be represented by an intrinsic identifier generated from the blob itself, the duplication of files is avoided. For this reason, all existing tools depending on filenames fail in our context, and the methods for recognising the language from a sequence of bytes is strongly demanded.
-We provide the implemented methods and more detailed results on Forge of Software Heritage \footnote{\url{http://??}}.
+Given such specific constraints in Software Heritage, our objective is to investigate several state-of-the-art methods, to experiment them on our dataset for quantitative evaluation and qualitative analysis.
+
+In this report, we introduce briefly the state-of-the-art methods in Section 2. In Section 3, the procedure of making a feasible dataset is explained. In Section 4, we explain the methods that we took in account for the evaluation. Experimental results including the comparison between methods and the observation on certain questions are described in Section 5. The best performing method is finally applied to a subset of Software Heritage, Section 6 gives a preview of its performance in the real world. Section 7 draws several possible tracks for the future amelioration of the tools.
+
+We provide the implemented methods and more detailed results in a repository on Forge of Software Heritage \footnote{\url{https://forge.softwareheritage.org/source/internship-lang-detection}}.
\section{Related Works}
-The existing approaches could be divided into two categories: practical methods and machine learning methods.
+The existing approaches for Programming Language Detection could be divided into two categories: heuristic methods and machine learning methods.
Practical methods are mostly based on several empirical or external information, basic ideas are presented as follows:
\begin{itemize}
- \item Judging from filename extension. Ohcount\cite{ohcount} and Linguist\cite{linguist} practice the detection by hashing filename extension. The problem from this straightforward method is that some extensions are related to different languages, \emph{e.g.} \texttt{*.m} refers to a file written in Objective-C or MATLAB, \texttt{*.pl} points to Python or Prolog.
+ \item Judging from filename extension. Ohcount~\cite{ohcount} and Linguist~\cite{linguist} practice the detection by projecting filename extension to corresponding language. The problem from this straightforward method is that some extensions are related to different languages, \emph{e.g.} \texttt{*.m} refers to a file written in Objective-C or MATLAB, \texttt{*.pl} points to Perl or Prolog.
\item Grammar-based approaches. The principal is to parse through all languages, which is complex in modelling and demand an heavy consumption of calculation time.
\item Heuristics approaches. Most of them, such as SLOCCount\cite{sloccount}, use predefined regular expressions to capture empirically discovered features, \emph{e.g.} a file start with ``\texttt{\#include}'' is probably written in C. Some other looks for hints in the file, such as shebang lines, Vim modelines, Emacs modelines, \emph{etc}.
\end{itemize}
-In Machine learning, the problem is regarded as a sub-problem of \emph{text categorisation} or \emph{text classification}, which means that given a piece of text, we find a function that predicts which category the text belongs to. The state-of-the-art methods build such function based on example input-output pairs, which are categorised as \emph{supervised learning}.
+In Machine learning, the problem is regarded as a variant problem of \emph{text categorisation} or \emph{natural language identification}, which means that given a piece of text, we find a function that predicts which category the text belongs to \cite{vanDam16, Gilda17}. The state-of-the-art methods build such function based on example input-output pairs, which are categorised as \emph{supervised learning}.
+
+Ugurel \emph{et al.} \cite{Ugurel02} selects firstly the features by Expected Entropy Loss for each language, then vectorise the tested document into a vector representing the presence of a selected feature. The $n$-class classification is resolved by training $n \choose 2$ Support Vector Machine (SVM) binary classifier in the form of decision tree. Van Dam and Zaytsev \cite{vanDam16} test several popular and performant methods in Natural Language Processing. Multi-nominal Naïve Bayes (MNB), one of the variants of Naïve Bayes Classifiers, utilises unified frequency of a word or a sequence of words in a byte-sequence to decide the most possibly corresponding programming language. $N$-gram model and skip-gram model calculate for each gram the possibility of its appearance after $N$ grams. Normalised Compression Distance compares a piece of compressed code to the examples in the training set, then chooses the nearest language on as projection. MNB and $N$-gram model outperform others according to the experimental results. Gilda\cite{Gilda17} adopts a general setup of Convolutional Neural Network (ConvNet) in NLP and proofs its performance.
-Ugurel \emph{et al.} \cite{Ugurel02} selects firstly the features by Expected Entropy Loss for each language, then vectorise the tested document into a vector representing the presence of a selected feature. The $n$-class classification is resolved by training $n \choose 2$ Support Vector Machine (SVM) binary classifier in the form of decision tree. Van Dam and Zaytsev \cite{vanDam16} test several popular and performant methods in Natural Language Processing. Multi-nominal Naïve Bayes (MNB), one of the variants of Naïve Bayes Classifiers, utilises unified frequency of a word or a sequence of words in a byte-sequence to decide the most possibly corresponding programming language. $N$-gram model and skip-gram model calculate for each gram the possibility of its appearance after $N$ grams. Normalised Compression Distance compares a piece of compressed code to the examples in the training set, then chooses the nearest language on as projection. MNB and $N$-gram model outperform others according to the experimental results. Gilda\cite{Gilda17} adopts a general setup of Convolutional Neurone Network (ConvNet) in NLP and proofs its performance.
+Our tested methods are partly issued from the preceding state of the art. They will be detailed with other applied algorithms in Section~4.
\section{Dataset}
-We considered either applying supervised learning and unsupervised learning for the problem. However, the usage of unsupervised learning is quite limited in classification problems (we will talk about it later in Section~7). We then focus on supervised methods.
+We considered applying both supervised learning and unsupervised learning for the problem. However, the usage of unsupervised learning is quite limited in classification problems (we will talk about it later in Section~7). We then focus on supervised methods.
-Supervised learning methods require a dataset containing labeled inputs to train and evaluate the model. Nowadays, since Programming Language Detection is not seriously considered as an important subject in machine learning, for the reason that it could be resolved by adopting existing classifiers of ML, the articles are rarely accompanied by a publicly available dataset. Therefore, we natively build a novel dataset for our experiments.
+Supervised learning methods require a dataset containing labeled inputs to train and evaluate the model. Unfortunately, the articles are rarely accompanied by a publicly available dataset. Therefore, we natively build a novel dataset for our experiments.
-GitHub\footnote{\url{https://www.github.com/}} is one of the most popular web-based hosting service for Git version control system, reporting having more than 57 million repositories. We build the dataset using GitHub for its large scale of languages included and its popularity in free software community.
+GitHub\footnote{\url{https://www.github.com/}} is one of the most popular web-based hosting service for Git version control system, reporting having 85 million repositories\cite{GitHub}. We build the dataset using GitHub for its large scale of languages included and its popularity in free software community.
\paragraph{Ground Truth Supposition}
In the context of Software Heritage, our aim is to cover as many languages as possible for classification, thus the dataset we build possesses inevitably a large amount of files, which is unaffordable to be labeled manually. We thus seek help from automatic labelling tools.
-Linguist \cite{linguist} is the tool of language detection developed by the GitHub team for unveiling the language composition in git repository, service provided on GitHub through API. There exists a command line version Linguist producing list of files by language for repository. Given that filename extensions are visible for Linguist and such features boost enormously on accuracy of classification (we will show this claim in later experiment), we suppose that the language recognised by Linguist is the ground truth language attributed to it. Since the original Linguist did not give detailed results some data description languages, \emph{i.e.} XML, JSON, we slightly modified Linguist to integrate these missing languages.
+Linguist \cite{linguist} is the tool of language detection developed by the GitHub team for unveiling the language composition in git repository, service provided on GitHub through their API. There exists a command line version Linguist producing list of files by language for repository. Given that filename extensions are visible for Linguist and such features boost enormously on accuracy of classification (we will show this claim in later experiment), we assume that the language recognised by Linguist is the ground truth language attributed to it. Since the original Linguist did not give detailed results some data description languages, \emph{i.e.} XML, JSON, we slightly modified Linguist to integrate these missing languages.
\paragraph{Source Code Recuperation and Languages Included}
The dataset is built in the context of Software Heritage. Therefore, the list of languages we consider integrating in the system covers as many languages as possible.
-We initially took the entire language list of Linguist into account for repository fetching. For each language, we fetch the first 75 repositories which top on the list ordered by number of stars, manifesting the popularity of the repository. To avoid huge repositories, we ignore all repositories whose size is superior to 150~MiB.
+We initially took the entire language list of Linguist into account for repository fetching. For each language, we fetched the first 75 repositories which top on the list ordered by number of stars, manifesting the popularity of the repository. To avoid huge repositories, we ignore all repositories whose size is superior to 150~MiB.
-We then eliminate some languages, \emph{i.e.} data description languages, which we could not fetch any repository from GitHub. We successfully fetched 5,162,128 files for 374 valid languages showed in Table~\ref{tab:lan}.
+Some languages, \emph{i.e.} data description languages were eliminated, for the reason that we could not fetch any repository of them from GitHub. We successfully fetched {5,162,128} files for 374 valid languages showed in Table~\ref{tab:lan} in Appendices.
\section{Methods for Evaluation}
In this section, we describe several NLP methods here tested on our dataset:
\begin{itemize}
\item $n$-gram-based frequency distance model,
\item $n$-gram model,
\item Multinominal Naïve Bayes (MNB), and
- \item Convolutional Neurone Networks (ConvNet).
+ \item Convolutional Neural Networks (ConvNet).
\end{itemize}
The first approach is regarded as a baseline method for the evaluation of the accuracy and the efficiency of the model.
-Given that in Software Heritage every file is only a sequence of bytes which we are not able to assert its encoding, even unable to judge whether it is a binary file or not, we are willing to discover the approaches at byte level.
+Given that every file in Software Heritage is only a sequence of bytes which we are not able to determine its character encoding, even unable to judge whether it is a binary file or not, we are willing to focus on the approaches at byte level.
\subsection{Baseline: $n$-gram-based frequency distance}
\paragraph{$n$-gram}
An $n$-gram is a slice of a larger sequence with $n$ units. In NLP, the sequence is naturally the string. Depending on different problems, an unit represents a character or a word.
-For example, the string ``\texttt{print(n)}'' with 8 characters could generate following character based $n$-grams:
+For example, the string ``\texttt{print(n)}'' with 8 characters could generate the following character based $n$-grams:
\begin{itemize}
\item unigrams: \texttt{p, r, ..., )}
\item bigrams: \texttt{\textvisiblespace p, pr, ri, ..., n), )\textvisiblespace}
\item trigrams: \texttt{\textvisiblespace\textvisiblespace p, \textvisiblespace pr, pri, rit, ..., n)\textvisiblespace, )\textvisiblespace\textvisiblespace}
\item ...
\end{itemize}
or word-based $n$-grams:
\begin{itemize}
\item unigrams: \texttt{, print, (, n, ), }
\item bigrams: \texttt{ print, print (, ( n, n ), ) }
\item trigrams: \texttt{ print (, print ( n, ( n ), n ) }
\item ...
\end{itemize}
Strings are often padded with start marker \texttt{} and end marker \texttt{}. In general, a $k$-unity sequence generates exactly $k-(n-1)$ n-grams.
-Cavnar and Trenkle \cite{Cavnar94} introduce an early NLP method using the distance between two $n$-gram frequency profiles.
+Cavnar and Trenkle \cite{Cavnar94} introduce an early NLP method for text categorisation using the distance between two $n$-gram frequency profiles.
-According to Zipf's law, an empirical observation expressing that the $n$-th most common word in a human language occurs with a frequency inversely proportional to $n$. By retaining the most common words, it is possible to obtain a list describing the characteristics of the language.
+Zipf's law is an empirical observation, expressing that the $n$-th most common word in a human language occurs with a frequency inversely proportional to $n$. According to Zipf's law, by retaining the most common words, it is possible to obtain a list describing the characteristics of the language.
Given a training set, at the training phase, a bag of $n$-grams is generated for each document in the training set. By gathering all bags of a language and counting the occurrences of each $n$-gram, a list of $n$-grams ordered by number of occurrences is created as the \emph{category profile} of the class. Only the most frequent 300 $n$-grams are kept, since they are highly correlated to the language.
The \emph{distance} between category profile and document profile is defined as follows:
Given trained category profiles $p_{l_1}, ..., p_{l_k}$ for $k$ languages, and document profile $p_{d}$ of test document $d$,
\[
distance(p_{l_i}, p_{d}) = \sum_{w\in p_{d}} | rankdist(w, p_d, p_{l_i})|
\]
\[
rankdist(w, p_d, p_{l_i})=
\begin{cases}
|rank(w, p_d) - rank(w, p_{l_i})| & \text{if }rank(w, p_{l_i}) \text{ exists,} \\
|p_d| & \text{else}
\end{cases}
\]
where $p$ containing an ordered list of word, $rank(w, p)$ returns the rank of $w$ in list $p$. $rankdist(w, p_d, p_{l_i})$ returns the out-of-place distance between two profiles if $w$ appears in $p_{l_i}$. If $w$ is an out-of-vocabulary word, the distance is the length of document profile $p_d$.
We then categorise the document as language with minimum distance.
\subsection{Multinominal Naïve Bayes}
-This approach is introduced by van Dam and Zaytsev \cite{vanDam16}.
+This approach was introduced by van Dam and Zaytsev~\cite{vanDam16} into Programming Language Detection.
We assume in Naïve Bayes model that each word of the document is independent from each other. According to Bayes' Theorem,
\begin{eqnarray*}
P(l|w_1w_2...w_n) & = & \frac{P(w_1w_2...w_n|l)P(l)}{P(w_1w_2...w_n)} \\
& = & c\cdot P(l) P(w_1w_2...w_n|l)\\
& = & c\cdot P(l) \prod_{i = 1}^n P(w_i|l)
\end{eqnarray*}
Probability of $w_i$ in language $l$ is estimated by its occurrences in language with bag-of-word assumption:
\[
P(w_i|l) = \frac{C_l(w_i) + 1}{\sum_{w\in V}C_l(w) + |V|}
\]
where $C_l$ gives frequency of a word, $V$ is the vocabulary all languages.
Assumption of independence of words is quite limited for classification, in practice we actually use unigrams to 5-grams to replace words in the original method for taking the context of words into account.
\subsection{$n$-gram model}
-The approach is introduced by van Dam and Zaytsev\cite{vanDam16}. As the precedent method, $n$-gram model utilises also statistical properties of $n$-grams but in another way.
+The approach was also tested by van Dam and Zaytsev~\cite{vanDam16}. As the precedent method, $n$-gram model utilises also statistical properties of $n$-grams but in another way.
Originally, $n$-gram model aims at predicting the possibility of an unit after knowing $n-1$ units occurred before. Given an unit $w_i$, the probability of its occurrence in a sequence is defined as:
\[
P(w_i | w_1...w_{i-1})
\]
According to Markov assumption, we omit older context in the sequence,
\[
P(w_i | w_1...w_{i-1}) \approx P(w_i | w_{i-(n-1)}...w_{i-1})
\]
In reality, the probability could be estimated by maximum likelihood estimation (MLE):
\[
P(w_i | w_{i-(n-1)}...w_{i-1}) = \frac{C(w_{i-(n-1)}...w_{i-1}w_{i})}{C(w_{i-(n-1)}...w_{i-1})}
\]
where $C$ gives the count of given $n$-gram.
By chain rule of probability and precedent estimation,
\[
P(w_1w_2...w_n)\approx \prod_{i = 1}^n P(w_i|w_{i-(n-1)}...w_{i-1})
\]
Now we transform such model into a classifier. Given a sequence $w_1w_2...w_n$, we assume that each language $l$ appears with the same probability and the probability of a given sequence is fixed.
According to Bayes' Theorem,
\begin{eqnarray*}
P(l|w_1w_2...w_n) & = & \frac{P(w_1w_2...w_n|l)P(l)}{P(w_1w_2...w_n)} \\
& = & c\cdot P(w_1w_2...w_n|l)\\
& = & c\cdot \prod_{i = 1}^n P(w_i|w_{i-(n-1)}...w_{i-1}, l)
\end{eqnarray*}
Rather than counting $n$-grams in the document, the probability of $n$-gram is estimated from the $n$-gram frequency of language, obtained from training set.
\[
P(w_i | w_{i-(n-1)}...w_{i-1}, l) = \frac{C_l(w_{i-(n-1)}...w_{i-1}w_{i})}{C_l(w_{i-(n-1)}...w_{i-1})}
\]
where $l$ is $C_l$ gives the count of language $l$ in training set.
-While estimating the probability of $n$-grams, the smoothing techniques are required because of possible occurrence of \emph{out-of-vocabulary (OOV)} $n$-gram. In our case, Modified Kneser-Ney is applied since it is one of the methods that gives better experimental results in \cite{vanDam16}.
+While estimating the probability of $n$-grams, smoothing techniques are required because of possible occurrence of \emph{out-of-vocabulary (OOV)} $n$-gram. In our case, Modified Kneser-Ney is applied since it is one of the methods that gives better experimental results in~\cite{vanDam16}.
\subsection{Convolutional Neural Network (ConvNet)}
Convolutional Neural Network is one of the most popular machine learning branch usually used for image classification. It is a class of deep feed-forward artificial neural networks.
The following two architectures are tested in Section 4.
\subsubsection{Word-level Approach}
\label{sec:word-conv}
-Although Gilda \cite{Gilda17} shows the performance of his own architecture, we are not able to rebuild the same network due to the lack of network architecture details and hyper-parameter configuration. We move our vision to other architectures.
+Although Gilda~\cite{Gilda17} shows the performance of his own architecture, we were not able to rebuild the same network due to the lack of network architecture details and hyper-parameter configuration. We focused on other architectures.
Kim \cite{Kim14} introduces a ConvNet for natural language sentence classification. Figure~\ref{fig:word-convnet} from \cite{Kim14} illustrates the architecture of the network.
-\begin{figure}
+\begin{figure}[t]
\centering
\includegraphics[width=\textwidth]{cnn.png}
\caption{\label{fig:word-convnet}Model architecture with two channels for an example sentence. \cite{Kim14}}
\end{figure}
\paragraph{Word Embedding}
-In this architecture, word is the unit of the input. The $i$-th word $w_i$ is transformed into a vector $\mathbf{x}_i \in \mathbb{R}^k$ by word embedding level using \texttt{word2vec}. Word vectors are then concatenated to form the representation of the document, an $n\times k$ matrix.
+In this architecture, word is the unit of the input. The $i$-th word $w_i$ is transformed into a vector $\mathbf{x}_i \in \mathbb{R}^k$ by word embedding level. Word vectors are then concatenated to form the representation of the document, an $n\times k$ matrix.
The number of words $n$ of the document is fixed by the model. Therefore, a document longer than $n$ words needs to be pruned and the shorter one needs padding, by concatenating zero-vectors at the beginning or the end of the matrix.
\paragraph{Feature Extraction}
In the convolutional levels, by using a \emph{filter} $\mathbf{w_h} \in R^{hk}$, a \emph{feature} $c_i$ is then generated,
\[c_i = f(\mathbf{w_h}\cdot(\mathbf{x}_i\ ||\ \mathbf{x}_{i+1}\ ||\ ...\ ||\ \mathbf{x}_{i+h-1}) + b)\]
where $||$ is vector concatenate operator, $b\in \mathbb{R}$ is a bias term, $f$ is an \emph{activation function} outputting a feature from a set of inputs.
This procedure utilises the similar principle of $n$-gram model, but rather than extracting features from original words, ConvNet works on their vector representation.
Each filter produces a \emph{feature map}, a vector $\mathbf{c}^h\in \mathbb{R}^{n - h+1}$. A max-over-time-pooling is then applied on the feature map $\mathbf{c}^h$, aiming at choosing the most important features with the highest values and avoiding overfitting at training stage. We then obtain the final feature map of this $h\times k$ filter.
Several filters are often applied to obtain the corresponding feature map, representing a \emph{channel}. They are then concatenated vertically into a final feature map $\mathbf{c}$.
\paragraph{Classification}
\emph{Fully connected layer} is a traditional multi-layer perceptron whose neurons are all connected to every neurons of the precedent and following levels. It uses a softmax activation function in the output layer.
-Feature map $\mathbf{c}$ is then put into a fully connected layer for extracting higher level features preparing for final classification. The output of these fully connected layers gives a vector indicating the score obtained for each class. The higher the score is given, the more possible the document is categorised into this class.
+Feature map $\mathbf{c}$ is then put into a fully connected layer for extracting higher level features preparing for final classification. The output of these fully connected layers gives a vector indicating the score obtained for each class. The higher the score given, the more possible the document is categorised into this class.
\subsubsection{Byte-level Approach}
Kim \cite{Kim15} introduces a character-level ConvNet for language modelling. The original architecture is adapted by Chaitanya Joshi\footnote{\url{https://github.com/chaitjo/character-level-cnn}} for achieving a classification model by replacing recurrent layers with same fully connected layers as word-level approach of Section~\ref{sec:word-conv}.
Instead of using word or token as feature, character-level approach could make use of character (or byte) without building a large vocabulary. Although the size of vocabulary is commonly considerably small, \emph{e.g.} 256 when we use every byte as character.
Feature extraction and classification are similar to the word-level approach.
\section{Experimentations}
-In this section, we present several questions that we are willing to answer by experiments on our customised dataset.
+In this section, we present several questions that we would like to answer by experiments on our customised dataset.
\subsection{Implementation and System Setup}
We implement the methods described in Section 4 in Python 3, in order to finally integrate one of them in Software Heritage.
Baseline method is implemented natively in Python. We implement MNB using Scikit-Learn. $n$-gram model is implemented with KenLM \cite{kenlm}. The last two ConvNets are both implemented with Keras \cite{keras} using TensorFlow \cite{tensorflow2015-whitepaper} as backend.
-We execute principally the training and test phase on a portable computer with 2.7 GHz Intel Core i5 processor running macOS 10.13. The training phase of two ConvNet methods are executed in an instance running Ubuntu 16.04 with one Intel Sandy Bridge virtual CPU, equipped with one NVIDIA Tesla K80 GPU on Google Cloud Platform. The instance is configured for making use of TensorFlow backend with GPU acceleration using CUDA Deep Neural Network Library (cuDNN).
+We execute principally the training and test phase on a portable computer with 2.7 GHz Intel Core i5 processor running macOS 10.13. The training phase of two ConvNet methods are executed in an virtual machine running Ubuntu 16.04 with one Intel Sandy Bridge virtual CPU, equipped with one NVIDIA Tesla K80 GPU on Google Cloud Platform. The VM is configured for making use of TensorFlow backend with GPU acceleration using CUDA Deep Neural Network Library (cuDNN).
\subsection{Training Set and Test Set}
-Files of the training set are randomly picked from the dataset at the first time. To avoid the imbalance of the training set that impacts the performance of several methods in Section 4, we restrain the maximum number of training files to 500 for each language. The test set is then built from remaining samples, it includes up to 1000 files for testing.
+Firstly, files of the training set are randomly picked from the dataset. To avoid the imbalance of the training set that impacts the performance of several methods in Section~4, we restrain the maximum number of training files to 500 for each language. The test set is then built from remaining samples, it includes up to {1,000} files for testing.
We built 3 series of training set and test set of different sizes:
\begin{itemize}
\item \texttt{mini}: 20 languages in \cite{vanDam16} , 10,000 training files, 20,000 test files.
\item \texttt{less}: 127 languages with more than 5,000 files collected in dataset, 63,500 training files, 127,000 test files.
- \item \texttt{total}: 374 languages in Table~\ref{tab:lan}, 157,897 training files, 286,224 test files.
+ \item \texttt{total}: 374 languages in Table~\ref{tab:lan} in Appendices, 157,897 training files, 286,224 test files.
\end{itemize}
\subsection{Tokenisation}
In our case, tokenisation is useless for byte-level applications of method. The interest to introduce a simple general tokeniser is to break a document into words for making use of word-based methods.
It is difficult to summarise the relationship between programming language alphabet and its byte representation. We empirically suppose that most of the programming languages share some basic characters, \emph{e.g.} latin alphabet, parentheses, space, \emph{etc.} and most of encoding standards covers these characters in common.
A binary document is broken by a set of characters (operators, punctuations, spaces, \emph{etc.}) and numbers (integer, float, \emph{etc.}). All separators are retrieved after splitting.
For example, for the string ``\verb|print ("Hello world! 你好，世界！")|'' with UTF-8 encoding, its byte representation is
\begin{lstlisting}
-"Hello world! \xe4\xbd\xa0\xe5\xa5\xbd\xef\xbc\x8c\xe4\xb8\x96\xe7\x95\x8c\xef\xbc\x81".
+'print ("Hello world! \xe4\xbd\xa0\xe5\xa5\xbd\xef\xbc\x8c\xe4\xb8\x96\xe7\x95\x8c\xef\xbc\x81")'
\end{lstlisting}
It is then tokenised to a sequence of 12 words:
\begin{lstlisting}
'print', ' ', '(', '"', 'Hello', ' ', 'world', '!', ' ', '\xe4\xbd\xa0\xe5\xa5\xbd\xef\xbc\x8c\xe4\xb8\x96\xe7\x95\x8c\xef\xbc\x81', '"', ')'
\end{lstlisting}
\subsection{Model Quality Metrics}
For a class $c$, test results of documents could be regrouped into 4 categories, we mark $\hat{y_i}$ as ground truth class label, $y_i$ as predicted label:
\begin{itemize}
\item True Positive (TP): when $\hat{y_i} = l$ and $y_i = l$, \emph{i.e.} document written in $l$ is recognised as the same language.
\item False Positive (FP): when $\hat{y_i} \neq l$ and $y_i = l$, \emph{i.e.} document not written in languag $l$ is incorrectly recognised as $l$.
\item True Negative (TN): when $\hat{y_i} \neq l$ and $y_i \neq l$, \emph{i.e.} document not written in $l$ is rejected by $l$.
\item False Negative (FN): when $\hat{y_i} = l$ and $y_i \neq l$, \emph{i.e.} document written in $l$ is incorrectly rejected by $l$.
\end{itemize}
In the context of classification, the quality of methods is measured by Precision, Recall and $F_1$ score.
Recall is also called True Positive Rate (TPR). It is the fraction of correctly classified samples over all samples should be predicted as in $c$:
\[\text{recall} = \frac{\text{\#TP}}{\text{\#TP}+\text{\#FN}}\]
Precision is also called Positive Predictive Value (PPV). It is the fraction of correctly classified samples over all samples predicted as in $c$:
\[\text{precision} = \frac{\text{\#TP}}{\text{\#TP}+\text{\#FP}}\]
The harmonic mean of precision and recall is called $F_1$ score, introduced for balancing two metrics:
\[
F_1 = \left(\frac{\text{precision}^{-1} + \text{recall}^{-1}}{2}\right)^{-1} = 2\cdot\frac{\text{precision}\cdot\text{recall}}{\text{precision}+\text{recall}}
\]
In following subsections, we use $F_1$ as the measurement of the model quality of each class' performance.
Global model quality is evaluated by accuracy score:
\[
\text{accuracy}(y,\hat{y}) = \frac{1}{n}\sum_{i=0}^{n-1}1(y_i = \hat{y}_i)
\]
where $y$ is the predicted labels, $\hat{y}$ is the ground truth labels, $n$ is the number of samples, $1(\cdot)$ is the indicator function. The score shows the ratio of the number of samples whose projected label is the same as its ground truth to the total number of samples.
\subsection{Experimental Results}
+This section contains the most significant results obtained during the experimentation. For more detailed results (confusion matrices, comparison of $F_1$ for each language between all tested methods), please check out the formerly provided repository of our work.
+
\subsubsection{Quality of Models}
-The evaluation of the quality of models utilises the entire list of 374 languages.
+The evaluation of the quality of models utilises the entire list of 374 languages.
\paragraph{Overall Quality}
Table~\ref{tab:total-comp} shows that baseline method reaches only 46.68\% of overall accuracy. Byte-level ConvNet marks the best accuracy at 88.64\% which is much higher than word-level ConvNet. Both MNB and $n$-gram model reach acceptable results respectively at 85.70\% and 84.42\%.
\begin{table}[t]
\centering
\begin{tabular}{|c|c|}
\hline
& Accuracy / \% \\ \hline
Baseline & 46.48 \\
MNB & 85.70 \\
$n$-gram model & 84.42 \\
Word-level ConvNet & 77.19 \\
Byte-level ConvNet & 88.64 \\ \hline
\end{tabular}
\caption{\label{tab:total-comp} Comparison of accuracy between evaluation methods.}
\end{table}
\paragraph{Inequality Between Classes} Although the overall score of Byte-level ConvNet reaches 88.64\%, $F_1$ score of several classes is much lower than the average. For instance, $F_1$ of Eagle reaches 99.6\%, meanwhile C achieves only 58.8\%. Figure~\ref{fig:ineq} illustrates huge gap between best and worst results.
\begin{figure}[t!]
\centering
\subfloat[][25 language with highest $F_1$]{
\includegraphics[height=0.4\textwidth]{./comparison_cnn_f1_above}
}
\subfloat[][25 language with least $F_1$]{
\includegraphics[height=0.4\textwidth]{./comparison_cnn_f1_below}
}
\caption{\label{fig:ineq} Inequality between the most performing classes and least performing classes.}
\end{figure}
\paragraph{Interclass Confusion}
Some languages are especially difficult to distinguish from each other for these methods. We visualise the confusion matrices of methods in our repository in order to give several intuitive observations.
There are significant confusions between similar languages, \emph{i.e.} C and C++; Objective-C, Objective-C++ and Objective-J; Befunge and HyPhy; Java and Processing; NetLinx, PAWN and Ruby; Javascript and Cycript, \emph{etc}.
\subsubsection{Benchmark and Model Sizes}
Table~\ref{tab:ben-train} shows that the first three basic NLP methods could be rapidly trained on CPU even when a large number of classes are considered. ConvNet methods demand more computing power in training stage. On the contrary, ConvNets classify a document over 10 times faster than other $n$-gram based approaches.
\begin{table}[t]
\centering
\begin{tabular}{|c|c|c|c|}
\hline
& \multirow{2}{*}{Training Time} & Test Time & \multirow{2}{*}{Model Size}\\
& & (per file)&\\
\hline
Baseline & 1.8 h & 0.12 s & 3.8 MiB \\
MNB & 0.7 h & 2 s & 323.0 MiB \\
$n$-gram model & 0.8 h & 1.2 s & 663.1 MiB \\
\multirow{2}{*}{Word-level ConvNet} & 40.6 h & \multirow{2}{*}{0.01 s} & \multirow{2}{*}{313.3 MiB}\\
& (18.2 h*) & & \\
\multirow{2}{*}{Byte-level ConvNet} & 20.8 h & \multirow{2}{*}{0.01 s} & \multirow{2}{*}{32.8 MiB} \\
& (1.6 h*) & & \\
\hline
\end{tabular}
\footnotesize{*: Training time on distant VM using GPU.}
\caption{\label{tab:ben-train} Comparison of training time and test time benchmark on the same computer with model size.}
\end{table}
\subsubsection{Filename Extension Is Important}
-We know empirically that filename extension is a critical feature of classification. However, we hope to find out how important it is. Knowing that ConvNet is good at highlighting features that distinguish mostly the inputs, we test the performance using Byte-level ConvNet by adding the extension of the file to the input.
+We know empirically that filename extension is a critical feature of Programming Language Detection. However, we would like to evaluate its importance by tests. Knowing that ConvNet is good at highlighting features that distinguish mostly the inputs, we test the performance using Byte-level ConvNet by adding the extension of the file to the input.
-For convenience, we test only for 20 languages in the list. Table~\ref{tab:ext} shows that by adding the extension into the code the detection accuracy could be dramatically improved.
+For convenience, we test only for 20 languages in the list. Table~\ref{tab:ext} shows that by adding the extension into the code the detection accuracy could be visibly improved.
\begin{table}[t]
\centering
\begin{tabular}{|c|c|}
\hline
& Accuracy / \%\\
\hline
Without Extension & 94.53 \\
With Extension & \textbf{97.61} \\
\hline
\end{tabular}
\caption{\label{tab:ext} Comparison of accuracy with extension and accuracy without extension with Byte-level ConvNet Classification on 20 classes.}
\end{table}
\subsubsection{Word or Byte}
Our choice of applying tested methods at byte-level is competitive with the word-level applications. We each family of methods at these two levels on \texttt{mini} training and test sets. Table~\ref{tab:w-b} indicates that byte-level methods perform better for MNB and ConvNet, $n$-gram model drops slightly after switched to byte-level.
-\begin{table}[h]
+\begin{table}[t]
\centering
\begin{tabular}{|c|c|c|}
\hline
&\multicolumn{2}{c|}{Accuracy / \%} \\
\cline{2-3}
& Word & Byte \\
\hline
Baseline & 68.47 & 62.14 \\
MNB & 89.19 & 92.04\\
$n$-gram model & 92.22 & 88.42 \\
ConvNet & 90.42 & 94.53 \\
\hline
\end{tabular}
\caption{\label{tab:w-b} Comparison of accuracy between word-level and byte-level application of tested methods on \texttt{mini} test set.}
\end{table}
\section{Application in Software Heritage}
-We apply Byte-level ConvNet, the most performing method, to a subset of Software Heritage archive, containing more than 17 millions files (around 0.1\% of the archive). However, we are not able to check the results one by one. Several folders are therefore selected for evaluation.
+We have applied Byte-level ConvNet, the most effective method, to a subset of the Software Heritage archive, containing more than 16 millions files (around 0.1\% of the archive). However, we were not able to check the results one by one because we were not equipped with other reliable automatic checking tool providing such large amount of languages and we should evaluate them manually by human efforts. For that reason, only several folders are therefore picked for evaluation by hand.
\subsection{Manual Verification Results}
Since we have nothing but the content of each file to judge its language in this dataset, the following results are based on author's acquired knowledge with the help of searching engine and other assistant tools. The results here are indicative.
-Table~\ref{tab:manual} indicates the test accuracy of more than a thousand files manually checked by author using a graphic interface. After the analysis of tested samples, errors could normally categorised into the following cases:
+We picked 5 folders with 1,259 files from the subset for evaluation using a graphic interface. Unfortunately, the overall accuracy reaches only at 66.05\%, fairly far from our experimental accuracy (88.64\%).
+
+After analysing tested samples, we know that errors could normally categorised into the following cases:
\begin{itemize}
\item Short files. These files containing short code snippet are even indistinguishable for human.
\item Non-text files. Documentations consist usually of PDF documents, PNG or JPEG photos are surely misclassified.
\item ConvNet does not work well for many popular languages. From the results of former section, massively appearing languages, such as C, C++, HTML, are more often wrongly classified.
\end{itemize}
\begin{table}[t]
\centering
\begin{tabular}{|c|c|}
\hline
& Accuracy / \% \\
\hline
Subset 1 & 72.53 \\
Subset 2 & 67.05 \\
Subset 3 & 59.11 \\
Subset 4 & 67.54 \\
Subset 5 & 63.45 \\
\hline
Overall & 66.05 \\
\hline
\end{tabular}
\caption{\label{tab:manual} Test results of manual checking on subsets of the archive.}
\end{table}
\paragraph{Recourse}
Libmagic is an efficient library differentiating plain text files and other formatted files. It is also reliable while recognising the popular languages. We decide to abandon some particular classes which is often misclassified by ConvNet and covered by Libmagic at the same time.
\section{Challenges of Large-scale Deployment}
\subsection{Imbalance Between Languages}
Imbalance in dataset between classes could affect the performance of different models in many ways. For the approaches essentially based on statistics, \emph{i.e.} $n$-gram frequency, $n$-gram model, a small training set means that it is possible that we could not fetch enough features. For ConvNet approaches, apart from the former reason, ConvNets intend to ignore smaller classes to avoid errors.
-Despite of our efforts on balancing the number of repositories for each class, a significant imbalance is eventually observed between language classes. We know from Figure~\ref{fig:distribution} that the first half of dataset consists of 13 languages, 361 other languages share the another half. Nearly a half of languages possess less than 5,000 files, and two third of these own less than 1,000 files.
+Despite our efforts on balancing the number of repositories for each class, a significant imbalance is eventually observed between language classes. We know from Figure~\ref{fig:distribution} that the first half of dataset consists of 13 languages, 361 other languages share the another half. Nearly a half of languages possess less than 5,000 files, and two third of these own less than 1,000 files.
-In future works, we are willing to fetch a more balanced database for each language and enrich weaker classes during the real deployment on the archive.
+In future work, we are willing to fetch a more balanced database for each language and enrich weaker classes during the real deployment on the archive.
\subsection{Recognising New Languages}
The real challenges come from changes over time. In order to recognise as many languages as possible, our language list should be able to grow through the time. Unfortunately, the existing performing methods fix \emph{a priori} a list of languages and focus on distinguish between them.
On the one hand, despite our efforts for fetching as many languages as possible, it is already impossible to list all existing languages. On the other hand, we have no idea about how many new languages will appear in the archive.
Therefore, in this subsection, we will note several attempts on discovering new classes and discuss the extensibility of models in following parts.
\subsubsection{Discovering New Languages}
-Unsupervised Learning is the machine learning task finding a model indicating inherent structures of unlabelled data. Clustering is one of the topic on finding potential new self-forming classes in feature space. Since new languages are still unknown for us, we focus here on hierarchical clustering, which does not demand \emph{a priori} a fixed number of new classes.
+Unsupervised Learning is the machine learning task of finding a model indicating inherent structures of unlabelled data. Clustering is one of the topic on finding potential new self-forming classes in feature space. Since new languages are still unknown for us, we focus here on hierarchical clustering, which does not demand \emph{a priori} a fixed number of new classes.
-\paragraph{Agglomerative Hierarchical Clustering}
+\paragraph{Agglomerative Hierarchical Clustering (AHC)}
-Agglomerative Hierarchical Clustering (AHC) is the mostly considered Hierarchical Clustering approach. It is a type of bottom-top approach.
+AHC, the mostly applied Hierarchical Clustering method, is a bottom-top approach.
-We call the sample without label an \emph{observation}. Given $n$ observations $\{o_1,o_2,...,o_n\}$, a distance is calculated with a \emph{pairwise metric} for each pair of documents, resulting $O(n^2)$ distances. At the first time, every single observation is a cluster. By applying a \emph{linkage criteria}, two of clusters are combined as a single cluster. The algorithm terminate when there is only one cluster containing $n$ observations for gathering.
+We call the sample without label an \emph{observation}. Given $n$ observations $\{o_1,o_2,...,o_n\}$, a distance is calculated with a \emph{pairwise metric} for each pair of documents, resulting $O(n^2)$ distances. At first, every single observation is a cluster. By applying a \emph{linkage criteria}, two of clusters are combined as a single cluster. The algorithm terminate when there is only one cluster containing $n$ observations for gathering.
-The clustering is tested firstly on the most popular 20 languages. Unfortunately, it does not work as we expected. By varying pairwise metric and linkage criteria, we obtained a slightly more performing combination: euclidean distance and average linkage. However, Figure~\ref{fig:clusters} shows that no language is able to form a huge (as original number of observations of a class), visible and pure agglomeration of the same language. Most of them are equally mixed up inside a cluster. We will continually discover other methods other than AHC for this task in the future.
+The clustering is tested firstly on the most popular 20 languages. Unfortunately, it does not work as we expected. By varying pairwise metric and linkage criteria, we obtained a slightly more performing combination: euclidean distance and average linkage. However, Figure~\ref{fig:clusters} shows that no language is able to form a huge (as original number of observations of a class), visible and pure agglomeration of the same language. Most of them are equally mixed up inside a cluster. Clearly, other methods are needed to be for this task in the future.
-\begin{figure}
+\begin{figure}[t]
\centering
\includegraphics[width=\textwidth]{clusters}
\caption{\label{fig:clusters} Top 20 clusters of Agglomerative Hierarchical Clustering. AHC is applied in \texttt{mini} training set for 20 languages, 500 observations for each language.}
\end{figure}
\subsubsection{Extensibility of Existing Models}
Once discovered, new classes need to be integrated into the existing model. Since the Baseline method, $n$-gram model and MNB demand a profile stocking statistics for each language, it suffices to train the incoming supplementary training sets and simply add the profiles into the model. On the contrary, ConvNet approaches should be retrained with a new network. However, no matter how we integrate these classes into original models, the quality of models will drop when more classes are added.
\paragraph{Impact of Retraining with More Classes}
-The objective of Software Heritage is to recognise as many languages as possible. Therefore it is inevitable to integrate new languages to older classifier. We test 3 series of training and test sets in order to discover the impact of number of classes on global results and the deterioration of $F_1$ for commonly appeared languages.
+In the context of Software Heritage, we need to be able to recognise as many languages as possible. Therefore it is inevitable to integrate new languages to older classifier. We test 3 series of training and test sets in order to discover the impact of number of classes on global results and the deterioration of $F_1$ for commonly appeared languages.
-\begin{table}[h]
+\begin{table}[t]
\centering
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{c|}{Accuracy / \%} \\
\cline{2-4}
& \texttt{mini} & \texttt{less} & \texttt{total} \\
& \footnotesize{(20 languages)} & \footnotesize{(127 languages)} & \footnotesize{(374 languages)}\\
\hline
Baseline & 63.13 & 51.06 & 46.48 \\
MNB & 92.04 & 87.38 & 85.72 \\
$n$-gram model & 88.42 & 85.33 & 84.42 \\
Word-level ConvNet & 90.42 & 85.78 & 77.19\\
Byte-level ConvNet & 94.53 & 91.71 & 88.64 \\
\hline
\end{tabular}
\caption{\label{tab:size} Comparison of accuracy score for each method on 3 series of training and test sets.}
\end{table}
Table~\ref{tab:size} compares the global accuracy scores of each series and each approach. We figure out that along with the growth of number of classes, the accuracy drops for all methods. From 20 languages to 374 languages, the baseline method loses 16.65\%, while $n$-gram model loses only 4\%.
Figure~\ref{fig:size} shows that the recognition quality of earlier integrated languages drops on most occasions, especially for those languages which are often the root of later introduced languages.
\begin{figure}[t!]
\centering
\subfloat[Baseline]{
\includegraphics[height=8cm]{./comparison_ngram_dist_size.pdf}
}
\subfloat[MNB]{
\includegraphics[height=8cm]{./comparison_bayes_size.pdf}
}
\subfloat[$n$-gram]{
\includegraphics[height=8cm]{./comparison_ngram_prob_size.pdf}
}
\subfloat[Word ConvNet]{
\includegraphics[height=8cm]{./comparison_cnn_word_size.pdf}
}
\subfloat[Byte ConvNet]{
\includegraphics[height=8cm]{./comparison_cnn_size.pdf}
}
\caption{\label{fig:size} Comparison of $F_1$ score for each method on 3 series of training and test sets. (Blue: \texttt{mini}, Red: \texttt{less}, Cyan: \texttt{total})}
\end{figure}
\subsubsection{Incremental Learning}
-Incremental learning is a another track of supervised learning, which is capable to take new classes in account when they appear in the training data flow. This online procedure means that earlier learned knowledge is conserved, reused and enriched, which is different from the offline retraining by completely forgetting the ancient knowledge. Nowadays, there exists several deep incremental learning models, \emph{e.g.} Gepperth's GeppNet\cite{Gepperth16}, Rebuffi \emph{et al.}'s iCaRL\cite{RebuffiKL16}, Kemker and Kanan's FearNet\cite{Kemker17}, \emph{etc.}
+Incremental learning is another trend in supervised learning, which is capable of taking new classes in account when they appear in the training data flow. This online procedure means that earlier learned knowledge is conserved, reused and enriched, which is different from the offline retraining by completely forgetting the ancient knowledge. Nowadays, there exists several deep incremental learning models, \emph{e.g.} Gepperth's GeppNet\cite{Gepperth16}, Rebuffi \emph{et al.}'s iCaRL\cite{RebuffiKL16}, Kemker and Kanan's FearNet\cite{Kemker17}, \emph{etc.}
-Although the online version learning is favourable for use cases of Software Heritage, the performance shown in \cite{Kemker17} points out that it is inevitable that the overall accuracy of these incremental learning method degrades after adding new classes. In addition, the online learning is shown in \cite{Kemker17} always underperforming to offline version.
+Although the online version learning is favourable for the use cases of Software Heritage, the performance shown in \cite{Kemker17} points out that it is inevitable that the overall accuracy of these incremental learning method degrades after adding new classes. In addition, the online learning is shown in \cite{Kemker17} to always underperform with reference to offline version.
\section{Conclusion}
In the frame of TRE, we investigated existing NPL methods of text categorisation for applying to source code in Software Heritage. A dataset covering 374 language classes was originally created for tested machine learning methods. We compared several mature NLP methods for a large scale and proposed the most performing one, byte-level ConvNet method, in the possible large-scale deployment in archive. Although the performance is not convincing for official deployment, we traced a potential roadmap for future extension of models.
\clearpage
\begin{appendices}
\section{Language List}
-\begin{table*}[h!]
+\begin{table}[h!]
\centering
\tiny
\begin{tabularx}{\textwidth}{|X|X|X|X|X|X|}
\hline
1C Enterprise & ABAP & ActionScript & Ada & Adobe Font Metrics & Agda\\ \hline
AGS Script & Alloy & AMPL & AngelScript & Ant Build System & ANTLR\\ \hline
ApacheConf & Apex & API Blueprint & APL & AppleScript & Arc\\ \hline
AsciiDoc & ASP & AspectJ & Assembly & ATS & Augeas\\ \hline
AutoHotkey & AutoIt & Awk & Ballerina & Batchfile & BitBake\\ \hline
BlitzBasic & BlitzMax & Bluespec & Boo & Brainfuck & Brightscript\\ \hline
Bro & C & C\# & C++ & Cap'n Proto & CartoCSS\\ \hline
Ceylon & Chapel & Charity & ChucK & Cirru & Clarion\\ \hline
Clean & Click & CLIPS & Clojure & CMake & COBOL\\ \hline
CoffeeScript & ColdFusion & COLLADA & Common Lisp & Common Workflow Language & Component Pascal\\ \hline
CoNLL-U & Cool & Coq & Crystal & Csound & Csound Document\\ \hline
Csound Score & CSS & CSV & Cuda & CWeb & Cycript\\ \hline
D & Dart & DataWeave & desktop & Diff & DIGITAL Command Language\\ \hline
DM & Dockerfile & Dogescript & DTrace & Dylan & E\\ \hline
Eagle & eC & ECL & edn & Eiffel & Elixir\\ \hline
Elm & Emacs Lisp & EmberScript & EQ & Erlang & F\#\\ \hline
Factor & Fancy & Fantom & Filebench WML & FLUX & Forth\\ \hline
Fortran & FreeMarker & Frege & G-code & Game Maker Language & GAMS\\ \hline
GAP & GDB & GDScript & Genie & Genshi & Gerber Image\\ \hline
Gettext Catalog & Gherkin & GLSL & Glyph & Gnuplot & Go\\ \hline
Golo & Gosu & Grace & Gradle & Grammatical Framework & Graph Modeling Language\\ \hline
GraphQL & Graphviz (DOT) & Groovy & Hack & Harbour & Haskell\\ \hline
Haxe & HCL & HLSL & HTML & HXML & Hy\\ \hline
HyPhy & IDL & Idris & IGOR Pro & Inform 7 & INI\\ \hline
Inno Setup & Io & Ioke & Isabelle & J & Jasmin\\ \hline
Java & JavaScript & Jolie & JSON & JSON5 & JSONiq\\ \hline
Julia & Jupyter Notebook & KiCad Layout & KiCad Legacy Layout & KiCad Schematic & Kit\\ \hline
Kotlin & KRL & LabVIEW & Lasso & Lean & Lex\\ \hline
LFE & LilyPond & Limbo & Linker Script & Linux Kernel Module & Liquid\\ \hline
LiveScript & LLVM & Logos & Logtalk & LOLCODE & LookML\\ \hline
LoomScript & LSL & Lua & M & M4 & Makefile\\ \hline
Mako & Markdown & Mask & Mathematica & Matlab & Maven POM\\ \hline
Max & MAXScript & MediaWiki & Mercury & Meson & Metal\\ \hline
Mirah & Modelica & Modula-2 & Module Management System & Monkey & Moocode\\ \hline
MoonScript & MQL4 & MQL5 & MTML & mupad & NCL\\ \hline
Nemerle & nesC & NetLinx & NetLogo & NewLisp & Nextflow\\ \hline
Nginx & Nim & Nit & Nix & NSIS & Nu\\ \hline
Objective-C & Objective-C++ & Objective-J & OCaml & ooc & Opa\\ \hline
OpenEdge ABL & OpenSCAD & OpenType Feature File & Org & Ox & Oz\\ \hline
P4 & Pan & Papyrus & Parrot & Pascal & PAWN\\ \hline
Pep8 & Perl & Perl 6 & PHP & Pickle & PicoLisp\\ \hline
PigLatin & Pike & PLpgSQL & PLSQL & Pod & PogoScript\\ \hline
Pony & PostScript & POV-Ray SDL & PowerBuilder & PowerShell & Processing\\ \hline
Prolog & Propeller Spin & Protocol Buffer & Public Key & Puppet & Pure Data\\ \hline
PureBasic & PureScript & Python & q & QMake & QML\\ \hline
R & Racket & Ragel & RAML & Rascal & Raw token data\\ \hline
RDoc & REALbasic & Rebol & Red & Redcode & Ren'Py\\ \hline
RenderScript & reStructuredText & REXX & Ring & RMarkdown & RobotFramework\\ \hline
Roff & Rouge & RPC & RPM Spec & Ruby & Rust\\ \hline
SaltStack & SAS & Scala & Scheme & Scilab & sed\\ \hline
Self & ShaderLab & Shell & Shen & Slash & Smali\\ \hline
Smalltalk & Smarty & SMT & Solidity & SourcePawn & SPARQL\\ \hline
SQF & SQL & SQLPL & Squirrel & SRecode Template & Stan\\ \hline
Standard ML & Stata & SubRip Text & SuperCollider & SVG & Swift\\ \hline
SystemVerilog & Tcl & Tea & Terra & TeX & Text\\ \hline
Textile & Thrift & TI Program & TLA & TOML & Turing\\ \hline
Turtle & TXL & TypeScript & Unity3D Asset & Uno & UnrealScript\\ \hline
UrWeb & Vala & VCL & Verilog & VHDL & Vim script\\ \hline
Visual Basic & Volt & Vue & Wavefront Material & Wavefront Object & wdl\\ \hline
Web Ontology Language & WebAssembly & WebIDL & wisp & X10 & xBase\\ \hline
XC & XML & Xojo & XPages & XProc & XQuery\\ \hline
XS & XSLT & Xtend & Yacc & YAML & YANG\\ \hline
Zephir & Zimpl \\ \cline{1-2}
\end{tabularx}
\caption{\label{tab:lan} Language List of the dataset, 374 languages engaged.}
-\end{table*}
+\end{table}
\section{File Distribution in Dataset of Each Language}
\begin{figure}[h]
\centering
\includegraphics[width=\textwidth]{circle}
\caption{\label{fig:distribution}File Distribution in Dataset of Each Language}
\end{figure}
\section{Hyperparameters of ConvNets}
\begin{table}[h!]
\centering
\begin{tabular}{|c|c|}
\hline
Hyperparameter & Value \\
\hline
input size & 400 \\
vocabulary size & 15000 \\
character embedding size & 128 \\
filter sizes & [3, 4, 5] \\
nb. of filter matrices & 100 \\
dropout rate & 0.5 \\
activation function & ReLU \\
nb. of neurons in fully connected level & 1024 \\
nb. of classes & 374 \\
\hline
\end{tabular}
-\caption{\label{tab:hyp-word} Details of hyperparameter configuration of word-level ConvNet architecture, referred from \cite{Kim14}.}
+\caption{\label{tab:hyp-word} Details of hyperparameter configuration of word-level ConvNet architecture for \texttt{total} training set and test set, referred from \cite{Kim14}.}
\end{table}
\begin{table}[h!]
\centering
\begin{tabular}{|c|c|}
\hline
Hyperparameter & Value \\
\hline
input size & 4,096 \\
vocabulary size & 256 \\
-character embedding size & 32 \\
+character embedding size & 64 \\
filter sizes & [3, 5, 7, 9, 10] \\
nb. of filter matrices & 256 \\
activation function & ReLU \\
nb. of neurons in fully connected level & 1,024 \\
nb. of classes & 374 \\
\hline
\end{tabular}
-\caption{\label{tab:hyp-byte} Details of hyperparameter configuration of byte-level ConvNet architecture, referred from Chaitanya Joshi's adaptation.}
+\caption{\label{tab:hyp-byte} Details of hyperparameter configuration of byte-level ConvNet architecture for \texttt{total} training set and test set, referred from Chaitanya Joshi's adaptation.}
\end{table}
\end{appendices}
\bibliography{bib-rapport}
\bibliographystyle{unsrt}
%Rapport
%
%Il doit faire de 15 à 30 pages et, dans la mesure du possible, doit être en grande part lisible par des non-spécialistes. Son plan peut être par exemple :
%présentation du domaine de recherche (le jury n'est pas constitué seulement de spécialistes du domaine, tenez-en compte !) ;
%énoncé et motivation du sujet ;
%résultats existants s'y rapportant (état de l'art, commentaire d'article, ...) ;
%vos résultats personnels (clairement identifiés comme tels).
%Le rapport devra être assorti d'un résumé d'une page compréhensible par quiconque.
\end{document}
\ No newline at end of file
diff --git a/scripts/comparison_all_lang.pdf b/scripts/comparison_all_lang.pdf
deleted file mode 100644
index b99516e..0000000
Binary files a/scripts/comparison_all_lang.pdf and /dev/null differ
diff --git a/scripts/comparison_less.pdf b/scripts/comparison_less.pdf
deleted file mode 100644
index e46bacf..0000000
Binary files a/scripts/comparison_less.pdf and /dev/null differ
diff --git a/scripts/draw_accuracy.py b/scripts/draw_accuracy.py
index f7a4a18..072f11c 100644
--- a/scripts/draw_accuracy.py
+++ b/scripts/draw_accuracy.py
@@ -1,202 +1,211 @@
#!/bin/bash/python3
import sys, os
from pickle import load
from collections import namedtuple, Counter
try:
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.ticker import MaxNLocator
except ImportError:
raise ImportError('Please run `pip3 install matplotlib\' in command line.')
-def heatmap(path):
+def heatmap(path, name):
with open(path, 'rb') as f:
data = load(f)
mat = process(data)
labels = sorted(data)
fig, ax = plt.subplots()
- fig.set_size_inches(100,100)
+ fig.set_size_inches(0.25 * len(labels), 0.25 * len(labels))
heatmap = ax.matshow(mat, cmap='Blues')
fig = plt.gcf()
ax.set_frame_on(False)
ax.set_yticks(np.arange(len(labels)), minor=False)
ax.set_xticks(np.arange(len(labels)), minor=False)
ax.set_xlabel('Classification of test files')
ax.set_ylabel('Ground truth class of test files')
ax.set_xticklabels(labels, minor=False)
ax.set_yticklabels(labels, minor=False)
ax.xaxis.tick_top()
ax.xaxis.set_label_position('top')
plt.xticks(rotation=90)
ax.grid(False)
'''
for i in np.arange(len(mat)):
for j in np.arange(len(mat[i])):
ax.text(i, j, "%.1f" % (mat[i][j] * 100), color='white')
'''
ax = plt.gca()
for t in ax.xaxis.get_major_ticks():
t.tick1On = False
t.tick2On = False
for t in ax.yaxis.get_major_ticks():
t.tick1On = False
t.tick2On = False
- fig.savefig("results.pdf", bbox_inches='tight')
+ fig.savefig("{}.pdf".format(name), bbox_inches='tight')
def process(data):
'''
'''
ldata = sorted(data)
length = len(ldata)
out = [[0 for x in range(length)] for y in range(length)]
for lang in ldata:
index_lan = ldata.index(lang)
ok = data[lang][0]
if data[lang][1] > 1000 :
test_size = 1000
else:
test_size = data[lang][1]
result = [x[1] for x in data[lang][3]]
counter = dict(Counter(result))
for res_lan in counter.keys():
index_res = ldata.index(res_lan)
out[index_lan][index_res] = counter.get(res_lan, 0) / test_size
return out
def get_recall(data):
ldata = sorted(data)
out = {}
true_pos = 0
false_neg = 0
for lang in ldata:
ok = data[lang][0]
if data[lang][1] > 1000:
test_size = 1000
else:
test_size = data[lang][1]
result = [x[1] for x in data[lang][3]]
counter = dict(Counter(result))
out[lang] = counter.get(lang, 0) / test_size
true_pos += counter.get(lang,0)
false_neg += test_size - counter.get(lang,0)
print(true_pos)
print(false_neg)
print(true_pos / (true_pos + false_neg))
return out
def get_precision(data):
ldata = sorted(data)
out = {}
true_pos = 0
false_pos = 0
a = []
for lang in ldata:
a += [x[1] for x in data[lang][3]]
counter_all = dict(Counter(a))
for lang in ldata:
ok = data[lang][0]
if data[lang][1] > 1000:
test_size = 1000
else:
test_size = data[lang][1]
result = [x[1] for x in data[lang][3]]
counter = dict(Counter(result))
try:
out[lang] = counter.get(lang, 0) / counter_all.get(lang, 0)
except ZeroDivisionError:
out[lang] = 0
true_pos += counter.get(lang,0)
false_pos += counter_all.get(lang,0) - counter.get(lang,0)
return out
def get_f1(recalls, precisions):
f1 = {}
for k in list(recalls.keys()):
recall = recalls[k]
precision = precisions[k]
f1[k] = harmonic_mean([recall, precision])
return f1
def harmonic_mean(l):
l_pos = [x for x in l if x > 0]
H_T = len(l)
H_0 = H_T - len(l_pos)
if H_T == H_0:
return 0
else:
return ((H_T - H_0) / sum([1 / x for x in l_pos])) * ((H_T - H_0) / H_T)
def compare(results, suffix):
datas = []
for result in results:
with open(result, 'rb') as f:
datas.append(load(f))
dicts = []
for data in datas:
recalls = get_recall(data)
precisions = get_precision(data)
dicts.append(get_f1(recalls, precisions))
-
-
-
- all_lang = sorted(list(set().union(dicts[0].keys(),dicts[1].keys())))[::-1]
+
+ if len(results) == 1:
+ import operator
+ all_lang = [ x[0] for x in sorted(dicts[0].items(), key=operator.itemgetter(1))][:25]
+ else:
+ s = set(dicts[0].keys())
+ for d in dicts:
+ s &= set(d.keys())
+ all_lang = sorted(list(s))[::-1]
+ # all_lang = sorted(list(set().union(dicts[0].keys(),dicts[1].keys())))[::-1]
+
n = len(all_lang)
accs = []
for d in dicts:
accs.append([d.get(lang, 0) for lang in all_lang])
fig, ax = plt.subplots()
- fig.set_size_inches(10, 75 * len(results))
+ fig.set_size_inches(15, 0.2 * len(results) * n)
ind = np.arange(n)
width = 0.75 / len(results)
opacity = 0.4
rectss = []
colors = ['b', 'r', 'c', 'm', 'y', 'g']
for idx, result in enumerate(results):
rectss.append(ax.barh(ind - (idx - len(results) / 2) * width, accs[idx], width, alpha=opacity, color=colors[idx % len(colors)], label=os.path.basename(result)))
- ax.set_xlabel('Accuracy / %')
+ ax.set_xlabel('F1 score / %')
ax.set_yticks(ind + width / 2)
ax.set_yticklabels(all_lang)
+ ax.set_xlim(xmin=0, xmax=1)
vals = ax.get_xticks()
ax.set_xticklabels(['{:3.0f}%'.format(x * 100) for x in vals])
ax.xaxis.tick_top()
+ #if len(rectss) > 1:
ax.legend()
def autolabel(rects):
for rect in rects:
width = rect.get_width()
ax.text(width + 0.01, rect.get_y() + rect.get_height() / 2., '{0:.1f}%'.format(width * 100), ha='left', va='center')
for rects in rectss:
autolabel(rects)
plt.ylim([-1,n+1])
fig.tight_layout()
fig.savefig("comparison_{}.pdf".format(suffix), bbox_inches='tight')
if __name__ == '__main__':
- if len(sys.argv) == 2:
- heatmap(sys.argv[1])
- elif len(sys.argv) > 2:
- compare(sys.argv[1:-1], sys.argv[-1])
+ if len(sys.argv) == 4 and sys.argv[1] == '--cm':
+ heatmap(sys.argv[2], sys.argv[-1])
+ elif len(sys.argv) >= 4 and sys.argv[1] == '--f1':
+ compare(sys.argv[2:-1], sys.argv[-1])
else:
print('Please check arguments.')
diff --git a/scripts/results_ngrams_frequency_distance.pdf b/scripts/results_ngrams_frequency_distance.pdf
deleted file mode 100644
index 8d0908f..0000000
Binary files a/scripts/results_ngrams_frequency_distance.pdf and /dev/null differ
diff --git a/scripts/results_ngrams_prob.pdf b/scripts/results_ngrams_prob.pdf
deleted file mode 100644
index b56ce47..0000000
Binary files a/scripts/results_ngrams_prob.pdf and /dev/null differ