디지털 라이브러리[ 검색결과 ]
다중 클래스 멤버쉽 처리를 위한 Bi-LSTM 기반 지식 그래프 완성 기법
http://doi.org/10.5626/JOK.2020.47.6.559
실세계의 지식을 구조화된 방식으로 표현한 지식 그래프는 웹 검색, 추천 시스템과 같이 다양한 분야에서 활용되고 있지만, 엔티티 또는 엔티티 사이의 링크가 누락되는 문제가 존재한다. 이러한 문제해결을 위해 임베딩 기법을 사용하거나 딥러닝을 활용한 다양한 연구들이 진행되었으며, 특히 CNN과 Bidirectional-LSTM을 결합한 최신 연구가 기존 연구들과 비교하여 높은 성능을 나타냈다. 그러나 하나의 엔티티에 대하여 여러 개의 클래스 타입이 정의된 경우 학습 데이터의 양이 기하급수적으로 증대되어 학습시간이 증가하는 문제와 엔티티의 클래스 타입 정보가 정의되지 않으면 학습 데이터 생성이 불가능하다는 한계점이 존재한다. 따라서 본 논문에서는 엔티티의 클래스 타입 수에 상관없이 학습 데이터 생성과 모델에서 학습 및 추론이 가능하도록 미리 학습된 지식 그래프 임베딩 벡터를 사용하는 방법과 vector addition 개념을 활용한 다중 클래스 멤버쉽 처리 방법을 제안한다. 본 논문에서 제안하는 방법의 성능을 평가하기 위해 데이터셋 NELL-995 와 FB15K-237을 대상으로 기존 지식 완성 연구들과 비교 실험을 진행하였으며 MAP이 1.6%p, MRR이 1.5%p 더 높은 성능을 보였다.
링크 추정을 위한 지식 그래프 임베딩 기반의 앙상블 모델
http://doi.org/10.5626/JOK.2020.47.5.473
링크 추정은 개체 사이의 관계를 추정하는 문제로, 지식 베이스를 완전하게 만들기 위한 태스크 중 하나이다. 지식 베이스는 많은 개체와 관계들을 포함하고 있지만, 누락된 지식 트리플들이 존재하기 때문에 완전하지 않다. 누락된 지식 트리플들은 지식 베이스의 활용에 한계를 야기하기 때문에 누락된 관계 정보들을 찾아 지식 베이스를 완전하게 만들기 위해 본 논문은 링크 추정을 수행하고자 한다. 기존의 링크 추정을 위한 연구들은 주로 지식 그래프 임베딩을 활용하여 누락된 관계들을 찾았다. 하지만 임베딩된 벡터들은 정확성이 부족하기 때문에 hit@10에서는 좋은 성능을 보였지만, hit@1에서는 부족한 성능을 보여 주었다. 그러므로 하나의 지식 그래프 임베딩만을 사용하여 링크를 추정하는 것은 효과적이지 않으며, 지식 그래프 임베딩들은 각자의 관점을 가지고서 임베딩하기 때문에 이들을 함께 고려하는 것이 필요하다. 따라서 본 논문에서는 기존의 링크 추정의 성능을 높이기 위하여 지식 그래프 임베딩 기반의 앙상블 모델을 제안한다. 지식 그래프 임베딩 모델들은 각자의 관점 및 특성을 가지고 있기 때문에, 이들을 결합하면 다양한 관점들을 고려할 수 있다. WN18과 FB15K 데이터 셋으로 실험한 결과, 기존의 각 모델들보다 제안한 모델이 평균적으로 13.5% 높은 성능을 보여 주었다. 또한 사용자 파라미터에 기존 모델보다 강건한 결과를 보여 제안한 모델의 우수함을 증명하였다.
네트워크의 중첩 클러스터링 구조를 고려한 정보 확산 모델
http://doi.org/10.5626/JOK.2020.47.4.422
정보 전파(information diffusion) 연구란 네트워크에서 특정 노드(initial adopters)가 새로운 정보를 습득할 것으로 가정하고, 그로부터 다른 노드로 퍼지는 정보의 전파 양상(cascading behavior)에 대한 메커니즘을 모델링하는 것이다. 대부분의 기존 정보 전파 연구들은 노드가 하나의 클러스터(cluster)에만 속한다고 가정하며, 이 가정에 의해 클러스터가 정보 전파를 방해함을 보여 왔다. 하지만, 실제 네트워크에는 노드가 여러 클러스터에 속할 수 있다. 즉, 클러스터는 중첩될 수 있다. 본 연구는 네트워크에 중첩 클러스터(overlapping cluster)가 존재할 때의 정보 전파 양상에 대해 소개한다. 새로운 정보를 습득한 노드가 네트워크의 중첩 클러스터에 속하거나 네트워크의 각 노드에 대해 정보 공존성(compatibility)을 허용하였을 때 클러스터는 정보 전파의 방해요소가 아님을 보인다. 네 개의 실제 네트워크 데이터 셋(dataset)에서 본 연구에서 제시한 모델과 이론을 검증한다.
정교한 이웃 노드 선택법을 활용한 그래프 합성곱 네트워크
http://doi.org/10.5626/JOK.2019.46.11.1193
그래프 합성곱 네트워크(GCNs)는 합성곱 구조를 활용하여 주변 노드들의 정보를 종합하는 방식으로 대상 노드의 표현력을 높인다. 높은 성능을 보이기 위해서는 우선적으로 대상 노드에게 필요한 정보를 전달할 수 있는 주변 노드를 선별하고, 이후 학습시 적절한 필터(filter) 값을 습득하는 과정이 수반되어야한다. 최근 GCNs 알고리즘들은 1-hop 거리의 노드들을 선택하는 등의 비교적 간단한 이웃 노드정의를 활용하고 있다. 이러한 경우 불필요한 정보가 대상 노드에 전파되어 성능을 저하하는 문제가 발생한다. 본 논문에서는 대상 노드와 주변 노드간의 유사도 계산을 통해 유효한 이웃 노드를 선별하여 활용하는 GCN 알고리즘을 제안한다.
데이터 재사용을 고려한 효율적인 연속 서브 그래프 매칭 기법
http://doi.org/10.5626/JOK.2019.46.8.842
다양한 응용에서 그래프 스트림에 대한 활용이 증가됨에 따라 실시간으로 변화되는 서브 그래프를 탐색하기 위해서는 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 그래프 스트림에서의 색인 재사용과 분산 처리가 가능한 효율적인 연속 서브 그래프 매칭 기법을 제안한다. 서브 그래프 매칭 질의를 분산 처리하기 위해 차수 기반의 질의 분할 기법을 제안하고 그래프 스트림을 분할된 질의 기반으로 색인한다. 다수의 질의가 입력되는 환경에서 야기되는 색인의 부하를 감소시키기 위해서 색인 정보를 재사용한다. 또한, 각 서버의 색인 부하를 계산하는 비용 모델을 통해 질의 할당을 수행한다. 제안하는 기법은 스트림 환경에서 효율적인 분산 처리를 수행하기 위해 스톰에서 구현된다. 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.
하이퍼그래프 데이터베이스에서 구조 인덱스를 활용한 효율적인 동형 서브그래프 검색
http://doi.org/10.5626/JOK.2019.46.7.697
그래프는 실세계의 객체 간 관계를 모델링 할 수 있으며, 관계들을 분석하는 데 사용된다. 하이퍼그래프는 그래프의 일반화된 모델로서 하나의 하이퍼에지가 2개 이상의 객체가 참여하는 관계를 나타낼 수 있다. 본 논문에서는 데이터 하이퍼그래프에서 질의 그래프와 동형인 서브그래프를 검색하는 효율적인 방법을 제안한다. 동형 서브그래프 검색의 높은 계산 비용을 줄이기 위해 기존 연구들에서는 각 질의 노드 에 대해 정답이 될 수 있는 후보군을 선택하고, 후보들의 조합으로 이루어진 서브그래프와 질의 그래프의 동형성을 검증하여 정답을 반환한다. 본 연구에서는 검색 성능을 높이기 위해, 질의 그래프를 여러 개의 서브그래프로 분해하여 제안하는 구조 인덱스로 각 서브그래프의 후보를 찾고, 제안하는 검색 알고리즘으로 서브그래프 동형성을 검증한다. 실제 데이터셋을 이용한 실험에서 제안 연구는 기존 연구 대비 검색 응답 속도 측면에서 최소 10배의 성능 향상을 얻었다.
맥락 정보를 이용한 시각 장면 이해
http://doi.org/10.5626/JOK.2018.45.12.1279
본 논문에서는, 시각 장면 이해의 한 문제로서, 입력 영상들로부터 장면 그래프와 영상 캡션을 동시에 생성하는 문제를 다룬다. 장면 그래프는 영상 내 물체들과 그들 간의 관계들을 나타내는 정형 지식 표현이며, 영상 캡션은 주어진 영상에 담긴 장면을 서술하는 자연어 문장이다. 본 논문에서는 이러한 문제를 효과적으로 해결하기 위해, 맥락 정보를 서로 교환함으로써 서로 다른 두 가지 표현을 상호보완적으로 생성하는 새로운 심층 신경망 모델을 제안한다. 제안 모델은 물체 탐지, 관계 탐지, 캡션 생성 등 각기 다른 세 가지 계층들로 구성되며, 각 계층은 그 계층에 부여된 작업을 성공적으로 수행하기 위해 맥락정보를 적절히 활용한다. 제안 모델의 성능을 평가하기 위해, 대규모 벤치마크 데이터 집합인 Visual Genome을 이용한 다양한 실험들을 수행하였다. 이러한 실험들을 통해, 맥락 정보를 활용하는 제안 모델이 기존의 경쟁 모델들에 비해 높은 성능 향상이 있었음을 확인할 수 있었다.
부분 임베딩 기반의 지식 완성 기법
http://doi.org/10.5626/JOK.2018.45.11.1168
지식 그래프는 실세계의 개체들과 개체 사이의 관계로 구성된 네트워크를 의미하며, 최근에는 대용량 데이터를 기반으로 구축되고 있다. 대부분의 지식 그래프들은 누락된 엔티티 또는 관계들로 인해 불완전성에 대한 문제점이 존재한다. 이를 해결하기 위해 지난 연구들은 지식 그래프를 다차원 공간상에 임베딩하는 방법을 적용했다. 그러나 이러한 연구들은 지식 그래프가 변화하지 않는다는 가정을 하고 있다. 이로 인해 새로운 트리플이 추가되어 빠르게 진화하는 실세계의 지식 그래프에 적용하기 위해 반복적인 임베딩 모델의 재학습은 고비용의 연산이 요구되며, 실용적이지 못하다. 따라서 본 논문에서는 변화하는 지식 그래프를 대상으로 하는 부분 임베딩 기반의 지식 완성 방법을 제안한다. 지식 완성의 대상이 되는 관심 관계들을 추출하기 위해 온톨로지의 공리와 문맥 정보를 활용했으며, 이를 기반으로 엔티티와 관계들을 임베딩하고 학습하여 지식 완성을 수행했다. 제안하는 방법의 성능을 측정하기 위해 Freebase와 WiseKB 데이터셋을 대상으로 최신 지식 완성 연구들과의 비교 실험을 진행하였고, 평균적으로 학습시간이 약 49%∼90% 감소했으며, 전체적인 성능이 약 6.7% 증가하는 것을 확인했다.
그래프 기반 준지도 학습에서 빠른 낮은 계수 표현 기반 그래프 구축
http://doi.org/10.5626/JOK.2018.45.1.15
낮은 계수 표현(Low-Rank Representation, LRR) 기반 방법은 얼굴 클러스터링, 객체 검출 등의 여러 실제 응용에 널리 사용되고 있다. 이 방법은 그래프 기반 준지도 학습에서 그래프 구축에 사용할 경우 높은 예측 정확도를 확보할 수 있어 많이 사용된다. 그러나 LRR 문제를 해결하기 위해서는 알고리즘의 매 반복마다 데이터 수 크기의 정방행렬에 대해 특이값 분해를 수행하여야 하므로 계산 비효율적이다. 이를 해결하기 위해 속도를 향상시킨 발전된 LRR 방법을 제안한다. 이는 최근 발표된 Fast LRR(FaLRR)을 기반으로 하며, FaLRR이 속도는 빠르지만 실제로 분류 문제에서 성능이 낮은 것을 해결하기 위해 기반 최적화 목표에 추가 제약 조건을 도입하고 이를 최적화하는 방법을 제안한다. 실험을 통하여 제안 방법은 LRR보다 더 좋은 해를 빠르게 찾아냄을 확인할 수 있다. 또한, 동일한 해를 도출하는 방법을 찾아내기는 어렵지만 최소화하는 목표가 추가될 경우 더 좋은 결과를 나타내는 Fast MLRR(FaMLRR)을 제안한다.
추상 도달가능성 그래프 기반 소프트웨어 모델체킹에서의 탐색전략 고려방법
http://doi.org/10.5626/JOK.2017.44.10.1034
본 연구에서는 추상 도달가능성 그래프(ARG) 기반의 소프트웨어 모델체킹에서 그래프 탐색전략을 설정할 수 있는 새로운 방법을 제시한다. ARG의 여러 실행 경로를 하나로 묶어 모델체킹 성능을 향상시키는 기법인 블록 인코딩(Block Encoding) 기법을 활용하는 경우 기존의 기법들은 인코딩 전의 ARG에서 인코딩을 효과적으로 수행할 수 있는 탐색전략만을 고려하였을 뿐 실제 모델체킹의 성능을 좌우할 수 있는 인코딩 후의 ARG에 대한 탐색전략을 고려하지 못하는 문제가 있었다. 본 연구에서는 기존 연구에서 제시된 탐색 기법을 사용하여 블록 인코딩을 효과적으로 수행하는 동시에 인코딩된 후의 ARG에 대한 탐색 순서를 고려할 수 있는 이중 탐색전략 기법을 제시한다. 또한 탐색 순서의 변화가 모델체킹의 성능에 미치는 영향을 확인하기 위하여 제시하는 기법을 오픈소스 모델체킹 도구에 구현하고 벤치마크 실험을 수행하였으며 탐색전략이 달라지면 모델체킹의 성능이 달라지는 현상을 확인하였다.
