나를 위한 알고리즘 문제와 라이벌 추천, RECJOON
Baekjoon Online Judge 문제 추천과 solved.ac 라이벌 추천 서비스
딥 러닝과 머신 러닝을 사용하여 BOJ(Baekjoon Online Judge)와 solved.ac 유저의 개인별 문제 풀이 이력을 바탕으로 본인의 수준에 맞는 문제와 라이벌을 추천하는 AI 모델 기반 서비스입니다.
※ 본 웹 서비스는 2022년 9월까지 운영될 계획이며, 피드백을 바탕으로 운영 기간동안 지속하여 개선이 이루어질 예정입니다.
Background
프로젝트 동기
BOJ는 국내 대표 프로그래밍 문제 풀이 사이트이며, 약 36만 명의 사용자와 2만여 개의 문제를 보유하고 있습니다.1 특히 여러 IT 기업에서 진행하는 코딩 테스트를 공부하고자 많은 취업준비생과 학생들이 이용하는 사이트이기도 합니다. 최근에는 solved.ac와 연계되어 사용자들이 문제별로 직접 세분화된 태그와 난이도를 매길 수 있고, 본인이 푼 문제 이력을 바탕으로 점수를 산출하여 자신의 실력이 어느 정도인지를 가늠할 수 있습니다.
프로그래밍 실력을 향상시키기 위해서는 본인의 실력에 맞는 적절한 알고리즘 유형과 난도의 문제를 선택해 푸는 것이 중요하지만, 많은 문제 수로 인해 사용자가 자신의 실력에 맞는 문제를 고르는 데 어려움을 겪는 경우가 적지 않습니다.2 또한 solved.ac에서는 여러 사용자 중에서 자신이 원하는 사람을 라이벌로 등록할 수 있는 기능을 제공하지만, 정작 라이벌 기능을 사용하는 유저 비율은 13%에 불과합니다.3
기대 효과
RECJOON 웹 서비스를 통해 개인의 실력에 맞는 알고리즘 문제를 추천하여 사용자의 문제 탐색 시간을 줄이고 학습의 효율성을 높여드리고자 합니다. 또한 개인의 수준과 풀이 이력이 비슷한 라이벌을 추천해줌으로써 경쟁 심리를 자극하여 문제 풀이 동기를 부여하고 학습 효율을 증대시킬 수 있는 효과를 기대해봅니다.
Features
사용자 검색
원하는 추천 결과는 핸들 검색으로 간단하게.
별도의 회원가입 없이 바로 검색창에 BOJ 핸들만 입력하세요. 사용자 검색 자동완성으로 본인의 핸들이 검색되는지도 한눈에 파악할 수 있습니다.
알고리즘 문제 추천
내 실력에 맞는 알고리즘 문제는 무엇일까?
유저 개개인의 solved.ac 티어와 문제 풀이 이력을 바탕으로 자신의 실력에 맞는 알고리즘 문제를 추천해드립니다.
라이벌 추천
나와 실력이 비슷한 라이벌은 누구지?
유저의 레벨별 문제 풀이 이력과 티어, 클래스, 레이팅을 종합적으로 고려하여 해당 유저의 실력과 유사한 다른 유저들을 6명4 추천해드립니다.
라이벌 기반 문제 추천
나의 라이벌이 푼 문제는 무엇일까?
유저의 풀이 이력을 바탕으로 라이벌은 풀었지만 유저 자신은 풀지 않은 문제도 같이 추천해드려요.
Data Resource
- 유저, 문제, 유저별 문제 풀이 이력: solved.ac 비공식 API
- 문제가 속한 클래스: solved.ac 클래스 페이지에서 웹 스크레이핑
※ Baekjoon Online Judge에서 데이터를 웹 스크레이핑하지 않습니다.
Data Analysis
※ 데이터 분석 결과에 관한 자세한 내용은 EDA 파일을 참고해주세요.
DL & ML Model
RECJOON에서는 정해진 주기에 따라 batch serving으로 데이터 수집과 함께 모델 학습과 예측을 실행합니다. 모든 추천 서비스는 모델 학습 후 검증 과정에서 사전에 정의된 지표를 측정하고, 주기별로 가장 좋은 결과롤 보인 모델을 예측 모델로 선택합니다.
문제 추천 모델
유저가 푼 문제를 기반으로 Autoencoder 기반5의 딥 러닝 모델을 학습시키고, 검증 결과에 따라 미리 정의된 평가 지표6 값이 가장 결과가 잘 나온 모델을 선택합니다. 이후 선택된 모델을 바탕으로 문제 후보를 선정하고 필터링을 통해 최종 문제 추천 결과가 출력됩니다.
특히 Multi-VAE와 Multi-DAE에서는 문제의 태그에 관한 임베딩을 encoder의 입력으로 같이 넣어서 문제에 관한 side information도 같이 학습할 수 있도록 하여 성능을 향상시키고자 했습니다.7
라이벌 추천 모델
| 모델명 | 참조 |
|---|---|
| Collective MF(Matrix Factorization) | David Cortes. 2020. Cold-start recommendations in Collective Matrix Factorization |
| K-nearest neighbors | Altman, and Naomi S. 1992. An introduction to kernel and nearest-neighbor nonparametric regression |
라이벌 추천에서는 다양한 딥 러닝 또는 머신 러닝 모델8을 학습시키고 사전에 정의한 온•오프라인 지표9 중 가장 결과가 잘 나온 모델을 예측 모델로 선정합니다.
라이벌 기반 문제 추천 모델
| 모델명 | 참조 |
|---|---|
| BPR(Bayesian Personalized Ranking) | Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009. BPR: Bayesian Personalized Ranking from Implicit Feedback |
| ALS(Alternating Least Squares) MF | Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative Filtering for Implicit Feedback Datasets |
| Item-based CF(Collaborative Filtering) | Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001. Item-based Collaborative Filtering Recommendation Algorithms |
라이벌 기반 문제 추천에서도 마찬가지로 여러 모델10을 통해 성능 지표11를 최소화 하는 방향으로 유저의 문제 풀이 패턴을 학습하고, 예측한 결과에서 실제로 자신이 풀었던 문제는 제외하여 필터링한 결과를 출력합니다.
Service
Service Architecture
※ 2022년 6월 15일 전후로 AI Stages Server에서 GCP(Google Cloud Platform) VM Instance로 전환되었습니다.
UML Sequence Diagram
※ 유저로부터 Explicit Feedback을 받는 API가 추가되었습니다. (2022.06.11)
Airflow DAG Workflow
Team Members
|
|
|
|
|
| 김은선 | 박정규 | 이서희 | 이선호 | 진완혁 |
| 라이벌 추천 모델링 라이벌 문제 추천 모델링 태스크 자동화 모델 실행 코드 모듈화 |
데이터 EDA Front-end 개발 GCP로 Airflow 이전 |
라이벌 추천 모델링 라이벌 문제추천 모델링 온•오프라인 지표 개발 라이벌 추천 고도화 |
Back-end 개발 Front-end 디자인 CI & CD 자동화 문제 추천 모델 전처리 |
데이터 수집과 EDA 문제 추천 모델링 티어 필터링 |
Further Information
프로젝트에 관한 전반적인 내용 소개는 발표 영상 또는 자료를 확인해주세요.
주 사용 모델 실험•분석 결과와 프로젝트 진행에 관한 자세한 내용은 발표 자료와 Wrap-up Report를 참고해 주세요.
💻 RECJOON Server Git Repository
GitHub Action 권한 문제로 인해 웹 서버로의 배포는 현재 Repository를 통해 이루어지지 않습니다.
실제 웹 서버로 배포된 코드는 위의 Git Repository를 참고해주세요.
Annotation
1. Baekjoon Online Judge 사이트 유저 수와 공개된 문제 수 (2022.04.21) ↩
2. Baekjoon Online Judge 문제와 라이벌 추천 서비스 예상 선호도 조사. 'BOJ 문제를 선택하는 데 있어서 어느 정도의 어려움을 겪고 있으신가요?'. 약 51.1%의 응답자 보통 이상 응답. (45명 참여, S 대학교 ICPC Team Slack 채널 등)↩
3. EDA 분석 결과, '라이벌과 역라이벌 수 분석' (2022.04.21) ↩
4. 서비스 개시일 기준 (2022.06.11), 추후 변동 가능 ↩
5. RecVAE(Variational AutoEncoder), Multi-VAE, Multi-DAE(Denoising AutoEncoder) (서비스 개시일 기준, 2022.06.11) ↩
6. Recall@30(모델이 해당 유저가 좋아할 것이라고 예측한 상위 30개 문제가 실제로 유저가 좋아하는 문제에 속하는 비율) ↩
7. Yifan Chen, and Maarten de Rijke. 2017. A Collective Variational Autoencoder for Top-N Recommendation with Side Information. ACM ↩
8. Collaborative MF(Matrix Factorization), K-nearest neighbors (서비스 개시일 기준, 2022.06.11) ↩
9. solved.ac 레이팅 산출법에 기반한 아래 세 가지 지표 값의 평균
10. BPR(Bayesian Personalized Ranking), ALS(Alternating Least Squares) Matrix Factorization, item-based CF(Collaborative Filtering) (서비스 개시일 기준, 2022.06.11) ↩
11. 추천된 문제와 타겟 유저가 푼 문제의 난이도 차이를 기반으로 구한 지표
