TCProF: 준지도 학습을 활용한 코드 시간 복잡도 예측 프레임워크

1. 문제 제기

코드의 시간 복잡도 예측은 알고리즘 분석에서 중요한 문제로, 개발자가 작성한 코드의 성능을 평가하는 데 필수적입니다. 하지만 정확한 시간 복잡도 계산은 이론적으로 판별 불가능한 문제이며, 수작업으로 복잡도를 주석 달아주는 것은 전문가의 개입이 필요하기 때문에 데이터 부족 문제가 심각합니다.

최근에는 시간 복잡도 예측을 위한 데이터셋과 기초적인 모델이 등장했지만, 라벨이 부족한 환경(low-resource setting)에서는 기존 접근법이 효과적으로 작동하지 않음이 관찰되었습니다. 이에 따라, 적은 양의 라벨 데이터만으로도 성능을 높일 수 있는 방법론이 필요합니다.

2. 제안 방법론: TCProF (Time-Complexity Prediction SSL Framework)

                                                                     TCProF의 전체 구조

우리는 준지도 학습(SSL) 기법을 활용한 TCProF 프레임워크를 제안합니다. TCProF는 다음 세 가지 핵심 기법을 결합하여 소량의 라벨 데이터만으로도 높은 성능을 달성할 수 있습니다.

1. 데이터 증강(Augmentation)

   • 코드의 루프 구조를 변환하거나(For → While 상호 변환), Back-Translation (BT) 기법을 활용해 다양한 코드 변형을 생성.
   • 이렇게 변형된 코드 데이터를 추가 학습 데이터로 활용.

2. Co-Training 기법

   • 두 개의 모델을 각각 원본 데이터와 증강 데이터를 활용하여 학습.
   • 각 모델이 상대방의 예측 결과를 활용하여 성능을 보완.

3. 기호 기반(Sym) 모듈

   

                                                                     심볼릭 모듈의 구조
   

   • **AST(Abstract Syntax Tree)와 정규 표현식(Regex)**을 활용하여 코드의 구조를 분석하고, 코드의 루프 및 재귀 패턴을 기반으로 기호적 시간 복잡도 예측 수행.
   • 모델이 생성한 가짜 라벨(Pseudo-label)이 부정확할 경우, 기호적 방법을 활용하여 정교한 보정을 수행.

   

                                                          심볼릭 모듈 실제 사용 시나리오.
   

3. 실험 결과

우리는 CodeComplex(Java, Python) 및 CorCoD 데이터셋에서 TCProF의 성능을 평가했습니다.

기존 Self-Training (ST) 기법 및 JointMatch (최신 준지도 학습 프레임워크)와 비교한 결과, TCProF는 기존 기법 대비 60% 이상의 성능 향상을 달성했습니다.

특히, Self-Training 대비 TCProF(UniXcoder)의 성능 향상폭이 64.81%에 달함을 확인했습니다.

                                                              SSL 베이스라인과의 비교 실험.

✅ 주요 실험 결과 요약:

• TCProF는 기존 SSL 기법보다 높은 정확도를 달성.
• 증강 기법(Aug), 기호 기반 모듈(Sym) 적용 시 일관된 성능 향상을 보임.