Elamur Research⌕
☰
home / papers / 2018 / The Adverse Effects of Code Duplication in Machine Learning Models of Code

The Adverse Effects of Code Duplication in Machine Learning Models of Code

Paper · 2018 · Miltiadis Allamanis

Summary

The paper studies how code duplication in large corpora (primarily those collected from GitHub) distorts the training and evaluation of machine learning models for code in the "big code" field. If identical or near-identical files end up in both the training and the test sets, the i.i.d. assumption is violated. The model is then rewarded for memorization rather than for its ability to generalize. The author formally decomposes a metric estimate into an unbiased component and a "duplication bias", whose influence grows with the proportion of duplicated samples. He then replicates the analysis of Lopes et al. on ten corpora from "big code" research and compares model performance on deduplicated and non-deduplicated data. It turned out that published metrics are sometimes inflated by as much as 100%: a real user sees performance up to roughly 50% lower. Together with the paper, an open near-duplicate detector and a duplication index for commonly used datasets are released. The paper warns anyone who builds corpora from open sources that, without deduplication, model comparisons are unreliable.

Key points

  • The author distinguishes three types of duplicates: in-train, in-test and cross-set. Cross-set duplicates are the most harmful, because they create a false impression that the model generalizes.
  • A duplication factor d is introduced, i.e. the proportion of duplicated samples. The measured metric equals (1−d)·unbiased estimate + d·β, where β is the duplication bias.
  • The near-duplicate-code-detector tool from Microsoft supports C#, Java, Python and JavaScript. It is a simplified reimplementation of SourcererCC for finding file-level duplicates: it takes identifier and literal tokens and builds "fingerprints" from them. An approximate version is available in the dpu-utils package.
  • Practical recommendations:
    • Removing only exact copies and forks is not enough. Splitting data by project helps but does not fully eliminate the problem.
    • Models with a high capacity for memorization are the most vulnerable. Simple memorization methods such as k nearest neighbors should be added to the baselines.
    • Instead of removing duplicates, each group of duplicates can be weighted as a single sample.
  • The work rests on two assumptions: duplication is considered only between whole files, and the target data distribution contains no duplicates. For some tasks, notably code deobfuscation, the second assumption does not hold.

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

 Institutions

🏢MicrosoftRedmond · United States378 works · 161,630 citations🏢Microsoft Research (United Kingdom)Cambridge · United Kingdom11 works · 3,215 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksInformation Systems · 1,730 worksSoftware · 119 works

Cite

Cite as Miltiadis Allamanis. 2018. The Adverse Effects of Code Duplication in Machine Learning Models of Code. arXiv:1812.06469.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1812.06469 · arXiv 1812.06469

@misc{allamanis2018adverse,
  title = {{The Adverse Effects of Code Duplication in Machine Learning Models of Code}},
  author = {Miltiadis Allamanis},
  year = {2018},
  doi = {10.48550/arxiv.1812.06469},
  eprint = {1812.06469},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1812.06469}
}

