Paper :
Main interset
복잡한 자연어 문제에서 다중 연결을 활용한 추론 과정을 해결하고자 한다. 쿼리가 복잡해지고 길어질수록 이 문제를 해결하는 것이 중요하다. 따라서 본 연구에서는 지식 그래프(Knowledge Graph, KG)에서의 multi-hop 추론을 목적으로 한다. 예를 들어 선수 $P$가 클럽 $T$에서 활동하고 $T$가 리그 $L$에 포함되어 있음이 KG에서 다수 확인되면 모델은 스스로 $playerPlaysForTeam(P,T)\wedge teamPlaysInLeague(T,L)\Rightarrow playerPlaysInLeague(P,L)$와 같은 공식을 도출해 내는 것이다. 이 공식을 testing에서 적용하면 두 entity 사이의 link를 예측할 수 있게 되는 것이다.
즉 위의 formula 뿐만 아니라 KG에서 신뢰도 높게 평가된 formula들을 다수 추출한 시스템은 두 entity 사이의 관계를 알아내는 능력을 갖게 된다. 따라서 이런 추론 머신은 복잡한 QA 시스템에서 필수적인 요소로 자리잡을 수 있는 것이다.
Problem with previous models
위에서 소개한 흐름의 연구 중에서 초기에 두각을 보인 모델은 PRA(2011)가 있었다. 이는 relation path를 찾는 random walk기반의 모델이다. 하지만 경로 이외에는 아무런 정보를 이용하지 않을뿐더러 학습하고자 하는 path의 종류를 처음부터 정해놓는 완전히 이산적인 환경에서 학습이 진행된다는 제약이 있다. 본 연구 DeepPath의 저자들은 PRA처럼 multi-hop 추론을 하는 방법을 고수하지만 좀 더 자유로운 환경에서의 학습을 추구한다.
그렇게 이들이 제안한 새로운 환경은 강화 학습(Reinforcement Learning, RL)기반 경로 학습 시스템인 DeepPath이다. 이는 path based 접근에 RL을 최초로 접목시킨 모델이다.
Architecture
먼저 만들고자 하는 것이 무엇인지 명확히 하고 DeepPath의 구조를 설명하겠다. 우리는 agent를 학습하고자 한다. 이 agent는 두 entity 쌍을 잇는 가장 신뢰도 높은 경로를 잘 찾는 능력이 있기를 우리는 바란다. 즉 학습 과정에서 positive example $(h,r,t)$가 주어졌을 때 agent는 $h$에서 출발해 $t$로 도착하는 경로를 찾는 방법을 배운다. 이후에 testing에서도 학습이 완료된 agent를 사용해 출발 노드를 기준으로 경로 탐색을 진행했을 때 도착 확률이 가장 높은 노드가 출발 노드와 link가 있다고 한다.
DeepPath의 RL 시스템은 2가지 부분으로 이루어져있다.
첫 번째는 agent가 상호작용할 환경이다. 이 환경은 Markov decision process(MDP)로 구성될 수 있으며 MDP는 튜플 $<S,A,P,R>$로 이루어져 있다.
$S$(States) : 연속적인 state 공간이다. 즉 KG에서 현재 agent 위치에 대한 설명이라고 볼 수 있다. 하지만 KG에서 entity와 relation은 이산적인 값들이다. 체스판이나 바둑판같은 연속 그리드 위에서 agent가 이동하고 있는 것이 아니기 때문에 state를 계산하기 어렵다. 따라서 이 문제를 연속적인 공간으로 끌어오려면 entity와 relation을 연속적인 값으로 표현할 필요가 있기 때문에 임베딩 기반 모델인 TransE, TransH와 같은 모델들의 힘을 빌린다. 따라서 step $t$에서 state vector는 $\textbf{s}_t=(\textbf{e}_t,\textbf{e}_{target}-\textbf{e}_t)$로 계산된다. $\textbf{e}_t$는 현재 위치해 있는 노드의 임베딩이고 $\textbf{e}_{target}$은 target entity의 임베딩이다. 결국 두 벡터를 concatenate한 결과로 $\textbf{s}_t$를 나타낼 수 있게 된다. 이때 relation 임베딩은 state에 사용되지 않는다. 왜냐하면 agent의 위치와 relation의 종류는 관련이 없기 때문이다.
$A$(Action) : 현재 위치에서 할 수 있는 actoin space이다.
$R$(Rewards) : Agent의 행동에 대한 보상 체계이다. DeepPath는 3가지 측면에서 보상을 준다. 3가지나 주는 이유는 KG의 action space가 거대하기 때문에 단순히 목적지 도착에 대한 보상만으로는 sparse 하기 때문이다.
1. 정확도
목적지 entity에 도달했는가에 대한 보상이다.
2. 경로 효율성
실험적으로 짧은 경로들이 더 높은 신뢰도의 결과물을 얻음이 관찰되었기 때문에 경로의 길이가 길어질수록 보상을 감소시킨다.
3. 경로 다양성
Positive sample은 $(\textbf{e}_{source},\textbf{e}_target)$의 형식을 갖는다. 즉 어떤 positive example에 대해서도 처음 state는 $(\textbf{e})_{source},\textbf{e}_{relation}$로 나타낼 수 있다. 이는 positive sample들의 초기 state가 벡터 공간에서 비슷하게 생길 수 있기 때문에 agent가 탐색한 경로들 사이의 중복, 상관관계가 있을 위험이 있다. 따라서 현재 경로 $\textbf{p}$와 다른 경로들 $\textbf{p}_i$ 사이의 평균각이 클수록 보상이 크다.
두 번째는 RL agent이다. 이는 정책 네트워크로 이루어져 있다. $\pi_\theta (s,a)=p(a|s;\theta )$와 같이 나타낼 수 있으며 2개의 DNN으로 이루어져 있고 마지막 출력 층은 취할 수 있는 모든 action(어느 relation을 선택할 것인지)에 대한 확률이므로 relation의 총개수가 차원이 된다. 물론 action은 확률로 나타내야 하기 때문에 출력층은 softmax이다.
$P$(Transition probability matrix) : 현재 state와 가능한 action이 주어졌을 때 다음 state에 대한 확률이다.
RL agent의 구성은 위와 같이 설명을 끝냈다. 이제부터는 훈련 과정에 대해 더 자세히 설명해 보겠다.
KG에서 action space가 큰 것은 여전한 문제이다. 따라서 supervised policy를 적용해 준다. 이 방법은 옳은 경로들에 대해 미리 agent가 학습할 기회를 주는 것이다. Supervised policy가 최초로 적용된 알파고의 경우 전문가의 초기 몇 수들이 사용되었다면 DeepPath에서는 $e_{source}$에서부터 $e_{target}$으로 가는 경로를 BFS로 탐색해 사용한다. 하지만 BFS가 짧은 경로들을 주로 찾는다는 것이 문제가 된다. 왜냐하면 경로의 길이는 $r_{EFFICIENCY}$에 의해서 통제되고 있는데 supervised policy에 의해서도 영향을 받으면 공정성에 어긋나고 실제로 신뢰도가 높은 잠정적 긴 경로들을 학습할 기회를 잃을 수 있기 때문이다.
따라서 두 개의 BFS를 진행하여 randomness를 부여해 준다. 이 방법은 $e_{source}$에서 BFS를 시작해 일정 거리 탐색 후 나온 노드를 $e_{inter}$로 정의하고 $e_{inter}$를 기준으로 새로운 BFS를 시작한다. 마지막으로 $(e_{source},e_{inter})$경로와 $(e_{inter},e_{target})$경로를 이어 붙여 supervised policy를 위한 데이터를 완성시킨다.
이 경로 데이터들을 갖고 누적 기대 보상을 최대화하기 위해 파라미터 $\theta$를 업데이트하는 방법으로 Monte-Carlo Policy Gradient를 사용한다.
$J(\theta)$는 하나의 positive sample에 대한 전체 보상 값이다. 우리가 randomized BFS로부터 얻은 경로는 아래의 목적 함수를 사용해 policy network를 업데이트해주면 된다.
보면 supervised policy 경로는 agent가 어떤 state에 대해서도 가장 올바른 선택을 하였다고 전제해서 생성된 데이터이기 때문에 $\pi (a=A_i|s_t;\theta)=1$이다.
Supervised policy learning을 마무리했다면 이제 전적으로 agent의 보상에 따르는 훈련을 할 차례이며 이 단계를 retraining 단계라고 한다.
step fail은 경로가 $max\_length$를 넘어가거나 더 이상 타고 이동할 relation이 없는 상태를 일컫는다.
학습이 끝났을 때 DeepPath는 이제 entity 쌍이 주어졌을 때 그 사이의 relation link를 예측할 수 있게 된다. 또한 agent가 학습한 path formula로 추론하기 위해 경로들을 re-rank 해야 한다. 하지만 어떤 노드는 하나의 relation(e.g., $personNationality^{-1}$)이 다수 연결되어 있을 수 있어 계산하기 복잡할 수 있다. 따라서 아래의 bi-directional search를 사용해 binary path feature를 얻고 path에 대응하는 파라미터와 함께 선형 회귀시켜 파라미터를 학습한다.
Experiments
사용된 데이터셋은 다음과 같다.
Link prediction는 쿼리 entity와 relation이 주어졌을 때 target entity를 rank 하는 task이다.
Fact prediction은 특정 relation에 대해 positive sample과 negative sample을 함께 rank 한다.
추가적으로 살펴볼만한 결과는 같은 path based 모델인 PRA와 비교했을 때 relation마다 학습한 reasoning path의 개수이다.
RL(DeepPath)이 PRA보다 훨씬 적은 수의 path를 찾았지만 그럼에도 MAP는 RL이 더 높았다. 이는 RL의 path들이 더 신뢰도가 높다고 해석할 수 있다.
또한 supervised policy learning의 효과도 확인할 수 있다. 아래는 supervised에 사용된 training episode의 개수에 대해 testing에서 10 step 안에 성공적으로 target entity에 도착한 비율을 $succ_{10}$으로 나타낸 것이다.
Conclusion
강화 학습을 사용해 KG에서 reasoning path를 학습함에 의의가 있다.
