Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию

Мы продолжаем публиковать разборы задач, которые предлагались на недавнем чемпионате. На очереди — задачи, взятые из квалификационного раунда для специалистов по машинному обучению. Это третий трек из четырёх (бэкенд, фронтенд, ML, аналитика). Участникам нужно было сделать модель исправления опечаток в текстах, предложить стратегию игры на игровых автоматах, довести до ума систему рекомендаций контента и составить ещё несколько программ.

A. Опечатки

Условие

(эпиграф)(с одного форума)
— Кто сочинил эту чушь?
— Астрофизики. Они тоже люди.
— Вы 10 ошибок в слове «журналисты» сделали.

Многие пользователи делают ошибки при наборе, некоторые — из-за попаданий мимо клавиш, некоторые — из-за своей неграмотности. Мы хотим проверить, мог ли пользователь на самом деле иметь в виду некоторое другое слово, чем то, которое он набрал.

Более формально, предположим, что имеет место следующая модель ошибок: пользователь начинает с некоторого слова, которое он хочет написать, и дальше последовательно делает в нём некоторое количество ошибок. Каждая ошибка представляет собой замену некоторой подстроки слова на другую подстроку. Одна ошибка соответствует замене только в одной позиции (то есть если пользователь захочет сделать единственную ошибку по правилу «abc»→«cba», то из строки «abcabc» он может получить либо «cbaabc», либо «abccba»). После каждой ошибки процесс повторяется. Одно и то же правило могло использоваться несколько раз в различных шагах (так, в вышеприведённом примере за два шага могло получиться «cbacba»).

Требуется определить, какое минимальное количество ошибок пользователь мог совершить, если он имел в виду одно заданное слово, а написал другое.

Решение

Попробуем сгенерировать из правильного написания все возможные слова не более чем с 4 ошибками. Их в худшем случае может быть O((L﹒N)⁴). В ограничениях задачи это довольно большое число, поэтому нужно придумать, как уменьшить сложность. Можно вместо этого воспользоваться алгоритмом meet-in-the-middle: сгенерировать слова не более чем c 2 ошибками, а также слова, из которых можно получить написанное пользователем слово, сделав не более 2 ошибок. Заметим, что размер каждого из этих множеств не будет превышать 10⁶. Если количество сделанных пользователем ошибок не превосходит 4, то эти множества будут пересекаться. Аналогично можно проверить, что число ошибок не превосходит 3, 2 и 1.

struct FromTo {
	std::string from;
	std::string to;
};

std::pair<size_t, std::string> applyRule(const std::string& word, const FromTo &fromTo, int pos) {		
	while(true) {
		int from = word.find(fromTo.from, pos);
		if (from == std::string::npos) {
			return {std::string::npos, {}};
		}
		int to = from + fromTo.from.size();
		auto cpy = word;
		for (int i = from; i < to; i++) {
			cpy[i] = fromTo.to[i - from];
		}
		return {from, std::move(cpy)};
	}
}

void inverseRules(std::vector<FromTo> &rules) {
	for (auto& rule: rules) {
		std::swap(rule.from, rule.to);
	}
}

int solve(std::string& wordOrig, std::string& wordMissprinted, std::vector<FromTo>& replaces) {
	std::unordered_map<std::string, int> mapping;
	std::unordered_map<int, std::string> mappingInverse;
	
	mapping.emplace(wordOrig, 0);
	mappingInverse.emplace(0, wordOrig);

	mapping.emplace(wordMissprinted, 1);
	mappingInverse.emplace(1, wordMissprinted);

	std::unordered_map<int, std::unordered_set<int>> edges;

	auto buildGraph = [&edges, &mapping, &mappingInverse](int startId, const std::vector<FromTo>& replaces, bool dir) {
		std::unordered_set<int> mappingLayer0;	
		mappingLayer0 = {startId};

		for (int i = 0; i < 2; i++) {
			std::unordered_set<int> mappingLayer1;			
			for (const auto& v: mappingLayer0) {
				auto& word = mappingInverse.at(v);
				for (auto& fromTo: replaces) {			
					size_t from = 0;
					while (true) {
						auto [tmp, wordCpy] = applyRule(word, fromTo, from);						
						if (tmp == std::string::npos) {
							break;
						}
						from = tmp + 1;					
						{
							int w = mapping.size();
							mapping.emplace(wordCpy, w);
							w = mapping.at(wordCpy);
							mappingInverse.emplace(w, std::move(wordCpy));
							if (dir) {
								edges[v].emplace(w);
							} else {
								edges[w].emplace(v);
							}
							mappingLayer1.emplace(w);
						}
					}
				}
			}
			mappingLayer0 = std::move(mappingLayer1);
		}
	};

	buildGraph(0, replaces, true);
	inverseRules(replaces);
	buildGraph(1, replaces, false);

	{
		std::queue<std::pair<int, int>> q;
		q.emplace(0, 0);
		std::vector<bool> mask(mapping.size(), false);
		int level{0};

		while (q.size()) {
			auto [w, level] = q.front();
			q.pop();
			if (mask[w]) {
				continue;
			}
			mask[w] = true;

			if (mappingInverse.at(w) == wordMissprinted) {
				return level;
			}

			for (auto& v: edges[w]) {
				q.emplace(v, level + 1);
			}
		}
	}

	return -1;
}

