Хабрахабр

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

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

A. Опечатки

Условие

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

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

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

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

Форматы ввода/вывода и пример

Формат ввода

В первой строке содержится слово, которое, по нашему предположению, пользователь имел в виду (оно состоит из букв латинского алфавита в нижнем регистре, длина не превышает 20).

Во второй строке содержится слово, которое он на самом деле написал (оно также состоит из букв латинского алфавита в нижнем регистре, длина не превышает 20).

В третьей строке содержится единственное число N (N < 50) — количество замен, описывающих различные ошибки.

Последовательности имеют длину не более 6 символов. В следующих N строках содержатся возможные замены в формате &lt«правильная» последовательность букв&gt<пробел><«ошибочная» последовательность букв>.

Формат вывода

Требуется вывести одно число — минимальное количество ошибок, которое мог совершить пользователь. Если это количество превышает 4 или же из одного слова невозможно получить другое, следует вывести –1.

Пример

Решение

Попробуем сгенерировать из правильного написания все возможные слова не более чем с 4 ошибками. Их в худшем случае может быть O((L﹒N)4). В ограничениях задачи это довольно большое число, поэтому нужно придумать, как уменьшить сложность. Можно вместо этого воспользоваться алгоритмом meet-in-the-middle: сгенерировать слова не более чем c 2 ошибками, а также слова, из которых можно получить написанное пользователем слово, сделав не более 2 ошибок. Заметим, что размер каждого из этих множеств не будет превышать 106. Если количество сделанных пользователем ошибок не превосходит 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) }; } 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. Многорукий бандит

Условие

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

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

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

Форматы ввода/вывода и пример

Формат ввода

Одно исполнение может состоять из нескольких тестов.

В следующей строке содержатся два вещественных числа α и β (1 ≤ α, β ≤ 10) — параметры бета-распределения вероятности выигрыша. Каждый тест начинается с того, что вашей программе в одной строке подаются два целых числа, разделённые пробелом: число N — количество жетонов в вашем мешке, и M — количество автоматов в зале (N ≤ 104, M ≤ min(N, 100)).

На каждый запрос выведите в отдельную строку номер автомата, в который вы будете играть (от 1 до M включительно). Протокол общения с проверяющей системой такой: вы делаете ровно N запросов. В качестве ответа в отдельной строке будет стоять либо «0», либо «1», означающие соответственно проигрыш и выигрыш в игре с запрошенным автоматом.

После последнего теста вместо чисел N и M будут стоять два нуля.

Формат вывода

Задача будет считаться сданной, если ваше решение не сильно хуже решения жюри. Если ваше решение будет значительно хуже решения жюри, вы получите вердикт «неправильный ответ».

Гарантируется, что если ваше решение не хуже, чем решение жюри, то вероятность получить вердикт «неправильный ответ» не превосходит 10–6.

Примечания

Пример взаимодействия:

____________________ stdin stdout
____________________
____________________ 5 2 2 2 2 1 1 0 1 1 2 1 2 1

Решение

Эта задача достаточно известна, её можно было решать по-разному. Основное решение жюри реализовывало стратегию 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.

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

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

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

.

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

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

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

.

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

Перевод 4.

Далее генерируем длину предложения на языке перевода Lt ≥ 1 из условного дискретного распределения: С вероятностью (1 – pd – pi – ph) берём длину предложения на языке оригинала Ls ≥ 1 из распределения ps (с округлением вверх).

.

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

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

[2-1] С вероятностью psplit s сгенерированное предложение на языке оригинала распадается на два непустых, так, чтобы суммарное количество слов увеличилось ровно на один. 1. Вероятность того, что предложение длины Ls распадётся на части длиной L1 и L2 (то есть L1 + L2 = Ls + 1), пропорциональна Ps(L1) ⋅ Ps(L2).

[1-2] С вероятностью psplit t сгенерированное предложение на языке перевода распадается на два непустых, так, чтобы суммарное количество слов увеличилось ровно на один. 2. Вероятность того, что предложение длины Lt распадётся на части длиной L1 и L2 (то есть L1 + L2 = Lt + 1), пропорциональна Pt(L1) ⋅ Pt(L2).

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

Форматы ввода/вывода, примеры и примечания

Формат ввода

В первой строке файла записаны параметры распределений: ph, pd, pi, psplit s, psplit t, μs, σs, μt, σt. 0,1 ≤ σst ≤ 3. 0 ≤ μs, μt ≤ 5.

В следующей строке стоят числа Ns и Nt — количество предложений в корпусе на языке оригинала и на языке перевода соответственно (1 ≤ Ns, Nt ≤ 1000).

В следующей строке находятся Nt целых чисел — длины предложений на языке перевода. В следующей строке находятся Ns целых чисел — длины предложений на языке оригинала.

В следующей строке находятся два числа: j и k (1 ≤ j ≤ Ns, 1 ≤ k ≤ Nt).

Формат вывода

Требуется вывести вероятность того, что предложения с индексами j и k в текстах соответственно являются параллельными (то есть что они сгенерированы на одном шаге алгоритма и ни одно из них не является результатом распада).

Ваш ответ будет принят, если абсолютная погрешность не превосходит 10–4.

Пример 1

Пример 2

Пример 3

Примечания

В первом примере исходную последовательность чисел можно получить тремя способами:

• Сначала с вероятностью pd дописать одно предложение в оригинальный текст, затем с вероятностью pi дописать одно предложение в перевод, потом с вероятностью ph закончить генерацию.

Вероятность этого события равна P1 = pd * Ps(4) * pi * Pt(20) * ph.

• Сначала с вероятностью pd дописать одно предложение в оригинальный текст, затем с вероятностью pi дописать одно предложение в перевод, потом с вероятностью ph закончить генерацию.

Вероятность этого события равна P2 = pi * Pt(20) * pd * Ps(4) * ph.

• C вероятностью (1 – ph – pd – pi) сгенерировать два предложения, затем с вероятностью (1 – psplit s – psplit t) оставить всё как есть (то есть не разбивать на два предложения ни оригинал, ни перевод) и после этого с вероятностью ph закончить генерацию.

Вероятность этого события равна
.

В итоге ответ рассчитывается как .

Решение

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

Код

#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector> double p_h, p_d, p_i, p_tr, p_ss, p_st, mu_s, sigma_s, mu_t, sigma_t; double lognorm_cdf(double x, double mu, double sigma) { if (x < 1e-9) return 0.0; double res = std::log(x) - mu; res /= std::sqrt(2.0) * sigma; res = 0.5 * (1 + std::erf(res)); return res;
} double length_probability(int l, double mu, double sigma) { return lognorm_cdf(l, mu, sigma) - lognorm_cdf(l - 1, mu, sigma);
} double translation_probability(int ls, int lt) { double res = length_probability(ls, mu_s, sigma_s); double mu = mu_t - mu_s + std::log(ls); double sigma = std::sqrt(sigma_t * sigma_t - sigma_s * sigma_s); res *= length_probability(lt, mu, sigma); return res;
} double split_probability(int l1, int l2, double mu, double sigma) { int l_sum = l1 + l2; double total_prob = 0.0; for (int i = 1; i < l_sum; ++i) { total_prob += length_probability(i, mu, sigma) * length_probability(l_sum - i, mu, sigma); } return length_probability(l1, mu, sigma) * length_probability(l2, mu, sigma) / total_prob;
} double log_prob10(int ls) { return std::log(p_d * length_probability(ls, mu_s, sigma_s));
} double log_prob01(int lt) { return std::log(p_i * length_probability(lt, mu_t, sigma_t));
} double log_prob11(int ls, int lt) { return std::log(p_tr * (1 - p_ss - p_st) * translation_probability(ls, lt));
} double log_prob21(int ls1, int ls2, int lt) { return std::log(p_tr * p_ss * split_probability(ls1, ls2, mu_s, sigma_s) * translation_probability(ls1 + ls2 - 1, lt));
} double log_prob12(int ls, int lt1, int lt2) { return std::log(p_tr * p_st * split_probability(lt1, lt2, mu_t, sigma_t) * translation_probability(ls, lt1 + lt2 - 1));
} double logsum(double v1, double v2) { double res = std::max(v1, v2); v1 -= res; v2 -= res; v1 = std::min(v1, v2); if (v1 < -30) { return res; } return res + std::log(std::exp(v1) + 1.0);
} double loginc(double* to, double from) { *to = logsum(*to, from);
} constexpr double INF = 1e25; int main(void) { using std::cin; using std::cout; cin >> p_h >> p_d >> p_i >> p_ss >> p_st >> mu_s >> sigma_s >> mu_t >> sigma_t; p_tr = 1.0 - p_h - p_d - p_i; int Ns, Nt; cin >> Ns >> Nt; using std::vector; vector<int> ls(Ns), lt(Nt); for (int i = 0; i < Ns; ++i) cin >> ls[i]; for (int i = 0; i < Nt; ++i) cin >> lt[i]; vector< vector< double> > fwd(Ns + 1, vector<double>(Nt + 1, -INF)), bwd = fwd; fwd[0][0] = 0; bwd[Ns][Nt] = 0; for (int i = 0; i <= Ns; ++i) { for (int j = 0; j <= Nt; ++j) { if (i >= 1) { loginc(&fwd[i][j], fwd[i - 1][j] + log_prob10(ls[i - 1])); loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j] + log_prob10(ls[Ns - i])); } if (j >= 1) { loginc(&fwd[i][j], fwd[i][j - 1] + log_prob01(lt[j - 1])); loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i][Nt - j + 1] + log_prob01(lt[Nt - j])); } if (i >= 1 && j >= 1) { loginc(&fwd[i][j], fwd[i - 1][j - 1] + log_prob11(ls[i - 1], lt[j - 1])); loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j + 1] + log_prob11(ls[Ns - i], lt[Nt - j])); } if (i >= 2 && j >= 1) { loginc(&fwd[i][j], fwd[i - 2][j - 1] + log_prob21(ls[i - 1], ls[i - 2], lt[j - 1])); loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i + 2][Nt - j + 1] + log_prob21(ls[Ns - i], ls[Ns - i + 1], lt[Nt - j])); } if (i >= 1 && j >= 2) { loginc(&fwd[i][j], fwd[i - 1][j - 2] + log_prob12(ls[i - 1], lt[j - 1], lt[j - 2])); loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j + 2] + log_prob12(ls[Ns - i], lt[Nt - j], lt[Nt - j + 1])); } } } int j, k; cin >> j >> k; double rlog = fwd[j - 1][k - 1] + bwd[j][k] + log_prob11(ls[j - 1], lt[k - 1]) - bwd[0][0]; cout << std::fixed << std::setprecision(12) << std::exp(rlog) << std::endl;
}

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

