Natural language processing with Python 이라는 책을 보다가 3.8절에 Word segmentation 프로그램을 simulated annealing 방법으로 예제를 올려 놓았길래.. 호기심이 발동해 이것을 유전(Genetic) 알고리즘으로 해찾기를 코드를 작성해 봤다.
“doyouseethekittyseethedoggydoyoulikethekittylikethedoggy”
위 문자열을 제대로 자른다면…
“do you see the kitty see the doggy do you like the kitty like the doggy”
뭐 이런식으로 될 것이다.
이런 세그먼트를 표현하기 위해 0과 1로만 표현된 세그먼트 문자열을 활용한다.
예를 들어 “[‘doyou’, ‘seeth’, ‘ekitty’, ‘seeth’, ‘edoggy’, ‘doyou’, ‘liketh’, ‘ekitty’, ‘liketh’, ‘edoggy’]”
이런 식으로 잘린다면…
0000100001000001000010000010000100000100000100000100000
위와 같은 문자열로 표현을 할 수 있을 것이다.
이를 정확하게 세그먼트 하려면 사전이나 여타 데이터가 필요할지 모르나, 이 예제는 간단한 목적함수를 활용해 목적함수에서 가장 최소값을 가지는 세그먼트를 추출하게 된다.
목적함수는 “렉시컨(lexicon) 사이즈와 + 단어 개수”로 표현 되는데, 이 값이 최소가 되어야 좋은 세그먼트라고 할 수 있다.
자세한 내용은 구글에 공개된 책 페이지를 참고하기 바란다.
사용한 유전알고리즘의 경우 n개만큼 정답 후보군들을 생성하고 이들간의 교배와 변이를 반복하면서 이들중에 가장 목적함수를 만족시키는 놈을 찾아내는 방법이다. 내 경우에는 과도한 변이를 줄이고, 선택압력(selection pressure)를 높이는 방향으로 튜닝을 하고 나서 가장 빠르게 목적함수를 만족시켜 나가는 것을 볼 수 있었다. 여기서 선택 압력은 교배나 부모 선택시 목적함수를 만족시키는 놈의 유전자가 선택될 확률을 높여주는 것을 의미한다. 이 부분을 과도하게 높이면 자식들이 다양한 유전자를 가지는 것을 방해하고 오직 우수하나 비슷한 자식들만 만들어 내는 결과를 보게 된다. 따라서 지역 최소점(local minima)에 빠질 가능성이 커지게 된다.
시뮬레이티드 어닐링 방법도 그렇지만 유전 알고리즘도 위의 문자열로는 42가 한계이다. 하지만 둘다 초기값으로 랜덤 세그먼트가 입력되었을 경우 많은 경우 유전 알고리즘의 해 수렴 속도가 더 빠른걸 알 수 있었다. 하지만 이것도 역시 해결해야 될 문제가 어떤것이느냐에 따라 알고리즘의 장단점은 부각이 될거라 생각해 본다.
아래는 코드이다.
#!/usr/bin/python
# coding=utf-8
import random
def segment(text, segs):
words = []
last = 0
for i in range(len(segs)):
if segs[i] == '1':
words.append(text[last:i+1])
last = i + 1
words.append(text[last:])
return words
def evaluate(text, segs):
words = segment(text, segs)
text_size = len(words)
lexicon_size = len(' '.join(list(set(words))))
return text_size + lexicon_size
def flip(segs, pos):
return segs[:pos] + str(1-int(segs[pos])) + segs[pos+1:]
def flip_n(segs, n):
for i in range(n):
segs = flip(segs, random.randint(0,len(segs)-1))
return segs
def anneal(text, segs, iterations, cooling_rate):
temperature = float(len(segs))
while temperature > 0.5:
best_segs, best = segs, evaluate(text, segs)
for i in range(iterations):
guess = flip_n(segs, int(round(temperature)))
score = evaluate(text, guess)
if score < best:
best, best_segs = score, guess
score, segs = best, best_segs
#print "temp : " + str(temperature)
temperature = temperature / cooling_rate
print "%s\t%d\t%s" % (segs, evaluate(text, segs), segment(text, segs))
## genetic algorithm ##
def initSegs(numSegs, n):
segsList = []
for j in range(numSegs):
seg = [str(random.randint(0, 1)) for i in range(n)]
segsList.append("".join(seg))
return segsList
from math import pow
def goodness(scores, param):
"rank-based method"
goodnessScores = [(seg, score, param * pow(1.0 - param, i))
for i, (seg, score) in enumerate(scores)]
sumofGoodness = sum([goodness for (_seg_, _score_, goodness) in goodnessScores])
normGoodnessScores = [(seg, score, goodnessScore/sumofGoodness)
for (seg, score, goodnessScore) in goodnessScores]
return normGoodnessScores
def selectFather(goodnessScores, param):
"Tournament"
parent1idx = random.randint(0, len(goodnessScores) - 1)
parent2idx = random.randint(0, len(goodnessScores) - 1)
parentCand1 = goodnessScores[parent1idx]
parentCand2 = goodnessScores[parent2idx]
r = random.random()
if r < param:
return max([parentCand1, parentCand2], key=lambda x:x[2])
else:
return min([parentCand1, parentCand2], key=lambda x:x[2])
def getParent(goodnessScores):
father = selectFather(goodnessScores, 0.9)
mother = selectFather(goodnessScores, 0.9)
return (father[0], mother[0])
def crossover(father, mother, param):
assert(len(father) == len(mother))
probs = [random.random() for i in range(len(father))]
child = []
for i, prob in enumerate(probs):
if prob >= param:
child.append(father[i])
else:
child.append(mother[i])
return "".join(child)
def mutation(child, param):
mutated = []
for c in child:
if random.random() < param:
mutated.append(str(1 - int(c)))
else:
mutated.append(c)
return "".join(mutated)
def genetic(text, numSegs, numLoop):
segs = initSegs(numSegs, len(text) - 1)
scores = [(seg, evaluate(text, seg)) for seg in segs]
scores.sort(lambda x,y:cmp(x[1], y[1]))
superSeg = scores[0]
print "%s\t%d\t%s" % (superSeg[0], superSeg[1] ,segment(text,superSeg[0]))
while(numLoop > 0):
#print "num Loop : " + str(numLoop)
goodnessScores = goodness(scores, 0.8)
scoredChilds = []
for i in range(numSegs):
father, mother = getParent(goodnessScores)
evalFat = evaluate(text, father)
evalMot = evaluate(text, mother)
crossoverProb = evalFat/(evalFat + evalMot)
child = crossover(father, mother, crossoverProb)
mutatedChild = mutation(child, 0.01)
scoredChild = (mutatedChild, evaluate(text, mutatedChild))
scoredChilds.append(scoredChild)
scores = scoredChilds
scores.sort(lambda x,y:cmp(x[1], y[1]))
superChild = scores[0]
if superChild[1] < superSeg[1]:
superSeg = superChild
print "%s\t%d\t%s" % (superSeg[0], superSeg[1] ,segment(text,superSeg[0]))
numLoop -= 1
return superSeg
Text = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"
seg0 = "0000000000000000000000000000000000000000000000000000000"
seg1 = "0000000000000001000000000010000000000000000100000000000"
seg2 = "0100100100100001001001000010100100010010000100010010000"
seg3 = "0000100100000011001000000110000100010000001100010000001"
rndseg = "".join([str(random.randint(0, 1)) for i in range(len(Text) - 1)])
if __name__ == "__main__":
#print segment(text, seg3)
print "-------Starting Annealing------------"
anneal(Text, rndseg, 5000, 1.2)
print "\n-------Starting Genetic ------------"
genetic(Text, 100, 5000)
Word Segmentation by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.