B. Многорукий бандит

Условие

Это интерактивная задача.

Вы сами не знаете как так вышло, но вы обнаружили себя в зале с игровыми автоматами с целым мешком жетонов. К сожалению, в кассе жетоны назад принимать отказываются, и вы решили испытать свою удачу. В зале есть много автоматов, в которые вы можете играть. Для одной игры с автоматом вы используете один жетон. В случае выигрыша автомат даёт вам один доллар, в случае проигрыша — ничего. У каждого автомата есть фиксированная вероятность выигрыша (которую вы не знаете), но у разных автоматов она разная. Изучив сайт производителя этих автоматов, вы выяснили, что вероятность выигрыша у каждого автомата выбирается случайно на этапе изготовления из бета-распределения с определёнными параметрами.

Вам хочется максимизировать свой ожидаемый выигрыш.

Решение

Эта задача достаточно известна, её можно было решать по-разному. Основное решение жюри реализовывало стратегию Thompson sampling, но поскольку число шагов было известно в начале работы программы, существуют и более оптимальные стратегии (например, UCB1). Более того, можно было даже обойтись epsilon-greedy-стратегией: с некоторой вероятностью ε играть в случайный автомат и с вероятностью (1 – ε) играть в автомат, у которого статистика побед лучше всего.

class SolverFromStdIn(object):
    def __init__(self):
        self.regrets = [0.]
        self.total_win = [0.]
        self.moves = []


class ThompsonSampling(SolverFromStdIn):
    def __init__(self, bandits_total, init_a=1, init_b=1):
        """
        init_a (int): initial value of a in Beta(a, b).
        init_b (int): initial value of b in Beta(a, b).
        """

        SolverFromStdIn.__init__(self)
        self.n = bandits_total

        self.alpha = init_a
        self.beta = init_b

        self._as = [init_a] * self.n # [random.betavariate(self.alpha, self.beta) for _ in range(self.n)]
        self._bs = [init_b] * self.n # [random.betavariate(self.alpha, self.beta) for _ in range(self.n)]
        self.last_move = -1
        random.seed(int(time.time()))

    def move(self):
        samples = [random.betavariate(self._as[x], self._bs[x]) for x in range(self.n)]
        self.last_move = max(range(self.n), key=lambda x: samples[x])

        self.moves.append(self.last_move)
        return self.last_move

    def set_reward(self, reward):
        i = self.last_move
        r = reward

        self._as[i] += r
        self._bs[i] += (1 - r)        

        return i, r

while True:
    n, m = map(int, sys.stdin.readline().split())

    if n == 0 and m == 0:
        break
        
    alpha, beta = map(float, sys.stdin.readline().split())
    solver = ThompsonSampling(m)

    for _ in range(n):
        print >> sys.stdout, solver.move() + 1
        sys.stdout.flush()
        reward = int(sys.stdin.readline())
        solver.set_reward(reward)

C. Выравнивание предложений

Условие

Одна из важнейших задач для обучения хорошей модели машинного перевода — хороший корпус параллельных предложений. Обычно источником для параллельных предложений являются параллельные документы. Оказывается, часто для того, чтобы построить некоторый корпус параллельных предложений, не нужно знать ничего, кроме их длин. В частности, можно заметить, что чем длинее предложение на исходном языке, тем длинее, скорее всего, будет его перевод. Некоторая сложность состоит в том, что при переводе количество предложений в тексте может поменяться: иногда два соседних предложения при переводе могут быть объединены в одно, или наоборот — одно предложение могло быть разделено на два. В отдельных редких случаях предложения могут целиком пропускаться в переводе, или в переводе может появиться предложение, которого не было в оригинале.

Более формально, предположим, что верна следующая генеративная модель для параллельных корпусов. На каждом шаге мы совершаем одно из следующих действий:

1. Остановка

С вероятностью p_h генерация корпусов заканчивается.

2. [1-0] Пропуск предложения

С вероятностью p_d приписываем в оригинальный текст одно предложение. В перевод не приписываем ничего. Длина предложения на языке оригинала L ≥ 1 выбирается из дискретного распределения:

.

Здесь μ_s, σ_s — параметры распределения, а α_s — нормировочный коэффициент, выбираемый так, чтобы .

3. [0-1] Вставка предложения

С вероятностью p_i приписываем в перевод одно предложение. В оригинал не приписываем ничего. Длина предложения на языке перевода L ≥ 1 выбирается из дискретного распределения:

.

Здесь μ_t, σ_t — параметры распределения, а α_t — нормировочный коэффициент, выбираемый так, чтобы .

4. Перевод

С вероятностью (1 – p_d – p_i – p_h) берём длину предложения на языке оригинала L_s ≥ 1 из распределения p_s (с округлением вверх). Далее генерируем длину предложения на языке перевода L_t ≥ 1 из условного дискретного распределения:

.

Здесь α_st — нормировочный коэффициент, а остальные параметры описаны в предыдущих пунктах.

Далее происходит ещё один шаг:

1. [2-1] С вероятностью p_{split s} сгенерированное предложение на языке оригинала распадается на два непустых, так, чтобы суммарное количество слов увеличилось ровно на один. Вероятность того, что предложение длины L_s распадётся на части длиной L₁ и L₂ (то есть L₁ + L₂ = L_s + 1), пропорциональна P_s(L₁) ⋅ P_s(L₂).

2. [1-2] С вероятностью p_{split t} сгенерированное предложение на языке перевода распадается на два непустых, так, чтобы суммарное количество слов увеличилось ровно на один. Вероятность того, что предложение длины L_t распадётся на части длиной L1 и L2 (то есть L₁ + L₂ = L_t + 1), пропорциональна P_t(L₁) ⋅ P_t(L₂).

3. 3. [1-1] С вероятностью (1 – p_{split s} – p_{split t}) ни одно из пары сгенерированных предложений не распадётся.

Решение

Задача является частным случаем выравнивания с помощью скрытых марковских моделей (HMM alignment). Основная идея состоит в том, что можно вычислить вероятность генерации конкретной пары документов с помощью этой модели и алгоритма forward: в данном случае состоянием является пара префиксов документов. Соответственно, требуемую вероятность выравнивания конкретной пары параллельных предложений можно вычислить алгоритмом forward-backward.

D. Лента рекомендаций

Условие

Рассмотрим ленту рекомендаций разнородного контента. В ней смешаны объекты разного типа (картинки, видео, новости и т. д.). Эти объекты обычно упорядочиваются по релевантности пользователю: чем релевантнее (интереснее) объект пользователю, тем он ближе к началу списка рекомендаций. Однако при таком упорядочивании часто возникают ситуации, в которых в списке рекомендаций встречаются несколько объектов подряд одного типа. Это сильно ухудшает внешнее разнообразие наших рекомендаций и поэтому не нравится пользователям. Необходимо реализовать алгоритм, который по списку рекомендаций составит новый список, который будет лишен этой проблемы и будет наиболее релевантным.

Пусть задан исходный список рекомендаций a = [a₀, a₁,…, a_{n − 1}] длины n > 0. Объект под номером i имеет тип с номером b_i ∈ {0,…, m − 1}. Кроме того, объект под номер i имеет релевантность r(a_i) = 2_−i. Рассмотрим список, который получается из исходного выбором подмножества объектов и их перестановкой: x = [a_i0, a_i1,…,a_ik−1] длины k (0 ≤ k ≤ n). Список называется допустимым, если никакие два подряд идущих объекта в нём не совпадают по типу, т. е. b_ij ≠ b_{ij + 1} для всех j = 0,…, k−2. Релевантность списка вычисляется по формуле $$. Вам нужно найти максимальный по релевантности список среди всех допустимых.

Решение

Путем несложных математических выкладок можно показать, что задача может быть решена «жадным» подходом, т. е. в оптимальном списке рекомендаций на каждой позиции стоит самый релевантный объект из всех, которые допустимы при том же начале списка. Имплементация этого подхода простая: берём объекты подряд и добавляем их в ответ, если это возможно. Когда встречается недопустимый объект (тип которого совпадает с типом предыдущего), то откладываем его в отдельную очередь, из которой вставляем в ответ при первой же возможности. Заметим, что в каждый момент времени у всех объектов в этой очереди будет совпадающий тип. В конце в очереди могут остаться несколько объектов, они уже не войдут в ответ.

 std::vector<int> blend(int n, int m, const std::vector<int>& types) {
    std::vector<int> result;
    std::queue<int> repeated;
    for (int i = 0; i < n; ++i) {
        if (result.empty() || types[result.back()] != types[i]) {
            result.push_back(i);
            if (!repeated.empty() && types[repeated.front()] != types[result.back()]) {
                result.push_back(repeated.front());
                repeated.pop();
            }
        } else {
            repeated.push(i);
        }
    }
    return result;
}

D. Кластеризация символьных последовательностей

Имеется конечный алфавит A = {a₁, a₂,…, a_K−1, a_K = S}, a_i ∈ {a, b,…, z}, S — конец строки.

Рассмотрим следующий способ генерации случайных строк над алфавитом A:

1. Первый символ x₁ — случайная величина с распределением P(x₁ = a_i) = q_i (известно, что q_K = 0).
2. Каждый следующий символ генерируется на основе предыдущего в соответствии с условным распределением P(x_i = a_j || x_{i – 1} = a_l) = p_jl.
3. Если x_i = S, генерация прекращается и результатом является x₁x₂...x_i−1.

Даётся набор строк, сгенерированных из смеси двух описанных моделей с различными параметрами. Необходимо для каждой строки дать индекс цепи, из которой она была сгенерирована.

Решение

Задача решается с помощью EM-алгоритма: предполагается, что представленная выборка сгенерирована из смеси двух марковских цепей, параметры которых восстанавливаются в процессе итераций. Ограничение в 80% правильных ответов сделано, чтобы на правильность решения не влияли примеры, у которых высокая вероятность в обеих цепях. Эти примеры, таким образом, при правильном восстановлении могут быть отнесены к цепи, неверной с точки зрения сгенерированного ответа.

import random
import math


EPS = 1e-9


def empty_row(size):
    return [0] * size


def empty_matrix(rows, cols):
    return [empty_row(cols) for _ in range(rows)]


def normalized_row(row):
    row_sum = sum(row) + EPS
    return [x / row_sum for x in row]


def normalized_matrix(mtx):
    return [normalized_row(r) for r in mtx]


def restore_params(alphabet, string_samples):
    n_tokens = len(alphabet)
    n_samples = len(string_samples)
    samples = [tuple([alphabet.index(token) for token in s] + [n_tokens - 1, n_tokens - 1]) for s in string_samples]
    probs = [random.random() for _ in range(n_samples)]

    for _ in range(200):
        old_probs = [x for x in probs]

        # probs fixed   
        p0, A = empty_row(n_tokens), empty_matrix(n_tokens, n_tokens)
        q0, B = empty_row(n_tokens), empty_matrix(n_tokens, n_tokens)
        for prob, sample in zip(probs, samples):
            p0[sample[0]] += prob
            q0[sample[0]] += 1 - prob
            for t1, t2 in zip(sample[:-1], sample[1:]):
                A[t1][t2] += prob
                B[t1][t2] += 1 - prob

        A, p0 = normalized_matrix(A), normalized_row(p0)
        B, q0 = normalized_matrix(B), normalized_row(q0)
        
        trans_log_diff = [
            [math.log(b + EPS) - math.log(a + EPS) for b, a in zip(B_r, A_r)]
            for B_r, A_r in zip(B, A)
        ]
      
        # A, p0, B, q0 fixed
        probs = empty_row(n_samples)
        for i, sample in enumerate(samples):
            value = math.log(q0[sample[0]] + EPS) - math.log(p0[sample[0]] + EPS)
            for t1, t2 in zip(sample[:-1], sample[1:]):
                value += trans_log_diff[t1][t2]
            probs[i] = 1.0 / (1.0 + math.exp(value))
        
        if max(abs(x - y) for x, y in zip(probs, old_probs)) < 1e-9:
            break
    
    return [int(x > 0.5) for x in probs]


def main():
    N, K = list(map(int, input().split()))
    string_samples = []
    alphabet = list(input().strip()) + ['']
    for _ in range(N):
        string_samples.append(input().rstrip())
    result = restore_params(alphabet, string_samples)
    for r in result:
        print(r)


if __name__ == '__main__':
    main()

---

Вот разборы задач по бэкенду и фронтенду.