Concept Graph Learning from Educational Data

ABSTRACT

This paper addresses an open challenge in educational data mining, i.e., the problem of using observed prerequisite relations among courses to learn a directed universal concept graph, and using the induced graph to predict unobserved prerequisite relations among a broader range of courses. This is particularly useful to induce prerequisite relations among courses from different providers (universities, MOOCs, etc.). We propose a new framework for inference within and across two graphs---at the course level and at the induced concept level---which we call Concept Graph Learning (CGL). In the training phase, our system projects the course-level links onto the concept space to induce directed concept links; in the testing phase, the concept links are used to predict (unobserved) prerequisite links for test-set courses within the same institution or across institutions. The dual mappings enable our system to perform an interlingua-style transfer learning, e.g. treating the concept graph as the interlingua, and inducing prerequisite links in a transferable manner across different universities. Experiments on our newly collected data sets of courses from MIT, Caltech, Princeton and CMU show promising results, including the viability of CGL for transfer learning.

References

1. R. Al-Rfou, B. Perozzi, and S. Skiena. Polyglot: Distributed word representations for multilingual nlp. arXiv preprint arXiv:1307.1662, 2013.
2. A. Ben-Israel and T. N. Greville. Generalized inverses, volume 13. Springer, 2003.
3. S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
4. E. J. Candies and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717--772, 2009.
5. Y. Chen, B. Perozzi, R. Al-Rfou, and S. Skiena. The expressive power of word embeddings. arXiv preprint arXiv:1301.3226, 2013.
6. R. Collobert, J. Weston, L. Bottou, M. Karlen, K. Kavukcuoglu, and P. Kuksa. Natural language processing (almost) from scratch. The Journal of Machine Learning Research, 12:2493--2537, 2011.
7. C. Do and A. Y. Ng. Transfer learning for text classification. In NIPS, 2005.
8. D. W. Fausett and C. T. Fulton. Large least squares problems involving kronecker products. SIAM Journal on Matrix Analysis and Applications, 15(1):219--227, 1994.
9. M. Fazel. Matrix rank minimization with applications. PhD thesis, PhD thesis, Stanford University, 2002.
10. S. Gopal and Y. Yang. Recursive regularization for large-scale classification with hierarchical and graphical dependencies. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 257--265. ACM, 2013.
11. P. O. Hoyer. Non-negative matrix factorization with sparseness constraints. The Journal of Machine Learning Research, 5:1457--1469, 2004.
12. T. Joachims, H. Li, T.-Y. Liu, and C. Zhai. Learning to rank for information retrieval (lr4ir 2007). In SIGIR Forum, volume 41, pages 58--62, 2007.
13. C. R. Johnson. Matrix completion problems: a survey. In Proceedings of Symposia in Applied Mathematics, volume 40, pages 171--198, 1990.
14. H. Kim and H. Park. Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method. SIAM Journal on Matrix Analysis and Applications, 30(2):713--730, 2008.
15. M. Kshirsagar, J. Carbonell, and J. Klein-Seetharaman. Transfer learning based methods towards the discovery of host-pathogen protein-protein interactions. In Proc of ISMB, volume 40, pages 171--198, 1990.
16. J. Kunegis and A. Lommatzsch. Learning spectral graph transformations for link prediction. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 561--568. ACM, 2009.
17. Q. V. Le and T. Mikolov. Distributed representations of sentences and documents. arXiv preprint arXiv:1405.4053, 2014.
18. D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788--791, 1999.
19. D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019--1031, 2007.
20. R. N. Lichtenwalter, J. T. Lussier, and N. V. Chawla. New perspectives and methods in link prediction. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 243--252. ACM, 2010.
21. T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781, 2013.
22. Y. Nesterov. A method of solving a convex programming problem with convergence rate o (1/k2). In Soviet Mathematics Doklady, volume 27, pages 372--376, 1983.
23. Y. Nesterov. On an approach to the construction of optimal methods of minimization of smooth convex functions. Ekonomika i Mateaticheskie Metody, 24:509--517, 1988.
24. X. Su and T. M. Khoshgoftaar. A survey of collaborative filtering techniques. Advances in artificial intelligence, 2009:4, 2009.
25. L. Yang, S. Hanneke, and J. Carbonell. A theory of transfer learning with applications to active learning. Machine learning, 90(2):161--189, 2013.
26. J. Zhang, Z. Ghahramani, and Y. Yang. Flexible latent variable models for multi-task learning. Machine Learning, 73(3):221--242, 2008.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Supervised learning

        • Supervised learning by classification

    • Machine learning approaches

      • Classification and regression trees

      • Logical and relational learning

        • Inductive logic learning

      • Markov decision processes

• Theory of computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes