2023년 6월 24일 (토) 00:52 판

프로젝트 개요=

기술개발 과제

국문 : 코테고리 서비스 - 알고리즘 유형분류 퀴즈 및 문제 추천 서비스

영문 : Cotegory Service - Algorithm type classification quiz and problem recommendation sevice

과제 팀명

Vision

지도교수

황*수 교수님

개발기간

2023년 3월 ~ 2023년 6월 (총 4개월)

구성원 소개

서울시립대학교 컴퓨터과학부 20189200** 류*욱(팀장)

서울시립대학교 컴퓨터과학부 20179200** 김*

서울시립대학교 컴퓨터과학부 20184300** 김*철

서울시립대학교 컴퓨터과학부 20189200** 임*욱

서울시립대학교 컴퓨터과학부 20189200** 한*한

서론

개발 과제의 개요

개발 과제 요약

◇ 사용자 수준에 맞춘 알고리즘 문제 유형 분류 퀴즈 제공
◇ 오답률이 높은 문제 유형의 알고리즘 분야 파악 및 문제 추천 기능 제공
◇ 퀴즈 결과를 기반으로 한 프로필 요약 제공
◇ 취업 및 자기계발이 서비스의 주 목적으로 취준생이 주요 타겟층

개발 과제의 배경

◇ IT 분야의 기업에 취업을 희망하는 경우, 다수의 기업이 알고리즘 코딩테스트를 기업의 전형에 포함하고있어, 알고리즘 학습에 대한 수요가 많은 상황이다.
◇ 알고리즘 문제를 읽고 접근방식에 대한 충분한 검토 없이 바로 풀이에 들어가는 사용자가 있다.

개발 과제의 목표 및 내용

◇ 알고리즘 대회 또는 코딩테스트를 준비하는 사용자가 쉽게 자신의 알고리즘 역량을 확인하고, 향상시킬 수 있는 웹 플랫폼을 개발한다.
◇ 퀴즈 결과를 통해 요약 프로필을 제공하고 이를 통해 자신의 알고리즘 풀이 능력을 한 눈에 확인할 수 있게 한다.
◇ 퀴즈 결과를 통해 취약한 알고리즘 유형의 문제를 추천하여 자연스럽게 구현까지 이어지게 한다.
◇ 사용자가 서비스를 활용할 수록 알고리즘 풀이에 흥미를 갖게하여 꾸준하게 Cotegory 서비스를 이용할 수 있도록 한다.

구성원 및 추진체계

◇ Front-end (류병욱)

 UI/UX
 프론트 페이지 HTML 작성
 Back-end와의 통신코드 작성

◇ Back-end (김준)

 mmr시스템 로직 구현
 mmr시스템을 통한 Quiz 추천
 기업문제 추천

◇ Back-end (김형철)

 크롤링 로직 구현
 JWT 로그인 구현
 어드민 페이지 API 개발
 비정상적 문제 검열 로직

◇ Back-end (김준, 김형철 공통)

 서비스 로직 API 개발

◇ AI (한수한)

 모델 학습
 평가 & 비교(EASE, AUTO_ENCODER)

◇ 아마존 배포 (임재욱)

 main 머지 시 자동 배포 (CI/CD)

설계

설계사양

제품의 요구사항

◇ R1: 알고리즘 퀴즈를 풀고 이력을 확인할 수 있다.
◇ R2: 취약한 알고리즘 분야에 대한 추천을 받을 수 있다.
◇ R3: 다양한 알고리즘 문제를 추천받을 수 있다.
◇ R4: 요약 프로필을 제공받을 수 있다.

설계 사양

◇ F1:

기능: 알고리즘 퀴즈를 하나씩 제공하고 정답 여부가 기록되어 마이페이지에서 제공한다.
정량 목표:

- AI: AUTO_ENCODER 모델을 적용하여 추천 문제를 선별하여 Back-end 서버에 제공한다.

- Back-end: 알고리즘 퀴즈를 Front-end 서버에 전달하며, 정답 여부를 db에 저장한다.

- Front-end: Back-end 서버로부터 전달받은 추천 문제와 알고리즘 퀴즈 문제를 화면에 보이고 문제를 풀수 있는 UI를 제공한다.

◇ F2:

기능: 유저로부터 전달받은 정보를 활용하여 AI 모델을 통해 적합한 문제를 추천한다.
정량 목표:

- AI: 유저가 취약한 알고리즘 분야의 문제를 추천받고자 하는 경우, AUTO_ENCODER 모델을 적용하여 추천 문제를 선별하여 Back-end 서버에 제공한다.

- Back-end: 추천 문제를 Front-end 서버에 전달한다.

- Front-end: Back-end 서버로부터 전달받은 추천 문제를 화면에 보이고 문제를 풀 수 있는 링크또한 제공한다.

◇ F3: 랜덤 문제, 유저가 취약한 알고리즘 분야의 문제, 기업 문제를 추천한다.

기능: 유저로부터 전달받은 정보를 활용하여 AI 모델을 통해 적합한 문제를 추천한다.
정량 목표:

- AI: AUTO_ENCODER 모델을 적용하여 추천 문제를 선별하여 Back-end 서버에 제공한다.

- Back-end: 추천 문제를 Front-end 서버에 전달하며, 오늘의 추천 문제와 기업 문제 또한 Front-end 서버에 전달한다.

- Front-end: Back-end 서버로부터 전달받은 추천 문제를 화면에 보이고 문제를 풀수 있는 링크 또한 제공한다.

◇ F4: 문제 히스토리와 요약 프로필을 제공한다.

기능: 퀴즈 결과와 알고리즘 대분류별 MMR을 제공한다.
정량 목표:

- Back-end: 퀴즈 결과와 알고리즘 대분류별 MMR 점수를 Front-end에 전달한다.

- Front-end: Back-end 서버로부터 전달받은 데이터를 화면에 보이고 데이터를 가공하여 100점 만점을 기준으로 점수를 보여주며 능력치를 progress bar 형태로 보여준다.

개념설계안

1. EC2 Instance와 Docker Container: EC2 인스턴스에서 Docker를 실행하고, Docker 컨테이너를 생성하여 애플리케이션을 실행합니다.
2. Dockerfile과 Docker Image: Dockerfile은 Docker 이미지를 작성하는데 사용됩니다. Docker 이미지는 애플리케이션과 애플리케이션 실행에 필요한 모든 종속성을 포함하는 실행 가능한 패키지입니다.

Dockerfile은 총 3개로, 각각 AI, Front-end, Back-end 도메인을 의미합니다.

3. Docker Compose.yml과 Docker Compose: Docker Compose는 여러 개의 Docker 컨테이너를 정의하고 관리하는 데 사용되는 도구입니다. Docker Compose.yml 파일은 Docker Compose가 사용하는 설정 파일입니다.
4. AWS S3와 EC2 Instance: EC2 인스턴스는 AWS S3에 접근하여 데이터를 읽거나 쓸 수 있습니다. 이를 통해 EC2 인스턴스와 S3 버킷 간에 파일 공유 또는 데이터 저장 등의 작업이 가능합니다.
5. AWS RDS와 EC2 Instance: EC2 인스턴스는 AWS RDS(Relational Database Service)에 접근하여 데이터베이스에 연결하고 데이터를 읽거나 쓸 수 있습니다. 이를 통해 애플리케이션과 데이터베이스 간의 상호작용이 가능합니다.
6. 현재 Dockerfile, docker-compose.yaml의 내용이 변경된 것은 쉽게 적용이 가능하지만, 프로젝트의 내용이 바뀐 경우도 고려하여 GitHub Actions를 사용하여 CI/CD를 적용하였습니다.

이론적 계산 및 시뮬레이션

AI 추천 모델

◇ 기본적으로 훈련에 쓰인 데이터외의 데이터를 통해서도 문제를 추천해줄 수 있는 모델을 선정하였다.
◇ auto_encoder 모델이 위의 특성을 가지고 있어 auto_encode 기본 모델(AUTO_ENCODER)과 간단하면서도 성능이 좋은 모델(EASE)을 선정하였다.

1. AUTO_ENCODER

《특징》
입력 데이터(X)를 encoder에 넣어 잠재 벡터로 만든후 이 잠재 벡터를 다시 decoder에 넣어 입력 데이터와 비슷한 출력 데이터로 복원하는 형태를 가진다.
입력 데이터를 원래의 입력데이터의 압축된 지식표현으로 만드는 것이 목적이지만 이는 추천에도 활용할 수 있다.

훈련을 너무 오래 돌리면 auto encoder의 weight의 곱이 단위 행렬과 비슷해질 수 있다.
즉, 대각 값이 가장 높아져 자기 자신이 자기 자신을 추천해버리는 경우가 생긴다. (overfitting)
그러므로 훈련을 적당한 선에서 멈추고 대각 값에 제약을 추가하는 방법을 사용한다.

본 프로젝트에서는 hidden layer를 2개(Encoder, Decoder)만 사용했다.

《학습 방법》
◇ 데이터 (X)

X = 유저(U) * 아이템(I) Matrix
0과 1로 이루어짐

◇ 파라미터

E = 아이템(I) * 잠재벡터차원(Z) Matrix

- 입력 데이터를 잠재 벡터로 encoding하는 작업을 수행

D = 잠재벡터차원(Z) * 아이템(I) Matrix

- 잠재 벡터를 입력 데이터처럼 decoding하는 작업을 수행

◇ 출력 (S)

S = X * E * D
유저(u)에 대한 아이템(j)의 ranking 점수

《목적함수 (손실함수)》
본 프로젝트에서는 손실함수 L을 auto_encoder에 흔히 쓰이는 mse(mean squared error)로 설정했다.

훈련 루프를 돌며 L을 최소화하도록 훈련한다.
단, 위에서 언급한 것처럼 L을 최소화하다보면 train data의 정확도는 높아지고 test data의 정확도는 낮아지는overfitting이 발생하므로 est data의 정확도가 최대일 때의 모델(가중치)를 저장한다.

2. EASE (Embarrassingly Shallow Autoencoders for Sparse Data)

《특징》
2019년에 나온 추천 모델로 hidden layer가 없는 shallow한 모델이다.
다른 딥러닝 모델과 달리 학습 파라미터(매트릭스)가 1개밖에 존재하지 않고 이 학습 파라미터의 대각 성분을 0으로 함으로써 목적함수를 closed form sulution로 만들 수 있어 최적의 해를 구할 수 있다.
《학습 방법》
◇ 데이터 (X)

X = 유저(U) * 아이템(I) Matrix
예시

	문제 1	문제 2	문제 3	문제 4
유저 A	0	1	1	0
유저 B	1	0	1	1
유저 C	0	0	0	1

◇ 파라미터 (B)

I * I Matrix
예시

◇ 출력 (S)

S = X * B
예시

《목적함수 (손실함수)》

◇ X와 XB 의 차이를 가장 작게 하는 B를 구하는 항에 과적합을 예방하기 위한 L2-norm정규화 항을 추가한다.
◇ 위에서 볼 수 있듯이 EASE 모델에서는 하이퍼파라미터(hyperparamter)는 밖에 없다.
◇ B의 값을 구하기 위해 대각 성분을 0으로 한다는 조건을 사용하여 라그랑주 승수법을 이용한다.
◇ 라그랑주 승수법을 통해 생성된 최종 목적함수는 다음과 같다.

◇ L이 최소가 되는 B를 구하는 중간 과정이 논문에 존재하지 않아 간단히 증명하면 다음과 같다.

위 식에서 L2-norm 제곱 항을 다음과 같이 변경할 수 있다.

위 식을 사용한 최종 손실함수 L은 다음과 같다.

L을 미분하여 L의 도함수가 0이 되는 B를 구하는 과정은 다음과 같다.

각 항에 대해 미분을 진행하면 다음과 같은 식이 나온다.

L의 도함수를 0으로 하여 B에 대해 정리하면 논문에서 나온 B의 항등식이 나온다.

다음부터는 논문에 있는 내용이다.먼저 식을 간추리기 위해 다음과 같이 P를 정의한다.

B에 P를 대입하여 정리하면 다음과 같다.

마지막으로 γ̃을 구하고

γ̃을 B식에 대입하면

즉, 이 과정으로 구한 B가 L이 최소가 되는 최적의 해가 된다.B의 요소를 표현해보면

즉, 대각 값은 전부 0이고 그렇지 않으면 P에 영향을 받는다.

P은 위 식에서 볼 수 있듯이 X^TX에 영향을 받는다.

이때, X^TX는 $라고 표현하는데 이는 Gram Matrix라고 한다.

G는 item-item matrix로 co-occurrence matrix(동시 발생 행렬)라고도 불리운다.

G를 본 프로젝트에 적용하자면 어떤 문제를 선택했을 때, 다른 문제도 선택될 빈도를 나타낼 수 있는 지표이다.

즉, 문제와 문제의 유사성을 띄는 matrix로 추천에 용이하게 쓰인다.

데이터셋

◇ 데이터는 백준 유저 랭킹 31~280 페이지에서 10명씩 총 2500명을 sampling하여 얻었다.
◇ 데이터를 얻은 2023/05/03 기준 280페이지는 한 유저가 최소 162문제를 풀었다.
◇ train data와 test data를 7:3으로 나누고 topk를 50까지 하기 위해서 위와 같이 sampling하였다.

162*0.3 ~= 49이므로 대부분의 유저가 test data에 들어갈 수 있다.

◇ train data와 test data를 나누는 방법은 다음과 같다.

ex) 유저 3명, 문제 5개 유저 - 문제 matrix [[1,0,1,1,1], [0,0,1,1,1], [1,1,1,0,0]] shape = (3,5) test_ratio = 0.2 각 유저별로 1인 값을 3개 sampling ((35) 0.2 = 3) split 결과 test data [(0,4), (1,2), (2,0)] train data [[1,0,1,1,0], [0,0,0,1,1], [0,1,1,0,0]] topk=1 train data를 모델에 넣어 train data에서 이미 1인 data를 제외하고 rating을 매긴 후 유저별로 가장 높은 1개의 문제를 고른다. 이때, 이 문제가 test data에 속한다면 true로 판정한다. ex) train data를 모델에 넣은 출력 값 [[0.8, 0.1, 0.9, 0.3, 0.15], [0.1,0.05 , 0.09, 0.6, 0.4], [0.2, 0.3, 0.7, 0.1, 0.12]] train data에서 1인 data 제외후 유저별로 가장 높은 1개의 문제를 고른다. [[0.8, 0.1, 0.9, 0.3, 0.15], [0.1,0.05 , 0.09, 0.6, 0.4], [0.2, 0.3, 0.7, 0.1, 0.12]] (0,4), (1,0), (2,0) // rating 결과 index (0,4), (1,2), (2,0) // test data 정확도는 2/3가 된다

평가지표

◇ precision
◇ recall
◇ ndcg
총 3가지로 평가한다.

topks 높은 점수를 받은 상위 k개를 추천해줄 때 사용되는 k 리스트 ex) topks = [10, 20, 50] precision true인 문제 개수 / k 여기서 true란 추천된 문제가 훈련에 쓰이지 않은 유저가 푼 문제에 해당한 경우 recall true인 문제 개수 / 유저가 푼 모든 문제 개수 ndcg (Normalized Discounted Cumulative Gain) relevance score(rating)의 할인된 합의 정규화 높은 점수일수록 가중치를 훨씬 많이 제공 ex) 문제 총 개수 = 10 어느 유저가 푼 문제 matrix [1, 0, 1, 1, 1, 0, 0, 0, 1, 0] test_ratio = 0.3 test_data = [2, 3, 4] train_maxtix = [1, 0, 0, 0, 0, 0, 0, 0, 1, 0] topk = 3 유저에 대한 rating = [0.9, 0.1, 0.2, 0.4, 0.6, 0.3, 0.2, 0.1, 0.8, 0.1] train_maxtix 에서 1인 index는 rating에서 -INF으로 변경 (훈련에 쓰인 문제는 추천 X) rating = [-INF, 0.1, 0.2, 0.4, 0.6, 0.3, 0.2, 0.1, -INF, 0.1] 이제 rating에서 상위 3개 index를 뽑으면 [0.6, 0.4, 0.3]의 index인 [4, 3, 5]가 된다. test_data에 속한 rating의 개수는 3,4 총 2개이므로 precision = 2/3 = 0.67, recall = 2/5 = 0.4, ndcg = 1.63 / 2.13 = 0.765 (dcg = 1/lg(2) + 1/lg(3) = 1 + 0.63 = 1.63 idcg = 1/lg(2) + 1/lg(3) + 1/lg(4) = 1 + 0.63 + 0.5 = 2.13)

모델별 정확도 비교

Model	Precision@10	Recall@10	nDCG@10
EASE	0.9614	0.1255	0.9691
AUTO_ENCODER	0.9595	0.1252	0.9670
AUTO_ENCODER_CONST	0.9647	0.1259	0.9712

Model	Precision@20	Recall@20	nDCG@20
EASE	0.9259	0.2404	0.9418
AUTO_ENCODER	0.9259	0.2403	0.9410
AUTO_ENCODER_CONST	0.9292	0.2413	0.9443

상세설계 내용

◇ AI

Amazon EC2 환경에서 서버 배포
모델 성능 비교 및 도메인을 고려하여 모델 선정
AUTO_ENCODER, EASE 모델 업로드 및 모델 적용을 통한 문제 추천

◇ Back-end

Amazon EC2 환경에서 서버 배포
Amazon RDS로 Maria DB 인스턴스 관리
Front-end에게 필요한 데이터 전달

- Amazon S3를 활용하여 이미지 리소스 전달

- Swagger를 활용하여 API 명세서 공유

◇ Front-end

Amazon EC2 환경에서 서버 배포
Back-end로부터 전달받은 데이터를 CLIENT에게 전달하며 구현한 화면에 포함시킴

◇ Infra

AI, Back-end, Front-end 서버를 Docker Compose를 활용하여 배포
GitHub Actions를 활용하여 CI/CD 적용

결과 및 평가

완료 작품의 소개

프로토타입 사진 혹은 작동 장면

내용

포스터

내용

완료작품의 평가

내용

향후계획

내용

특허 출원 내용

내용

@@ 492번째 줄: / 492번째 줄: @@
 | 0.1259
 | 0.9712
-|}
+|}<br>
+{| class="wikitable" style="vertical-align:middle;"
+|-
+! Model
+! Precision@20
+! Recall@20
+! nDCG@20
+|-
+| EASE
+| 0.9259
+| 0.2404
+| 0.9418
+|-
+| AUTO_ENCODER
+| 0.9259
+| 0.2403
+| 0.9410
+|-
+| AUTO_ENCODER_CONST
+| 0.9292
+| 0.2413
+| 0.9443
+|}<br>
 ===상세설계 내용===

	서비스 타겟	추천 서비스	문제 제공 서비스	프로필 제공
백준	알고리즘을 해결하고자 하는 사용자	존재하지 않음.	알고리즘 문제 제공	간단한 정보 제공
solved.ac	백준을 사용하는 사용자	존재하지 않음.	제공하지 않음	사용자 맞춤형 정보 제공
programmers	알고리즘을 해결하고자 하는 사용자	존재하지 않음.	알고리즘 문제 제공	간단한 정보 제공
산타 토익	토익을 준비하는 사용자	사용자의 수준에 맞는 문제 추천	토익 문제 제공	사용자 맞춤형 정보 제공
코테고리	취업을 준비하는 사용자	사용자의 수준에 맞는 문제 추천	알고리즘 카테고리 문제 제공	사용자 맞춤형 정보 제공

기술 로드맵 구성	진행 순서 (월단위)
기술 로드맵 구성	3	4	5	6
프로젝트 구상 및 구체화
DB 설계
UI 설계
추천 모델 데이터 수집 및 학습
AI 서버 제작
API 서버 제작
웹 제작
설문 조사
릴리즈 버전 테스트

"Vision"의 두 판 사이의 차이