디지털 라이브러리[ 검색결과 ]
극대공통부분서열을 찾는 개선된 알고리즘
http://doi.org/10.5626/JOK.2023.50.9.737
두 문자열의 극대공통부분서열(MCS)은 어떤 문자를 삽입하여도 더 긴 공통부분서열을 만들 수 없는 공통부분서열이다. 최장공통부분서열(LCS)과 달리 MCS의 길이는 다양하고, 가장 긴 MCS가 LCS이다. LCS는 일반적으로 두 서열의 유사도를 비교할 때 사용되지만, 계산하는데 매우 긴 시간이 걸린다. MCS는 LCS보다 빠르게 계산할 수 있으므로 더 긴 MCS를 찾는 문제는 중요하다. 길이의 합이 n인 두 문자열 X와 Y의 MCS 중 하나를 O(n) 공간을 이용하여 O(n√(logn/loglogn)) 시간에 계산하는 알고리즘이 제시되었고 이를 개선한 알고리즘들도 제시되었다. 본 논문에서는 기존의 알고리즘들보다 더 많은 문자를 확인하여, 상수 k가 주어졌을 때 O(kn) 공간을 이용하여 O(n√(logn/loglogn)) 시간에 MCS를 계산하는 알고리즘을 제시한다. 실제 데이터와 무작위로 생성한 데이터를 이용하여 실험을 진행한 결과, 본 논문에서 제시한 알고리즘으로 계산된 MCS의 길이가 기존의 알고리즘으로 계산된 MCS보다, 최대 6.31배 길다.
철저한 대조 학습 방법을 통한 생성적 적대 신경망의 불균형 데이터 생성 품질 향상
http://doi.org/10.5626/JOK.2023.50.4.295
딥러닝(Deep learning) 알고리즘의 성능이 향상되면서 실세계의 다양한 문제를 해결하기 위한 방법으로 사용되고 있다. 실세계를 반영하는 데이터의 경우 사건의 발생 빈도나 수집 난이도에 따라 데이터의 불균형(Imbalance)이 나타날 수 있다. 데이터를 구성하는 클래스의 수가 일정하기 않은 데이터를 불균형 데이터라고 하며, 특히 데이터가 상대적으로 적은 소수 클래스는 딥러닝 알고리즘을 통해 학습하기 어렵다. 최근에는 데이터 증강을 위한 방법으로 생성적 적대 신경망(Generative Adversarial Nets, GANs)이 응용되고 있으며, 소수 클래스 학습을 위해 자기 지도 학습(Self-supervised learning)기반의 사전 학습(Pre-training)이 제안되었다. 하지만 생성 모델(Generative Model)을 학습하는 과정에서 불균형 데이터의 클래스 정보를 활용하기 때문에 소수 클래스의 학습이 제대로 이루어지지 않아 생성 데이터의 품질이 떨어지는 문제가 나타난다. 이러한 문제를 해결하기 위하여 본 논문에서는 유사도 기반의 철저한 대조 학습(Exhaustive Contrastive Learning) 방법을 제안하였다. 제안 방법은 프레쳇 인셉션 거리(Frechet Inception Distance, FID)와 인셉션 점수(Inception Score, IS)를 통해 정량적으로 평가하였다. 본 논문에서 제안하는 방법은 기존 방법보다 프레쳇 인셉션 거리는 16.32, 인셉션 점수는 0.38의 성능 개선을 확인하였다.
