Я хотел бы показать вам простое применение алгоритма цепи Маркова - генерацию случайных текстов на основе реального корпуса. Читатели, незнакомые с цепями Маркова, могут найти много исследований по этой теме в Интернете или прочитать мою эту статью.
Каждый текстовый генератор, основанный на цепи Маркова, требует некоторого начального корпуса - как и в машинном обучении, мы сначала «обучаем» наш алгоритм, предоставляя ему набор данных. Чтобы продемонстрировать, как для этого можно использовать простейшую цепочку первого порядка, я буду использовать «Улисс» Джеймса Джойса, классический и хорошо известный пример техники «потока сознания».
Строительная матрица
С точки зрения теории вероятностей, мы можем рассматривать исходный корпус как систему, описываемую матрицей вероятностей перехода, в которой каждое слово является состоянием. Количество строк и столбцов в такой матрице равно количеству уникальных символов, содержащихся в предварительно отфильтрованном тексте. Давайте посмотрим на матричное представление короткого предложения с 4 уникальными словами:
Мы можем видеть, что, например, за словом номер 3 никогда не следует слово номер 1, но с неравной вероятностью за ним могут следовать слова 3 и 4. Построение представления матрицы вероятностей на основе заданного корпуса - это первое, что у нас есть делать. Для этого мы пройдемся по тексту и создадим словарь для каждого уникального слова, где его ключом будет слово, а его значение будет содержать другие словари: ключ каждого внутреннего словаря - это любое слово, которое следует за данным словом и значением. - количество раз, когда второе слово встречается после первого. Это может показаться сложным, поэтому вот некоторое «визуальное представление» структуры:
[uniqueKey: [uniqueKey: значение]]
Я написал настраиваемую коллекцию хешируемых элементов на основе словаря, чтобы иметь возможность быстро хранить и получать доступ к уникальным элементам, поэтому окончательная структура данных будет Словарь ‹Подстрока, Происхождение ‹Подстрока›. Ниже приведена часть кода структуры (остальную часть можно найти на моем GitHub), которая добавляет уникальные элементы вместе с их количеством в коллекцию:
struct Occurrence <Element: Hashable> {
private var contents: [Element : Int] = [:]
init() {}
mutating func add(_ substring: Element, occurrences: Int = 1) {
if let currentCount = contents[substring] {
contents[substring] = currentCount + occurrences
} else {
contents[substring] = occurrences
}
}
...
}
Моя реализация генератора содержит 3 класса: CorpusParses, CorpusAnalyser и TextGenerator. Я не буду делиться кодом, который обрабатывает синтаксический анализ, а вместо этого объясню функцию построения матрицы CorpusAnalyser:
func buildMatrix(completion: (_ matrix: Dictionary<Substring, Occurrence<Substring>>) -> Void) {
guard let strings = self.parser.parse(fileName: self.corpusName) else {
return
}
var occurrences = Dictionary<Substring, Occurrence<Substring>>()
for (index, substring) in strings.enumerated() {
var chain = Occurrence<Substring>()
if let value = occurrences[substring] {
chain = value
}
if strings.indices.contains(index + 1) {
chain.add(strings[index + 1], occurrences: 1)
occurrences[substring] = chain
}
}
completion(occurrences)
}
Подстрока - это объект, который представляет собой часть строки. Я использовал его для представления слова в корпусе, которое предварительно было отфильтровано и разбито на массив подстрок. Вышеупомянутая функция выполняет итерацию по подстрокам и, если есть элемент, следующий за текущим, добавляет его в словарь результатов, также увеличивая вхождение на 1. Если слово уже можно найти в словаре, новую цепочку можно заменить существующей. . По окончании итерации вызывается блок завершения. Вот одно из значений в данных результата:
«medium»: MarkovChain.Occurrence ‹Swift.Substring› (содержимое: [«and»: 1, «steers»: 1, «in»: 1])
Как видите, в тексте после ключа 3 слова. Они перечислены как словарь и с такой же вероятностью появятся после слова «medium».
Подведем итоги алгоритма:
- Прочтите слово из файла.
- Проверьте, есть ли он уже в словаре.
- Если это не так, добавьте новую пару "ключ-значение".
- Если он есть, замените существующую пару "ключ-значение" на текущую.
- Проверьте, не является ли слово последним в файле.
- Если это не так, добавьте значение пары ключей со словом, которое следует за текущим словом, в качестве ключа и «1» в качестве значения.
- Повторите для каждого слова в файле.
Знать, является ли текущее слово последним в файле (или в предложении), не всегда требуется, это зависит от того, чего мы хотим достичь. Например, мы можем пометить слова, за которыми следует "." и используйте их, чтобы закончить предложение или текст.
Что дальше? Если все вероятности известны, мы, наконец, можем начать генерировать тексты. Очевидно, что нам нужно читать значения для каждого слова в цепочке, но выбор следующего слова может быть выполнен двумя разными способами, перечисленными в Selection enum:
enum Selection {
case random
case weighted
}
Да, мы можем сделать это простым способом и просто взять случайное слово из словаря, и это даже поможет в некоторых конкретных случаях, но гораздо разумнее учитывать вес каждого слова (помните, что с точки зрения графов вероятностей, вес просто означает вероятность перехода в указанное состояние из текущего). Для этого нам нужно решить типичную задачу генерации случайных значений с заданным распределением вероятностей.
Для генерации псевдослучайных значений может потребоваться отдельная статья, но одно из самых простых решений было хорошо объяснено Питером Келли здесь. Вот так финальная версия генератора:
func nextWord(matrix: Dictionary<Substring, Occurrence<Substring>>, currentWord: Substring, selection: Selection) -> Substring? {
if let probabilities = matrix[currentWord] {
switch selection {
case .random:
if let next = probabilities.map({ $0.0 }).randomItem(){
return next
}
case .weighted:
return weightedRandom(probabilities)!
}
}
return nil
}
}
private func weightedRandom(_ probabilities: Occurrence<Substring>) -> Substring? {
let totalSum = probabilities.map({ $0.1 }).reduce(0, +)
var pseudoRandom = Int(arc4random_uniform(UInt32(totalSum)))
let weights = probabilities.map({ $0.1 })
for i in 0...probabilities.count {
pseudoRandom -= weights[i]
if pseudoRandom <= 0 {
guard let next = probabilities.filter({ $1 == pseudoRandom }).map({ $0.0 }).randomItem() else {
return nil
}
return next
}
}
return nil
}
Функция randomItem () - это простое расширение массива:
extension Array {
func randomItem() -> Element? {
if isEmpty { return nil }
let index = Int(arc4random_uniform(UInt32(self.count)))
return self[index]
}
}
Алгоритм построения текста, начинающегося с заданного слова:
- Проверяем, содержит ли матрица текущее слово, если его нет, возвращаем nil.
- Если ключ был найден, выберите следующее слово одним из способов.
- Чтобы получить случайное слово из вероятностей, отобразите вероятности в массив и верните из него случайную подстроку.
- Чтобы сделать выбор на основе вероятности, сгенерируйте случайное значение на основе суммы значений в словаре вероятностей. После этого вычтите значение на вес каждого слова. Если результат меньше или равен 0, отфильтруйте словарь, чтобы он содержал только ключи с результатом вычитания в качестве значения, сопоставьте его с массивом и снова верните случайный элемент.
Код TextGenerator:
class TextGenerator {
var corpus: String
init(_ corpusName: String) {
self.corpus = corpusName
}
func buildText(length: Int, start: String, generator: Selection) {
let analyser = CorpusAnalyser(corpusName: self.corpus)
analyser.buildMatrix { ( result ) in
var initial = Substring(start)
var text = String(start)
for _ in 0...length {
if let next = analyser.nextWord(matrix: result, currentWord: initial, selection: generator) {
text.append(String(" \(next)"))
initial = next
}
}
print("\(text).")
}
}
}
И все, что осталось, это указать файл, слово, с которого нужно начинать, и длину текста:
let generator = TextGenerator("ulysses")
generator.buildText(length: 200, start: "Ulysses", generator: .random)
Проблемы с производительностью
К сожалению, реализация Swift работает не так быстро, как хотелось бы. Профилирование с помощью инструментов показало, что функция buildMatrix () потребляет 90% ресурсов ЦП плюс много памяти и требует около 5 секунд на выполнение из-за размера файла. Судя по всему, словари Swift еще недостаточно оптимизированы, потому что аналогичный код на Java работает намного быстрее. Я пытаюсь найти способ оптимизировать код. Друзья-программисты, я рекомендую вам попробовать реализовать текстовые генераторы на основе цепей Маркова на других языках!
Веселиться
Я намеренно использовал «Улисс» как корпус. Читатели, знакомые с литературой о потоке сознания, могут обнаружить, что даже цепочка первого порядка порождает тексты, которые забавно похожи на исходный:
Улисс Браун безрассудства, лжи, обнаженного, скованного, в чулке: помятый, блестящий черный с уликами предоставил отличные возможности для другого, перерыв рядом с ним теперь захватил его. За жировыми складками скрывается потенциал пакетов, покрытых свинцовой бумагой: отборная смесь, сделанная известна. Звонили уверения, что если мы повернем направо. Что-то вроде всплытия, уменьшения блюдца для завтрака, хотя и не обращая внимания на компании с ограниченной ответственностью, заместители председателя совета директоров щебетали яркого безмолвного свидетеля и спешили на трезвую голову и в зеркале уходили, поспешно шагая, и духи, которые хотели бы разгласить высоту над мистером Кернаном, огромными напитками мистера Каннингема. клятва, он закрепил занятие, слишком непослушный тоже? О, я очень взволновал его грог. - Привет, Блум! Вы оба чемпионы.
