Что такое цепь Маркова?
Алгоритм недели — цепь Маркова. Используя эту технику, вы используете небольшую вероятность для легкого машинного обучения. В этом случае введите песню и попросите компьютер создать оригинальную работу на основе шаблонов, которым вы ее научили.
Я приложил образец песни. Дай послушать. Я думаю, вы будете несколько удивлены, что это полностью сгенерированная компьютером песня. Только немного … это не очень хорошо, но это определенно не предсказуемо и, тем не менее, не является шумом.
Нажмите здесь, чтобы открыть пример в виде файла .wav
Как ты это сделал ?!
Существует довольно простая техника информатики, известная как «цепь Маркова». Не позволяйте всей ссылке на информатику обмануть вас, это действительно не сложно понять. По сути, я создал таблицу чисел, которая отвечает на следующий вопрос: Когда играла нота X, в каком процентном соотношении остальные ноты игрались дальше? Так что просто представьте таблицу со всеми нотами от a до g #, расположенными сверху (это ноты, которые мы в последний раз играли), а вертикальная ось — это все те же ноты, но эта ось представляет вероятность того, что эта конкретная нота была сыграна следующей ,
Вот пример того, что генерирует моя программа:
a a# b c c# d d# e f f# g g# a [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], a# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], b [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], c [0, 0, 0, 6, 0, 1, 0, 0, 0, 0, 2, 0], c# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], d [0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0], d# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], e [0, 0, 0, 1, 0, 2, 0, 3, 1, 0, 0, 0], e# [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0], f [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], f# [0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 2, 0], g [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], g# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
Это называется «списком смежности». Я наполнил его музыкой для Twinkle Twinkle. Давайте ответим на вопрос, используя его. Как часто при игре на ноте C мы играем еще одну ноту C?
Сначала мы ищем C в левом столбце и следуем по строке до столбца, помеченного C. Мы получаем ответ 6. Чтобы выяснить, как часто мы играем в C, учитывая, что мы только что играли в C, хотя нам нужно знать, сколько раз мы сначала сыграл ноту до Суммирование всех значений в строке дает нам 9. Таким образом, 6/9 (или 2/3) игры ноты C приведут к тому, что мы сыграем еще одну ноту C.
Вот таблица времени (1, 1/2, 1/4, 1/8, 1/16 примечания):
1 2 4 8 16 1 [0, 0, 0, 0, 0], 2 [0, 0, 0, 1, 0], 4 [0, 0, 3, 5, 0], 8 [0, 2, 4, 11, 0], 16 [0, 0, 0, 0, 0]
Но это все, это магия, которая управляет всем процессом. Как видите, я на самом деле не храню проценты, а просто подсчет количества раз, когда заметка приводила к другой заметке. В итоге получается то же самое.
Код
Конечно, нам нужно увидеть код! Как обычно, я начну с самого высокого уровня и углублюсь в него более подробно.
Эта часть кода записывает ноты для «Twinkle, Twinkle» в создателя музыки, который я создаю. Тогда я говорю это, чтобы дать мне 100 примечаний, основанных на том, что это изучено:
class MusicMatrix:
def __init__(self):
self._previous_note = None
self._markov = MarkovBuilder(["a", "a#", "b", "c", "c#", "d", "d#", "e", "f", "f#", "g", "g#"])
self._timings = MarkovBuilder([1, 2, 4, 8, 16])
def add(self, to_note):
"""Add a path from a note to another note. Re-adding a path between notes will increase the associated weight."""
if(self._previous_note is None):
self._previous_note = to_note
return
from_note = self._previous_note
self._markov.add(from_note[0], to_note[0])
self._timings.add(from_note[1], to_note[1])
self._previous_note = to_note
def next_note(self, from_note):
return [self._markov.next_value(from_note[0]), self._timings.next_value(from_note[1])]
# Playing it comes next 🙂
#test = [['c',4], ['e',4], ['g',4], ['c5',1]]
#pysynth.make_wav(test, fn = "test.wav")
musicLearner = MusicMatrix()
# Input the melody of Row, Row, Row Your Boat
# The MusicMatrix will automatically use this to
# model our own song after it.
musicLearner.add(["c", 4])
musicLearner.add(["c", 4])
musicLearner.add(["c", 4])
musicLearner.add(["d", 8])
musicLearner.add(["e", 4])
musicLearner.add(["e", 4])
musicLearner.add(["d", 8])
musicLearner.add(["e", 4])
musicLearner.add(["f", 8])
musicLearner.add(["g", 2])
musicLearner.add(["c", 8])
musicLearner.add(["c", 8])
musicLearner.add(["c", 8])
musicLearner.add(["g", 8])
musicLearner.add(["g", 8])
musicLearner.add(["g", 8])
musicLearner.add(["e", 8])
musicLearner.add(["e", 8])
musicLearner.add(["e", 8])
musicLearner.add(["c", 8])
musicLearner.add(["c", 8])
musicLearner.add(["c", 8])
musicLearner.add(["g", 4])
musicLearner.add(["f", 8])
musicLearner.add(["e", 4])
musicLearner.add(["d", 8])
musicLearner.add(["c", 2])
random_score = []
current_note = ["c", 4]
for i in range(0,100):
print current_note[0] + ", " + str(current_note[1])
current_note = musicLearner.next_note(current_note)
random_score.append(current_note)
pysynth.make_wav(random_score, fn = "first_score.wav")
MarkovBuilder — то, где алгоритм скрывается. Обратите внимание, как MusicMatrix отслеживает предыдущую заметку для нас? MarkovBuilder должен быть четко указан, какие примечания связаны с какими.
import random
class MarkovBuilder:
def __init__(self, value_list):
self._values_added = 0
self._reverse_value_lookup = value_list
self._value_lookup = {}
for i in range(0, len(value_list)):
self._value_lookup[value_list[i]] = i
# Initialize our adjacency matrix with the initial
# probabilities for note transitions.
self._matrix=[[0 for x in range(0,len(value_list))] for i in range(0,len(value_list))]
def add(self, from_value, to_value):
"""Add a path from a note to another note. Re-adding a path between notes will increase the associated weight."""
value = self._value_lookup
self._matrix[value[from_value]][value[to_value]] += 1
self._values_added = self._values_added + 1
def next_value(self, from_value):
value = self._value_lookup[from_value]
value_counts = self._matrix[value]
value_index = self.randomly_choose(value_counts)
if(value_index < 0):
raise RuntimeError, "Non-existent value selected."
else:
return self._reverse_value_lookup[value_index]
def randomly_choose(self, choice_counts):
"""Given an array of counts, returns the index that was randomly chosen"""
counted_sum = 0
count_sum = sum(choice_counts)
selected_count = random.randrange(1, count_sum + 1)
for index in range(0, len(choice_counts)):
counted_sum += choice_counts[index]
if(counted_sum >= selected_count):
return index
raise RuntimeError, "Impossible value selection made. BAD!"
Опять же, единственная причина существования этого класса состоит в том, чтобы отслеживать, как одно значение, которое мы ему даем, приводит к другому, и это облегчает выбор значений, чтобы дать нам информацию о том, что произошло в прошлом. Важно отметить, что мы не просто выбираем значение, которое произошло больше всего. Если бы мы это сделали, это сделало бы нашу программу менее интересной. Вместо этого мы используем функцию randomly_choose для взвешивания следующего значения (очень похоже на теорему Байеса для тех, кто интересуется вами).
Grok’d
Подводя итог, моя программа смогла сгенерировать музыку, потому что я дал ей образец музыкальной партитуры, и она выяснила, какой процент времени ноты переменного тока приводил к другой ноте. Вот пошаговый прогон:
- Дайте программе записку и сроки. — Когда я даю ему вторую заметку / время, в таблице отмечается, что первая заметка однажды привела ко второй ноте. Он также отмечает, что первый тайминг привел ко второму таймингу один раз. (заметьте, я не пытаюсь связать заметки / время, это не удивительно).
- Введите третью заметку. — Затем программа отмечает в своей таблице, что 2-я нота однажды привела к 3-й ноте. — Продолжить до начала работы. Так мы настроили систему. Далее, вот как мы заставляем программу создавать собственную песню:
- Выберите случайную заметку / время начала. — Попросите компьютер подсказать, какая хорошая нота / время будет следовать за ними. — распечатайте заметку / время (в случае, если это работа гения;)
- проиграйте каждую ноту, используя библиотеку python, которую я использую, pysynth.
Вот ссылка на мое git-репо со всем моим кодом на Python: http://github.com/jcbozonier/MarkovMusic/tree/master
На этом пока все!
Отказ от ответственности: Мнения, выраженные здесь, представляют мое собственное, а не мнение моего работодателя.