USTORY: Unsupervised Story Discovery from Continuous News Streams via Scalable Thematic Embedding

얼마 전, 텍스트마이닝 공부를 하면서 네이버 기사들을 크롤링하여 군집화하는 작업을 진행해보았다.

해당 작업에서는 코사인 유사도를 구해서 특정 threshold (ex. 0.5)를 기준으로, 해당 threshold를 넘으면 같은 기사로 분류하고,

아니면 다른 기사로 분류하는 작업을 진행했었다. (https://yjoonjang.tistory.com/7)

이런 실습은 정말 재미있었음과 동시에, '실제로도 이렇게 간단하게 cosine similarity만을 고려해서 군집화 할까?' 라는 의문을 제기했다 .

이에 리서치 해보던 중 이 논문을 읽게 되었는데, 내용이 상당히 흥미로웠다.

이번에도 자세히 읽었으니, 읽은 흔적을 첨부해본다.

2304.04099.pdf

12.22MB

---

Abstract

뉴스 기사에 있어서, 기사의 모든 정보를 무분별하게 인코딩하는 단순 모델의 적용은 텍스트가 풍부하고, 시시각각 변화하는 뉴스 스트림 처리 시 비효율적인 부분을 보였다.

이에 USTORY라는 프레임워크를 개발하여 새로운 thematic embedding과 pretrained sentence encoder로 공유된 temporal theme (시간적 정보)를 고려하여 동적으로 article과 story를 나타내게 했다.

해당 프레임워크는 시간, 테마를 고려한 동적 embedding과 새로움을 고려한 적응적 clustering을 사용하여 실제 뉴스 데이터셋으로 좋은 퍼포먼스를 보여 주었다.

---

Introduction

USTORY는 인간 주석 없이도 실시간 뉴스 큐레이션 서비스와 추천, 요약, 이벤트 감지와 같은 task를 수행할 수 있다.

본래 연구들에서는 LLM 기반의 PSE를 사용하여 문장을 building block으로 사용해 article을 embed 했다.

이는 article의 문장마다 single article representation으로 바꾸는 indiscriminative embedding 방식을 사용했는데, 많은 문장들을 단 하나의 대표적인 문장으로 간주하다보니 content의 테마를 이해하는데 당연히 한계가 생길 수밖에 없었다. 이에 story discovery의 퍼포먼스가 저하되었다.

 

이에 대한 해결방안으로 thematic embedding과 PSE를 결합한 방식이 제시됐는데, 이는 최신 뉴스 stream에서 실시간으로 포착된 theme을 공유하여 동적으로 article와 story를 embed 하는 방식이다.

해당 방식은 story가 비슷한 문장들만 감별하고, 뚜렷한 story들로 군집화하여 앞선 embedding들보다 더 좋은 article 유사도를 보여주었다.

 

해당 과정에서 다음과 같은 문제들을 해결해야 했다:

1. story의 특별한 주제는 자동적으로 식별되고, 항상 최신 버전이 story들이 유지돼야 한다.
2. 기사 등은 언제나 사라질 수 있으므로, 항상 군집화할 수 있는 적응적인 메커니즘이 필요하다.
3. embedding, clustering이 효율적이고 scalable 해야 한다.

USTORY는 이러한 문제들을 다음과 같이 해결한다:

1. 시간적인 테마를 체계적으로 식별하고 테마와 시간의 관련성을 고려하여 article과 story를 embedding한다.
2. 기사를 기존의 이야기에 할당하거나 새 이야기의 시작을 위해 article-story 신뢰도 점수를 추정한다.
   이 과정에서 USTORY는 할당된 기사를 간단하게 처리하기 위해 최소한의 정보만 요약하여 관리한다.

---

Thematic Embedding

1. Motivation

기존 word-level과 entire article-level granularity (article을 얼마나 세부적으로 분석/군집화하는지 나타내는 척도)를 사용하면 story를 나타내는 의미를 얻어내기 너무 어렵다.

그러나 sentence-level을 사용하면 의미의 모호함을 균형 있게 맞추고, 전형적 LLM input의 제한을 받는다.

해당 논문에서는 pre-trained 문장 인코더로 기사를 임베딩할 때, 문장을 작은 구성 요소 (building block)로 보고 활용한다.

 

또, 긴 문장을 embedding 하는 경우에 벡터를 concat하거나 mean-pooling하여 대표 의미를 포착하려는 기존의 방식이 theme과 연관 없는 정보를 얻어내는 경우도 있었다 (아래 그림 참조).

이에 USTORY에서는 PSE와 thematic embedding을 함께 사용하며 특정 뉴스 stream에서 기사의 시간적 theme을 식별하여, 기사와 이야기를 동적으로 embedding한다.

2. Temporal Theme Identification

시간적 theme을 얻기 위해, keyword를 추출하는 과정을 우선 거친다. 그 이유는 간단한 토큰화 방식으로 키워드를 추출하기 쉽고, 다양한 keyword들의 조합으로 theme을 명확하게 나타내기 좋기 때문이다.

이후에는 time-decaying 정보를 popular-ranking 함수에 반영함으로써 thematic 키워드를 식별할 수 있다.

위의 식에서 rec-pop이 time-decaying 정보와 관련된 함수이고, dist(k,D)가 score function이다.

3. Theme/Time-aware Dynamic Embedding

1. Article Embedding

USTORY는 theme 유사성을 weight로 가진 문장들을 모아 글을 동적으로 나타낸다. 이때 문장에서 나타난 키워드의 주기와 중요성을 고려한다. 작성된 식은 다음과 같다:

2. Story Embedding

이후, 특정 기사를 대상으로 할 때, 그 기사와 관련된 다른 기사들의 임베딩 표현을 사용하여 이야기를 표현한다.

이때, 각각의 기사는 대상 기사와의 시간적인 관련성에 따라 가중치를 부여한다. 이 가중치를 고려하여 다른 기사들의 임베딩을 pooling하여 이야기를 표현하게 된다. 관련된 식은 다음과 같다:

최종적으로 시각화한 그림은 다음과 같다:

정리하면,

1. 스토리가 주어지고 article을 embedding하는 경우, theme-relevant 문장들이 주가 된다.
2. article이 주어지고 스토리를 embedding하는 경우, 스토리의 article 중 주어진 article과 가장 가까운 article이 해당 스토리를 대표하게 된다.

---

Novelty-Aware Adaptive Clustering

Overview

이 챕터에서 얘기하는 내용은 다음과 같이 요약 가능하다:

1. 현존하는 story가 없으면, 새 article은 각각의 theme으로 표현되고, seed story들은 새 article로부터 cluster-center initialize된다.
2. 할당되지 않은 기사들은 기존 이야기 중 하나에 잘 할당될 수 있는지 확인된다.
   이후 article-story쌍이 동적으로 embedding되고, 테마적 유사도 기반하여 신뢰도 점수가 계산된다.
3. 남은 할당되지 않은 article들이 새 story를 형성하도록 새 story를 발굴한다.

Novel Story Discovery

Initial Article Embedding

현존하는 story가 없으면, article별 theme은 thematic embedding을 통해 이루어진다.

Seed Stories Discovery

thematic embedding에 cluster center initialization 기술이 더해져 할당되지 않은 article들의 표현이 새로운 seed story들을 찾는 것에 사용된다. USTORY는 이 과정에서 관성이 가장 낮은 seed center을 찾아 가장 독특한 seed story의 주제를 찾는다.

Confidence-based Story Assignment

현존하는 story가 있을 경우, 할당되지 않은 article들은 story들 중 하나에 할당되기 위해 평가된다.

이를 위해 현존하는 story들의 시간적 theme들이 업데이트 되고, 스토리와 할당될 article들의 thematic 유사도를 찾아 article-story confidence score을 얻는다.

Article-Story Thematic Similarity

USTORY는 article과 story의 관계에 있어 다음 theme 2개를 고려한다.

1. Semantic Themes: 위 2개의 코사인 유사도로 추정한다.
2. Symbolic Themes: thematic keyword 분포의 다양성으로 추정한다.

Thematic 유사도의 식은 다음과 같다:

처음에 max(0,~)라고 써있는 부분은 article과 story의 코사인 유사도이고,

다음 JSD(~)라고 써있는 부분은 article과 story의 keyword 분포 JS-divergence 이다.

Article-Story Assignment

마지막으로, USTORY는 article과 story의 thematic 유사도를 다른 후보 assignment들의 thematic 유사도와 비교하여 confidence score을 결정한다. 식은 다음과 같다:

이후, article은 highest confidence score이 threshold를 넘으면 해당 story에 할당된다.

할당되지 못한 article 들은 다시 window를 탐색하며 새 story를 찾는다.

Scalable Processing with Story Summary

Story Summary

앞서 너무 많은 양의 article을 모두 보관하기보다 story들의 줄거리만 보관하는 방식을 사용한다고 언급한 적이 있다.

USTORY는 pane-based 주장으로부터 영향받은 pane-based story summary를 사용한다.

pane-based story summary (PSS)과 관련된 식은 다음과 같다:

USTORY는 PSS를 사용하여 시간적 theme을 인지하고, 동작 article과 story의 표현을 이전 글에 대한 조회 없이 끌어낸다.

Efficiency Analysis

또, PSS를 사용함으로써, article이 story에 할당된 후에 제거되기 위해서는 다시 PSS만 쓰인다.

---

Conclusion

해당 논문은 뉴스 스트림으로부터 비지도 온라인 스토리 발굴을 가능하게 하는 scalable 프레임워크인 USTORY를 제안한다.

USTORY는 thematic embedding과 pre-trained 문장 인코더라는 새로운 아이디어를 도입하고, compact한 스토리 summary를 다루는 최신식 적응적 clustering을 사용한다.

 

이는 실제 뉴스 데이터로 실험한 결과 굉장한 성능을 보여주었다.