디지털 라이브러리[ 검색결과 ]
큰 그래프 상에서의 개인화된 페이지 랭크에 대한 빠른 계산 기법
http://doi.org/10.5626/JOK.2022.49.10.859
그래프 내에서 개인화된 페이지랭크(Personalized PageRank, PPR)를 계산하는 것은 검색, 추천, 지식발견 등 여러 분야에서 광범위하게 활용되는 중요한 작업이다. 개인화된 페이지랭크를 계산하는 것은 고비용의 과정이 필요하므로, 개인화된 페이지랭크를 계산하는 효율적이고 혁신적인 방법들이 다수 개발되어왔다. 그러나 수백만 이상의 노드를 가진 대용량 그래프에 대한 PPR 계산은 여전히 시간이 크게 소요되는 작업이다. 그에 더하여, 기존에 제시된 알고리즘들은 그래프 갱신을 효율적으로 처리하지 못하여, 동적으로 변화하는 그래프 처리에 한계가 있다. 이에 대응하여, 본 연구에서는 높은 정밀도를 보장하면서도 빠르게 수렴하는 PPR 계산 알고리즘을 제시한다. 전통적인 거듭제곱법(Power Iteration)에, 축차가속완화법(Successive Over Relaxation)과 초기 추측값 보정법(Initial Guess Revision)을 활용한 벡터 재사용 전략을 적용하여 수렴 속도를 개선하였다. 제시된 방법은 기존 거듭제곱법의 장점인 단순성과 엄밀성을 유지하면서도 수렴율과 계산속도를 크게 개선한다. 또한 개인화된 페이지랭크 벡터의 갱신을 위하여 이전에 계산되어 저장된 벡터를 재사용하여, 갱신에 드는 시간이 크게 단축된다. 본 방법은 주어진 오차 한계에 도달하는 즉시 결과값을 산출하므로 정확도와 계산시간을 유연하게 조절할 수 있으며, 이는 표본 기반 추정방법이나 역행렬 기반 방법이 가지지 못한 특성이다. 실험 결과, 본 방법은 거듭제곱법에 비하여 20배 이상 빠르게 수렴한다는 것이 확인되었으며, 기 제시된 최속 알고리즘과 비교하여도 결과 품질을 일정 수준 이상으로 유지하면서도 수행시간 면에서 우수한 성능을 보이는 것 또한 확인되었다.
Graph2Tree 모델을 이용한 한국어 수학 문장제 문제 풀이
http://doi.org/10.5626/JOK.2022.49.10.807
본 논문은 8개 유형으로 이루어진 한국어 수학 문장제 문제 데이터셋을 자체적으로 구축하여 이를 기반으로 기존에 제시되지 않았던 Graph2Tree 모델 기반 한국어 수학 문장제 문제 자동 풀이 모델인 Ko-Graph2Tree 모델을 제시한다. 최근 공개된 Graph2Tree 모델은 영어 수학 문장제 문제 자동 풀이에 기존의 자연어 처리 모델들보다 뛰어난 성능을 보인 모델이다. 해당 모델은 문제 텍스트 내의 숫자 간 관계성 및 순서, 즉 수학적 관계를 반영한 두 가지의 그래프를 풀이 생성에 사용함으로써 기존의 트리 기반 모델들보다 향상된 성능을 보인다. 자체 제작한 한국어 수학 문장제 문제 데이터셋으로 학습시킨 후 성능을 측정한 결과, 시퀀스 투 시퀀스 구조의 트랜스포머 모델은 정확도가 42.3%, 본 논문이 제시한 Ko-Graph2Tree 모델은 정확도가 68.3%로 26.0%p 더 높은 성능을 보였다.
개체 유형 정보를 활용한 지식 그래프 임베딩
http://doi.org/10.5626/JOK.2022.49.9.773
지식 그래프 임베딩은 그래프의 구조적 특성을 반영하여 개체와 관계를 특성 공간에 나타내는 기술이다. 대부분의 지식 그래프 임베딩 모델은 그래프 구조 이외의 정보를 가정하지 않고 특징 벡터를 생성한다. 하지만 실생활과 밀접한 지식 그래프는 개체의 유형 정보 등 추가적인 정보를 얻을 수 있다. 본 논문에서는 개체의 유형이 클러스터의 역할을 수행할 수 있다는 점에 착안하여, 유형 정보를 반영할 수 있는 손실 함수를 통한 지식 그래프 임베딩 모델을 제시한다. 또한, 지식 그래프 내 관계의 주어/술어에 해당하는 유형이 제한적이라는 관찰을 토대로 개체 유형 제한에 특화된 네거티브 샘플링 기법을 제시한다. 본 논문에서 제시한 모델에 대한 링크 예측을 평가하기 위해 개체 유형 제한을 가진 지식 그래프인 SMC 데이터 셋을 생성하여 실험을 진행하였다. 링크 예측 결과는 본 모델이 네 개의 베이스라인 모델과 비교해서 뛰어난 성능을 보이는 것을 확인하였다.
메신저 사용자 검증을 위한 그래프 기반 채팅 메시지 분석 모델 제안
http://doi.org/10.5626/JOK.2022.49.9.696
메신저를 통한 범죄와 사고가 증가하고 있어 메신저 사용자 검증의 필요성이 대두되고 있다. 본 연구에서는 전통적인 저자 검증 문제를 채팅 텍스트에 적용해 두 개의 그래프 기반 메신저 사용자 검증 모델을 제안했다. 그래프 랜덤워크 모델은 이전 채팅 메시지로 n-gram 전이 그래프를 구축하고, 작성자를 알 수 없는 메시지로 전이 그래프를 순회한 특성을 학습해서 사용자를 검증한다. 실험결과 10,000개의 채팅 대화에서 정확도 86%의 성능을 보였다. 그래프 볼륨 모델은 시간의 흐름에 따라 전이 그래프의 규모가 증가하는 특성을 이용해 사용자를 검증했고, 1,000개의 채팅 대화에서 정확도 87%의 성능을 낼 수 있었다. 전송 시각을 기준으로 채팅 메시지의 밀도를 계산했을 때, 두 그래프 모델 모두 채팅 밀도가 15 이상일 때 80% 이상의 정확도를 보장할 수 있었다.
노드와 링크간의 상호작용을 동시에 반영한 그래프 어텐션 네트워크 기반 지식 그래프 임베딩
http://doi.org/10.5626/JOK.2022.49.7.555
지식 그래프는 실제 세계의 다양한 지식들을 노드와 링크 기반의 트리플 형태로 표현하는 지식구조로서 검색, 질의 응답 등의 여러 분야에서 유용하게 활용된다. 이런 지식 그래프는 불완전하며, 누락된 다른 관계들을 찾기 위해 노드와 링크를 저차원 벡터공간에 효과적으로 표현하는 임베딩 기법들이 많이 연구되었다. 최근 뉴럴 네트워크 기반의 지식 그래프 링크 예측 방법이 많이 연구되었지만, 기존 모델들은 노드에 대한 트리플의 중요도를 구할 때 노드와 링크를 독립적으로 고려하므로 트리플 내의 노드와 링크의 상호작용이 잘 반영하기 어렵다. 본 논문에서는 합성연산자를 이용하여 노드와 링크를 동시에 고려하여 트리플 단위의 중요도를 구하는 임베딩 방법을 제안하며 해당 모델이 지식 그래프 링크 예측에 우수한 성능을 보임을 증명한다.
시각적 관계 예측을 위한 계산 효율적인 조합적 전이 표현 학습법
http://doi.org/10.5626/JOK.2022.49.7.544
장면 그래프는 이미지에 존재하는 객체 사이의 고차원 시각 관계를 표현하기 위해 널리 활용된다. 본 논문에서는 장면 그래프를 자동으로 구축하기위해 객체 사이의 시각 관계를 감지하고 그 관계를 술어로 예측하는 알고리즘을 제안한다. 우리는 기존에 제시된 텍스트 기반 지식 그래프 임베딩 TransR에서 영감을 받아 i) 시각적 관계의 구성적 관점을 고려하기 위한 잠재 관계 부분 공간을 정의하고 ii) 각 부분 공간에서 객체 표현 사이의 전이적 제약을 적용하는 CompTransR을 제시한다. 장면 그래프 생성을 위한 대표적인 벤치마크 데이터인 VRD, VG200 및 VrR-VG에서 제안하는 방법론은 기제시된 모델과 비교하여 학습 복잡도를 줄이는 동시에 우수한 성능을 보였다. 또한, 높은 수준의 시각-언어 추론을 요구하는 문제 중 하나인 이미지 캡션 검색에 장면 그래프가 효과적으로 적용될 수 있음을 보이고, 제안하는 알고리즘으로 예측된 술어 표현이 검색 성능을 높이는데 도움이 됨을 확인하였다.
지리적 인접성을 이용한 아파트 가격변화율 예측 모델 개발
http://doi.org/10.5626/JOK.2022.49.6.424
최근 들어 금관구, 노도강, 마용성 등 주택가격이 권역별로 변동하는 탈동조화 현상이 심화하고 있다. 해당 현상의 특징은 각 권역이 지리적으로 가까운 구들로 구성되어 있다는 것이다. 본 논문은 서울시의 인접한 자치구들 사이에는 가격이 상호 동조한다고 보고 가격 변동이 인접 지역에 의한 것임을 확인하고자 한다. 가설 검증에는 아파트 가격변화율, 거시경제지표 및 사교육 지표가 사용되며 이는 3차원(시간, 거리, 속성)의 데이터로 조립되고 CNN으로 학습된다. 조립 방식에 따라 모델은 3가지 하위 모델(타깃 지역만 고려(I), 원거리 지역 고려(II), 이웃 수 변경(III))로 세분되며 성능은 MAE와 MDA로 측정된다. 실험 결과, 이웃을 사용한 모델은 영속성 모델과 XGBoost 보다 좋은 성능을 보였고 하위 모델은 모델 III(이웃 수 3인 경우), II, I 순으로 좋은 성능을 보였다. 이를 통해 ‘이웃’이 타깃 지역의 아파트 가격변화율에 영향을 미친다는 것을 알 수 있었다.
Transient EMG 신호를 이용한 손가락의 움직임 추정
http://doi.org/10.5626/JOK.2022.49.2.157
본 논문에서는 근전도 신호를 기반으로 손가락의 움직임을 추측하기 위한 딥 러닝 모델을 제안한다. 우리는 또한 모델의 정확도를 평가하고 분석하였다. 우리는 의료 영상의 분석에 널리 이용되는 U-Net의 구조를 모델에 적용하였다. 일반적으로 U-Net은 2차원 영상 처리에 주로 사용된다. 그러나 본 논문에서는 8채널 1차원 시계열 근전도 데이터를 입력으로 사용하고 그 결과로 손가락 움직임에 대한 정보를 얻는다. 8,000개의 동작으로 구성된 데이터 세트를 획득했으며, 이는 훈련 데이터 세트와 평가 데이터 세트로 나누어진다. 모델의 예측 정확도는 약 89.32%이다.
부분 그래프 매칭 문제를 위한 새로운 동적 매칭 순서와 성능 비교
http://doi.org/10.5626/JOK.2022.49.1.1
최근 다양한 분야에서 그래프 분석이 사용되고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나는 부분 그래프 매칭(subgraph matching) 문제이다. 부분 그래프 매칭 문제는 데이터 그래프와 쿼리그래프가 주어졌을 때 데이터 그래프에서 쿼리 그래프의 모든 임베딩(embedding)을 찾는 문제이다. 그동안 이 문제를 해결하는 백트래킹 기반의 많은 알고리즘이 연구되어왔다. 본 논문에서는 이 문제를 해결하는 최신 알고리즘인 DAF에서 제안한 동적 매칭 순서의 문제점을 분석하고 이를 개선한 동적 매칭 순서를 소개한다. 또한, 제안한 매칭 순서를 실제 데이터 그래프를 가지고 실험을 진행하여 가지치기 기법을 사용하지 않았거나 가지치기 기법을 사용하더라도 수행 시간이 매우 짧지 않으면 이전 매칭 순서들보다 효과적임을 입증하였다.
그래프 신경망을 이용한 삭제 기반 한국어 문장 축약
http://doi.org/10.5626/JOK.2022.49.1.32
문장 축약은 주어진 문장의 요지를 담은 짧고 간결한 글을 생성하는 것으로 주로 삭제 기반의 축약 연구가 많이 진행되었다. 삭제 기반의 축약은 문장에서 덜 중요한 부분을 제거하여 문장을 축약하는 것이다. 본 연구에서는 딥러닝 모델을 이용하여 삭제 기반의 한국어 문장 축약 모델을 구축한다. 각각의 단어가 삭제될 것인지 축약에 포함될 것인지 이진 분류하는 기본 모델을 구축하고 여기에 LSTM과 어텐션 레이어를 추가한 모델을 설계한다. 그래프 신경망은 그래프 구조에 딥러닝 방법을 적용한 모델로 본 연구에서는 문장의 구문 구조를 축약에 사용할 수 있도록 그래프 신경망을 도입하였다. 그래프 신경망 중 대표적인 모델인 그래프 합성곱 신경망을 이용하여 의존 트리를 인코딩하고, 인코딩된 트리의 각 노드를 문장 축약 모델의 입력으로 사용한다. 일반적인 그래프 합성곱 신경망은 무방향 그래프만을 다루기 때문에 문장 축약에서 의존 트리의 부모, 자식 노드를 구분하기 위하여 유향그래프 합성곱 신경망을 제안한다. 실험 결과 기본 모델에 그래프 신경망을 적용했을 때 문장 축약의 정확도가 향상되었다. 또한 부모, 자식 노드를 구분할 수 있는 유향그래프 합성곱 신경망이 그렇지 못한 그래프 합성곱 신경망에 비해 높은 F1 점수를 얻었다. 실험을 통해 의존 구문 트리 구조를 명시적으로 반영하였을 때, 문장 축약에 더 좋은 성능을 발휘할 수 있음을 확인하였다.