References

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

  1. Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton. 2018. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR) 51, 4 (2018), 81.
  2. Miltiadis Allamanis, Marc Brockschmidt, and Mahmoud Khademi. 2018. Learning to Represent Programs with Graphs. In Proceedings of the International Conference on Learning Representations (ICLR).
  3. Miltiadis Allamanis, Hao Peng, and Charles Sutton. 2016. A convolutional attention network for extreme summarization of source code. In Proceedings of the International Conference on Machine Learning (ICML). 2091–2100.
  4. Miltiadis Allamanis and Charles Sutton. 2013. Mining source code repositories at massive scale using language modeling. In Proceedings of the Working Conference on Mining Software Repositories (MSR). IEEE Press, 207–216. find
  5. Uri Alon, Omer Levy, and Eran Yahav. 2010. code2seq: Generating Sequences from Structured Representations of Code. In Proceedings of the International Conference on Learning Representations (ICLR). find
  6. Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. 2019. code2vec: Learning distributed representations of code. Proceedings of the ACM on Programming Languages 3, POPL (2019), 40. find
  7. Antonio Valerio Miceli Barone and Rico Sennrich. 2017. A Parallel Corpus of Python Functions and Documentation Strings for Automated Code Documentation and Code Generation. In Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 2: Short Papers), Vol. 2. 31… find
  8. Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Jauvin. 2003. A neural probabilistic language model. Journal of Machine Learning Research (JMLR) 3, Feb (2003), 1137–1155.
  9. Pavol Bielik, Veselin Raychev, and Martin Vechev. 2016. PHOG: Probabilistic Model for Code. In Proceedings of the International Conference on Machine Learning (ICML). 2933–2942. find
  10. Joshua Charles Campbell, Abram Hindle, and José Nelson Amaral. 2014. Syntax errors just aren’t natural: improving error reporting with language models. In Proceedings of the Working Conference on Mining Software Repositories (MSR). ACM, 252–261. find
  11. Mohammad Gharehyazie, Baishakhi Ray, Mehdi Keshani, Masoumeh Soleimani Zavosht, Abbas Heydarnoori, and Vladimir Filkov. 2018. Cross-project code clones in GitHub. Empirical Software Engineering (2018), 1–36. find
  12. Tatsunori B Hashimoto, Kelvin Guu, Yonatan Oren, and Percy Liang. 2018. A Retrieve-and-Edit Framework for Predicting Structured Outputs. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS). find
  13. Vincent J Hellendoorn, Christian Bird, Earl T Barr, and Miltiadis Allamanis. 2018. Deep learning type inference. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ACM, 152–162. find
  14. Vincent J Hellendoorn and Premkumar Devanbu. 2017. Are deep neural networks the best choice for modeling source code?. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering. ACM, 763–773. find
  15. Abram Hindle, Earl T Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. 2012. On the naturalness of software. In Software Engineering (ICSE), 2012 34th International Conference on. IEEE, 837–847. find
  16. Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer. 2016. Summarizing source code using a neural attention model. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Vol. 1. 2073–2083. find
  17. Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer. 2018. Mapping Language to Code in Programmatic Context. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. 1643–1652.
  18. Cory J Kapser and Michael W Godfrey. 2008. “Cloning considered harmful” considered harmful: patterns of cloning in software. Empirical Software Engineering (ESEM) 13, 6 (2008), 645. find
  19. Cristina V Lopes, Petr Maj, Pedro Martins, Vaibhav Saini, Di Yang, Jakub Zitny, Hitesh Sajnani, and Jan Vitek. 2017. DéjàVu: a map of code duplicates on GitHub. Proceedings of the ACM on Programming Languages 1, OOPSLA (2017), 84. find
  20. Chris Maddison and Daniel Tarlow. 2014. Structured generative models of natural source code. In Proceedings of the International Conference on Machine Learning (ICML). 649–657. find
  21. Kevin P Murphy. 2012. Machine Learning: A Probabilistic Perspective. MIT Press. find
  22. Veselin Raychev, Pavol Bielik, Martin Vechev, and Andreas Krause. 2016. Learning programs from noisy data. In Proceedings of the Symposium on Principles of Programming Languages (POPL), Vol. 51. ACM, 761–774. find
  23. Veselin Raychev, Martin Vechev, and Andreas Krause. 2015. Predicting program properties from Big Code. In Proceedings of the Symposium on Principles of Programming Languages (POPL), Vol. 50. ACM, 111–124. find
  24. Veselin Raychev, Martin Vechev, and Eran Yahav. 2014. Code completion with statistical language models. In Proceedings of the Symposium on Programming Language Design and Implementation (PLDI), Vol. 49. ACM, 419–428. find
  25. Chanchal Kumar Roy and James R Cordy. 2007. A survey on software clone detection research. Queen’s School of Computing TR 541, 115 (2007), 64–68. find
  26. Hitesh Sajnani, Vaibhav Saini, Jeffrey Svajlenko, Chanchal K Roy, and Cristina V Lopes. 2016. SourcererCC: scaling code clone detection to big-code. In Software Engineering (ICSE), 2016 IEEE/ACM 38th International Conference on. IEEE, 1157–1168. find
  27. Ewan Tempero, Craig Anslow, Jens Dietrich, Ted Han, Jing Li, Markus Lumpe, Hayden Melton, and James Noble. 2010. The Qualitas Corpus: A curated collection of Java code for empirical studies. In Software Engineering Conference (APSEC), 2010 17th Asia Pacific. IEEE, 336–345. find
  28. Tijmen Tieleman and Geoffrey Hinton. 2012. Lecture 6.5-RMSProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning 4, 2 (2012), 26–31. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/allamanis-2018-adverse-effects-code-duplication-machine/