Использование Beam Search на графике для создания предложения с наибольшим количеством баллов - PullRequest
Новая
       3

Использование Beam Search на графике для создания предложения с наибольшим количеством баллов

0 голосов
/ 30 января 2020

Я работаю с графиком, который я извлек из длинной статьи. Направленный взвешенный граф, который на самом деле является не чем иным, как словарем, содержит заголовочные слова в виде вершин, которые связаны через ребра с каждым словом (хвостовыми словами), которое следует за этим словом в статье. Таким образом, если слово «желтый» встречается в статье 3 раза, а за ним следуют слова «кирпич», «кирпич» и «подводная лодка», то «желтая» запись будет представлена ​​следующим образом на графике: 

{"yellow": ["brick", "brick", "submarine"]}

Этот график был создан с использованием класса python, который я написал под названием ExtractedGraph, который помимо метода __init__, который выполняет работу по генерации графа, имеет метод getProb(self, head_word, tail_word), который принимает в качестве входных данных ключевое слово и хвостовое слово и выводит вероятность того, что ключевое слово будет следовать за хвостовым словом, которое является весом ребра, соединяющего узел главного слова и узел конечного слова. Итак, если мы введем «желтый» и «кирпичный», результат будет 2/3.

Мой вопрос заключается в том, как можно выполнить поиск луча на этом графике, чтобы найти предложение с максимальным баллом. В частности, что, если входными данными для функции поиска луча была строка prefix_words, beam_width int и sen_length int (максимальная длина слова предложения). Как будет выглядеть алгоритм? После прочтения об алгоритме Beam Search в Интернете и просмотра многочисленных учебных пособий я не уверен, как будет работать функция Beam Search в этом конкретном сценарии c.

1 Ответ

1 голос
/ 30 января 2020

Допустим, graph_nodes - это словарь, и каждое предложение должно начинаться с символа <s> с вероятностью 1,0, а все предложения должны заканчиваться специальным символом </s>. Чтобы избежать сортировки гипотез, я держу их в куче, поэтому добавление элемента является постоянным. 

import heapq

beam = [(1.0, ["<s>"])]
for _ in range(sen_length):
    new_beam = []
    for score, hypothesis in beam:
        hypothesis_end = hypothesis[-1]

        # finished hypothesis will return to the beam and compete with new ones
        if hypothesis_end == "</s>":
            heapq.heappush(new_beam, (score, hypothesis))
            if len(new_beam) > beam_width:
                heapq.heappop(new_beam)

        # expand unfinished hypothesis
        for possible_continuation in graph_nodes[hypothesis_end]:
            continuation_score = score * get_prob(hypothesis_end, possible_continuation)
            heapq.heappush(
                new_beam, (continuation_score, hypothesis + [possible_continuation])
            if len(new_beam) > beam_width:
                heapq.heappop(new_beam)
    beam = new_beam

Если ваши гипотезы могут иметь разную длину, вам следует рассмотреть некоторую нормализацию длины (например, геометрию c среднее из вероятностей). Кроме того, вероятности умножения не всегда могут быть численно стабильными, поэтому вы можете использовать вместо них суммы логарифмов.

...