Submodular function이란?
고양이에 대한 지식이 전무한 사람이 (고양이의 존재자체도 몰랐던 사람이라 가정하자.) 고양이에 대해 학습하기 위해서, 고양이에 관련된 이미지들을 배우는 상황이라고 가정하자.
고양이 이미지 set A는 {고양이_이미지_1.jpg, 고양이_이미지_2.jpg} 로 주어졌을때에 사람이 배울 수 있는 정보량을 F(A)라고 하자.
임의의 고양이 이미지 s (A에 속하지 않은) = 고양이_이미지_star.jpg 를 A에 추가했을때의 정보량은,
F(A U s)로 나타내진다.
즉, s를 A에 추가함으로써 얻을 수있는 정보량의 이득 (marginal gain) 은 F(A U s) - F(A)이다.
Diminishing return property: 만약 A를 포괄하는 더 큰 set B {고양이_이미지_1.jpg, 고양이_이미지_2.jpg, ..., 고양이_이미지_10000.jpg} 가 있다고 가정하면, B에 s를 추가하여 얻을 수 있는 정보량의 이득은, A에 s를 추가함으로써 얻을 수 있는 정보량의 이득보다 훨씬 낮을 것이다.
즉, 어떤 set의 원소개수가 늘어나면 늘어날수록, 그로인해 얻을 수 있는 marginal gain (e.g. 정보량의 이득)은 줄어드는 게 diminishing return property 이다. 만약 어떤 set function F가 요 성질을 만족한다면, submodular set function이라고 볼 수 있다.
예시 그림은 아래와 같다.
출처: https://www.youtube.com/watch?v=Y3u_hvxayDY, from Stefanie Jegelka (MIT)
댓글
댓글 쓰기