code와 함께 보는 TransE 논문 리뷰

논문: Bordes, Antoine, et al. "Translating embeddings for modeling multi-relational data." 

코드: github.com/bladejun/Knowledge_graph_tensorflow

bladejun/Knowledge_graph_tensorflow

---

entity와 relation의 다양한 관계를 저차원의 벡터 공간에 표현이 가능하다면 추천시스템에서 지식그래프를 활용하여 user-item간의 관계를 표현하고 그 활용은 무궁무진하게 될 것이다. 이에 Knowlege Graph Embedding(KGE) 관련된 논문을 차근차근히 훑어보려고한다.

 

먼저 지식그래프 임베딩의 처음 제안된 TransE 알고리즘이다. 되게 간단한 방법이다. 하지만 뒤에서 설명하겠지만 1대 다 관계를 동일한 space에 embedding할때 많은 문제점이 발생하기 때문에 TransE를 이어서 많은 알고리즘들이 제안되었다. 이후 알고리즘은 차차 리뷰를 올려보려고 한다.

 

•  지식그래프에서의 표기법

트리플이라고도 하며 (h, l, t)로 표현한다. 이는 head, relation, tail을 의미하며 head와 tail의 entitiy의 relation이라는 관계가 있다는 뜻이다. 

 

• TransE 정의

해당 논문에서는 TransE를 엔티티(head, tail)를 저차원의 임베딩으로 표현하기위해 학습하는 모델이라고 적혀있다. wmr 즉 embedding 공간에서 entitiy 관계 표현을 해석이 가능하게 만든것이다. (h, l, t)가 있다고 가정하면, tail entity의 embedding이 head entity embedding에다가 relation vector를 더한것과 비슷하게 만드는과정이라고 볼 수 있다.

 

• Pseudo code

transE pseudo code

---

• input: S는 앞에서 말했던 triple (head, relation tail)의 집합이다. E는 entitiy embedding이고 L은 relation embedding 그리고 해당 논문에서 margin을 넣어서 표현했고 k는 embedding 차원이다.
• 1 line: relation embedding 초기값 설정, boundary를 설정 // 크기는 entity size와 embedding dimension

# 초깃값 boundary 설정
bound = 6 / math.sqrt(self.k)

self.relation_embedding = tf.get_variable(
                          name='entity',
                          shape=[self.params.entity_size, self.k],
                          initializer=tf.random_uniform_initializer(-bound, bound)
			  )

•  2 line: normalize

  self.entity_embedding = tf.nn.l2_normalize(self.entity_embedding, axis=1)

• 3 line: entity embedding

self.entity_embedding = tf.get_variable(
                        name='entity',
                        shape=[self.params.entity_size, self.k],
                        initializer=tf.random_uniform_initializer(-bound, bound)
			)

• 5 line: normalize

self.relation_embedding = tf.nn.l2_normalize(self.relation_embedding, axis=1)

• 7 line: triplets 초기화

init_ops = [tf.global_variables_initializer(), tf.local_variables_initializer(), tf.tables_initializer()]

• 9 line: corupted triplets 생성 = 즉, negative sample 생성 / 해당 논문에서는 head를 바꾸거나 tail을 임의로 선택한다고 적혀있다. 둘다 동시에 바꾸는 경우는 x

# corrupt sampling
def sample():
	if random.random() < 0.5:
		return lambda h, t, r: (h, t, r, random.choice(entity), t)
	else:
		return lambda h, t, r: (h, t, r, h, random.choice(entity))       

임의의 random값 head_negative, tail_negative 생성

def generate_negative_samples(infile, outfile):
    head_entities, tail_entities = set(), set()
    triples = []
    for line in open(infile):
        h, t, r = line.strip().split('\t')
        head_entities.add(h)
        tail_entities.add(t)
        triples.append([h, t, r])

    head_entities = list(head_entities)
    tail_entities = list(tail_entities)
    
    with open(outfile, "w") as fo:
        for h, t, r in triples:
            head_neg = h
            tail_neg = t
            prob = random.random()
            if prob > 0.5:
                head_neg = random.choice(head_entities)
            else:
                tail_neg = random.choice(tail_entities)
            fo.write('\t'.join([head_neg, tail_neg, r])+'\n')

• 10 line: positive sample과 negative sample 둘다 사용

with tf.name_scope('lookup'):
  self.h = tf.nn.embedding_lookup(self.entity_embedding, self.iterator.h)
  self.t = tf.nn.embedding_lookup(self.entity_embedding, self.iterator.t)
  self.r = tf.nn.embedding_lookup(self.relation_embedding, self.iterator.r)
  self.h_neg = tf.nn.embedding_lookup(self.entity_embedding, self.iterator.h_neg)
  self.t_neg = tf.nn.embedding_lookup(self.entity_embedding, self.iterator.t_neg)

         

• 12 line: loss function SGD를 사용해서 parameter update

# score function
def _score_func(self, h, r, t):
        """f_r(h,t) = |h+r-t|"""
        with tf.name_scope('score'):
            if self.params.score_func.lower() == 'l1':  # L1 score
                score = tf.reduce_sum(tf.abs(h + r - t), axis=1)
            elif self.params.score_func.lower() == 'l2':  # L2 score
                score = tf.sqrt(tf.reduce_sum(tf.square(h + r - t), axis=1))
        return score

# positive score
score_pos = self._score_func(self.h, self.r, self.t)

# negative score
score_neg = self._score_func(self.h_neg, self.r, self.t_neg)

# loss function
self.loss = tf.reduce_sum(tf.maximum(0.0, self.params.margin + score_pos - score_neg))

# optimizer
optimizer = get_optimizer_instance(self.params.optimizer, self.params.learning_rate)
self.global_step = tf.Variable(initial_value=0, trainable=False, name='global_step')
self.train_op = optimizer.minimize(self.loss, global_step=self.global_step)