基于深度强化学习与程序分析的OJ习题推荐模型

doi:10.11896/jsjkx.220600260

Abstract

Abstract: At present,there are a large number of exercises on the existing programming Online Judge systems(OJ),which makes it difficult for students to quickly find suitable exercises according to their own knowledge level and learning demand.Therefore,it is necessary to design a model to recommend suitable exercises to students.However,due to uniqueness of OJ and complexity of programming ability evaluation,existing recommendation model can not complete OJ exercise recommendation task well,the main problems include:OJ exercises' lack of knowledge label and unique proposition style make it difficult for existing models to mine correlation between exercises; actual correctness of the program submitted by student is inconsistent with OJ judgement result,which leads to deviation of students' knowledge state estimated by models; existing models are difficult to provide exercises that increase students' programming ability most significantly.Based on this,this paper proposes an OJ exercise recommendation model based on deep reinforcement learning and program analysis.Firstly,analyzing optimal solution of exercises to mine correlations between exercises.Then,comparing the similarity between programs submitted by students and optimal solution of exercises to check actual correctness of the programs submitted by students,so that knowledge state of students can be estimated more accurately.Finally,using deep reinforcement learning technology,taking knowledge tracking model as student simulator and treating student simulator's performance difference on all the exercises before and after answering exercises provided by exercise re-commendation model as reward,so that exercise recommendation model can learn which exercise is able to improve the students' programming ability to the greatest extent,and recommend such exercises to students.This paper conducts extensive experiments on two datasets CodeForces and Libre of the well-known OJ system,and experimental results show that the proposed model can achieve higher performance than the state-of-the-art recommendation models.

Key words: Recommender system, Deep reinforcement learning, Program analysis, Knowledge tracing, Online judge

CLC Number:

TP301

JIN Tiancheng, DOU Liang, ZHANG Wei, XIAO Chunyun, LIU Feng, ZHOU Aimin. OJ Exercise Recommendation Model Based on Deep Reinforcement Learning and Program Analysis[J].Computer Science, 2023, 50(8): 58-67.

References

[1]GONG J,WANG S,WANG J,et al.Attentional graph convolutional networks for knowledge concept recommendation in moocs in a heterogeneous view[C]//Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval.Xi'an:ACM,2020:79-88.
[2]SHAO E,GUO S,PARDOS Z A.Degree Planning with PLAN-BERT:Multi-Semester Recommendation Using Future Courses of Interest[C]//Proceedings of the AAAI Conference on Artificial Intelligence.Vancouver:AAAI,2021:14920-14929.
[3]HUO Y,WONG D F,NI L M,et al.Knowledge modeling via contextualized representations for LSTM-based personalized exercise recommendation[J].Information Sciences,2020,523:266-278.
[4]ZHAO J,BHATT S,THILLE C,et al.Interpretable persona-lized knowledge tracing and next learning activity recommendation[C]//Proceedings of the Seventh ACM Conference on Learning@ Scale.New York:ACM,2020:325-328.
[5]KANG W,ZHANG L,LI B,et al.Personalized exercise recommendation via implicit skills[C]//Proceedings of the ACM Tu-ring Celebration Conference－China.Chengdu:ACM,2019:1-6.
[6]MA X R,XU Y,ZHU Q X.Personalized Exercises Recommendation Method Based on Deep Knowledge Tracing[J].Journal of Chinese Computer Systems,2020,41(5):990-995.
[7]XIONG H J,SONG Y F,ZHANG P,et al.Personalized Question Recommendation Based on Autoencoder and Two-step Collaborative Filtering[J].Computer Science,2019,46(11A):172-177.
[8]QI B,ZOU H X,WANG Y,et al.Questions RecommendationBased on Collaborative Filtering and Cognitive Diagnosis[J].Computer Science,2019,46(11):235-240.
[9]ZHU T Y,HUANG Z Y,CHEN E H,et al.Cognitive DiagnosisBased Personalized Question Recommendation[J].Chinese Journal of Computers,2017,41(1):176-191.
[10]FAN X.Item response theory and classical test theory:An empirical comparison of their item/person statistics[J].Educational and Psychological Measurement,1998,58(3):357-381.
[11]DE LA TORRE J.DINA model and parameter estimation:A didactic[J].Journal of Educational and Behavioral Statistics,2009,34(1):115-130.
[12]GAO W,LIU Q,HUANG Z,et al.Rcd:Relation map driven cognitive diagnosis for intelligent education systems[C]//Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval.Montreal:ACM,2021:501-510.
[13]CORBETT A T,ANDERSON J R.Knowledge tracing:Mode-ling the acquisition of procedural knowledge[J].User Modeling and User-adapted Interaction,1994,4(4):253-278.
[14]PIECH C,BASSEN J,HUANG J,et al.Deep knowledge tracing[C]//Proceedings of the Advances in Neural Information Processing Systems.Quebec:MIT Press,2015:505-513.
[15]ZHANG J,SHI X,KING I,et al.Dynamic key-value memory networks for knowledge tracing[C]//Proceedings of the 26th International Conference on World Wide Web.Perth:ACM,2017:765-774.
[16]CHOI Y,LEE Y,CHO J,et al.Towards an appropriate query,key,and value computation for knowledge tracing[C]//Procee-dings of the Seventh ACM Conference on Learning@ Scale.New York:ACM,2020:341-344.
[17]Renmin University of China.Libre OJ[EB/OL].(2022-03-25) [2022-05-11].https://loj.ac.
[18]WANG C Q.Luogu OJ[EB/OL].(2022-05-11) [2022-05-11].https://www.luogu.com.cn.
[19]LIU Q,HUANG Z,HUANG Z Y,et al.Finding similar exercises in online education systems[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Disco-very & Data Mining.London:ACM,2018:1821-1830.
[20]TAN D W,ZHANG K F,LIU Y,et al.Program Classification Using Gated Graph Attention Neural Network[J].Computer Engineering and Applications,2020,56(7):176-183.
[21]HUANG Z,LIU Q,ZHAI C,et al.Exploring multi-objectiveexercise recommendations in online education systems[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management.Beijing:ACM,2019:1261-1270.
[22]ZHANG J,HAO B,CHEN B,et al.Hierarchical reinforcement learning for course recommendation in MOOCs[C]//Procee-dings of the AAAI Conference on Artificial Intelligence.Hawaii:AAAI,2019:435-442.
[23]LIN Y,LIN F,ZENG W,et al.Hierarchical reinforcement lear-ning with dynamic recurrent mechanism for course recommendation[J].Knowledge-Based Systems,2022,244:108546.
[24]LIU Q,TONG S,LIU C,et al.Exploiting cognitive structure for adaptive learning[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mi-ning.Alaska:ACM,2019:627-635.
[25]ALLAMANIS M,PENG H,SUTTON C.A convolutionalattention network for extreme summarization of source code[C]//International Conference on Machine Learning.New York:JMLR,2016:2091-2100.
[26]LU Y,LI G,ZHAO Z,et al.Learning to infer API mappings from API documents[C]//International Conference on Know-ledge Science,Engineering and Management.Melbourne:Sprin-ger,2017:237-248.
[27]MOU L,LI G,ZHANG L,et al.Convolutional neural networks over tree structures for programming language processing[C]//Thirtieth AAAI Conference on Artificial Intelligence.Arizona:AAAI,2016:1287-1293.
[28]LI Y,TARLOW D,BROCKSCHMIDT M,et al.Gated graphsequence neural networks[C]//4th International Conference on Learning Representations.Puerto Rico:OpenReview,2016.
[29]Saratov State University.CodeForces[EB/OL].(2022-05-11)[2022-05-11].https://codeforces.com.
[30]Clemson University.United States of America ComputingOlympiad[EB/OL].(2022-05-11) [2022-05-11].http://www.usaco.org.
[31]Peking University.Peking University OJ[EB/OL].(2022-05-11) [2022-05-11].http://poj.org.
[32]Zhejiang University.Zhejiang University OJ[EB/OL].(2022-05-11) [2022-05-11].http://acm.zju.edu.cn/onlinejudge.
[33]Hangzhou Dianzi University.Hangzhou Dianzi University OJ[EB/OL].(2022-05-11) [2022-05-11].http://acm.hdu.edu.cn.
[34]10XRECRUIT.Kattis Problem Archive[EB/OL].(2022-05-11) [2022-05-11].https://open.kattis.com.
[35]ZHENG W,DU Q,FAN Y,et al.A personalized programming exercise recommendation algorithm based on knowledge structure tree[J].Journal of Intelligent & Fuzzy Systems,2022,42(3):2169-2180.
[36]YERA TOLEDO R,CABALLERO MOTA Y,MARTINEZ L.A recommender system for programming online judges using fuzzy information modeling[J].Informatics,2018,5(2):1-17.
[37]YERA R,MARTINEZ L.A recommendation approach for programming online judges supported by data preprocessing techniques[J].Applied Intelligence,2017,47(2):277-290.
[38]TOLEDO R Y,MOTA Y C.An e-learning collaborative filtering approach to suggest problems to solve in programming online judges[J].International Journal of Distance Education Techno-logies(IJDET),2014,12(2):51-65.
[39]MAO H Y.A Study on Knowledge Recommender AlgorithmBased on Time Transition[D].Tianjin:Tianjin University,2017.
[40]NANDPAWAN D.KalkiCode[EB/OL].(2022-05-11) [2022-05-11].https://kalkicode.com/ai/java-to-cplusplus-converter-online.
[41]LUKAS M,TIMOTHY C.Python to C++ 14 transpiler[EB/OL].(2018-06-03) [2022-05-11].https://github.com/luk-asmartinelli/py14.
[42]MNIH V,KAVUKCUOGLU K,SILVER D,et al.Playing atari with deep reinforcement learning[J].arXiv:1312.5602,2013.
[43]HIDASI B,KARATZOGLOU A,BALTRUNAS L,et al.Session-based recommendations with recurrent neural networks[C]//Proceedings of 4th International Conference on Learning Representations.Puerto Rico:OpenReview,2016:1-10.
[44]KANG W C,MCAULEY J.Self-attentive sequential recommendation[C]//2018 IEEE International Conference on Data Mi-ning(ICDM).Singapore:IEEE Computer Society,2018:197-206.
[45]LI J,WANG Y,MCAULEY J.Time interval aware self-attention for sequential recommendation[C]//Proceedings of the 13th International Conference on Web Search and Data Mining.Texas:ACM,2020:322-330.
[46]HE Z,ZHAO H,LIN Z,et al.Locker:Locally Constrained Self-Attentive Sequential Recommendation[C]//Proceedings of the 30th ACM International Conference on Information & Know-ledge Management.Queensland:ACM,2021:3088-3092.
[47]TANG J,CHEN Y,ZHOU M,et al.A Survey of Studies on Deep Learning Applications in POI Recommendation[J].Computer Engineering,2022,48(1):12-23,42.
[48]YANG G,QIAO S,QU L.A survey of learning based database index advisor technology[J].Journal of Chongqing University of Technology(Natural Science),2022,36(6):189-199.

Related Articles 15

[1]	XIONG Liqin, CAO Lei, CHEN Xiliang, LAI Jun. Value Factorization Method Based on State Estimation [J]. Computer Science, 2023, 50(8): 202-208.
[2]	WANG Hanmo, ZHENG Shijie, XU Ruonan, GUO Bin, WU Lei. Self Reconfiguration Algorithm of Modular Robot Based on Swarm Agent Deep Reinforcement Learning [J]. Computer Science, 2023, 50(6): 266-273.
[3]	YANG Bin, LIANG Jing, ZHOU Jiawei, ZHAO Mengci. Study on Interpretable Click-Through Rate Prediction Based on Attention Mechanism [J]. Computer Science, 2023, 50(5): 12-20.
[4]	ZHANG Qiyang, CHEN Xiliang, CAO Lei, LAI Jun, SHENG Lei. Survey on Knowledge Transfer Method in Deep Reinforcement Learning [J]. Computer Science, 2023, 50(5): 201-216.
[5]	YU Ze, NING Nianwen, ZHENG Yanliu, LYU Yining, LIU Fuqiang, ZHOU Yi. Review of Intelligent Traffic Signal Control Strategies Driven by Deep Reinforcement Learning [J]. Computer Science, 2023, 50(4): 159-171.
[6]	DONG Yongfeng, HUANG Gang, XUE Wanruo, LI Linhao. Graph Attention Deep Knowledge Tracing Model Integrated with IRT [J]. Computer Science, 2023, 50(3): 173-180.
[7]	XU Linling, ZHOU Yuan, HUANG Hongyun, LIU Yang. Real-time Trajectory Planning Algorithm Based on Collision Criticality and Deep Reinforcement Learning [J]. Computer Science, 2023, 50(3): 323-332.
[8]	Cui ZHANG, En WANG, Funing YANG, Yong jian YANG , Nan JIANG. UAV Frequency-based Crowdsensing Using Grouping Multi-agentDeep Reinforcement Learning [J]. Computer Science, 2023, 50(2): 57-68.
[9]	LIU Zejing, WU Nan, HUANG Fuqun, SONG You. Hybrid Programming Task Recommendation Model Based on Knowledge Graph and Collaborative Filtering for Online Judge [J]. Computer Science, 2023, 50(2): 106-114.
[10]	WEI Nan, WEI Xianglin, FAN Jianhua, XUE Yu, HU Yongyang. Backdoor Attack Against Deep Reinforcement Learning-based Spectrum Access Model [J]. Computer Science, 2023, 50(1): 351-361.
[11]	HAO Jingyu, WEN Jingxuan, LIU Huafeng, JING Liping, YU Jian. Deep Disentangled Collaborative Filtering with Graph Global Information [J]. Computer Science, 2023, 50(1): 41-51.
[12]	HUANG Yuzhou, WANG Lisong, QIN Xiaolin. Bi-level Path Planning Method for Unmanned Vehicle Based on Deep Reinforcement Learning [J]. Computer Science, 2023, 50(1): 194-204.
[13]	ZHANG Qiyang, CHEN Xiliang, ZHANG Qiao. Sparse Reward Exploration Method Based on Trajectory Perception [J]. Computer Science, 2023, 50(1): 262-269.
[14]	CHENG Zhang-tao, ZHONG Ting, ZHANG Sheng-ming, ZHOU Fan. Survey of Recommender Systems Based on Graph Learning [J]. Computer Science, 2022, 49(9): 1-13.
[15]	WANG Guan-yu, ZHONG Ting, FENG Yu, ZHOU Fan. Collaborative Filtering Recommendation Method Based on Vector Quantization Coding [J]. Computer Science, 2022, 49(9): 48-54.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

OJ Exercise Recommendation Model Based on Deep Reinforcement Learning and Program Analysis

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0