Условие

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

Объект под номером i имеет тип с номером bi ∈ {0,…, m − 1}. Пусть задан исходный список рекомендаций a = [a0, a1,…, an − 1] длины n > 0. Рассмотрим список, который получается из исходного выбором подмножества объектов и их перестановкой: x = [ai0, ai1,…,aik−1] длины k (0 ≤ k ≤ n). Кроме того, объект под номер i имеет релевантность r(ai) = 2−i. е. Список называется допустимым, если никакие два подряд идущих объекта в нём не совпадают по типу, т. Релевантность списка вычисляется по формуле $\sum_{j=0}^{k-1} 2_{-j}r(a_{i_j})$. bij ≠ bij + 1 для всех j = 0,…, k−2. Вам нужно найти максимальный по релевантности список среди всех допустимых.

Форматы ввода/вывода и примеры

Формат ввода

На первой строке через пробел записаны числа n и m (1 ≤ n ≤ 100000, 1 ≤ m ≤ n). На следующих n строках записаны числа bi для i = 0,…, n − 1 (0 ≤ bi ≤ m − 1).

Формат вывода

Выпишите через пробел номера объектов итогового списка: i0, i1,…, ik−1.

Пример 1

Пример 2

Пример 3

Решение

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

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 = {a1, a2,…, aK−1, aK = S}, ai ∈ {a, b,…, z}, S — конец строки.

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

Первый символ x1 — случайная величина с распределением P(x1 = ai) = qi (известно, что qK = 0).
2. 1. Если xi = S, генерация прекращается и результатом является x1x2...xi−1. Каждый следующий символ генерируется на основе предыдущего в соответствии с условным распределением P(xi = aj || xi – 1 = al) = pjl.
3.

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

Форматы ввода/вывода, пример и примечания

Формат ввода

В первой строке записано два числа 1000 ≤ N ≤ 2000 и 3 ≤ K ≤ 27 — число строк и размер алфавита соответственно.

Во второй строке записана строка, состоящая из K−1 различных строчных букв латинского алфавита, обознающая первые K−1 элементов алфавита.

Каждая из следующих N строк сгенерирована по описанному в условии алгоритму.

Формат вывода

N строк, в i-й строке содержится номер кластера (0/1) для последовательности на i+1-й строке входного файла. Совпадение с истинным ответом должно быть не менее 80%.

Пример

Примечания

Замечание к тесту из условия: в нём первые 50 строк сгенерированы из распределения
P(xi = a | xi−1 = a) = 0.5, P(xi = S | xi−1 = a) = 0.5, P(x1 = a) = 1; вторые 50 — из распределения
P(xi = b | xi−1 = b) = 0.5, P(xi = S | xi−1 = b) = 0.5, P(x1 = b) = 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()

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть