Пропущенные значения являются распространённой проблемой в анализе данных, для решения которой разработано множество методов. Одним из наиболее популярных подходов является заполнение пропущенных значений с использованием метода k-ближайших соседей (KNN), основанного на информации от схожих наблюдений. Данный подход широко применяется в анализе больших данных, где объёмы выборок могут достигать миллиардов объектов, что делает задачу ускорения KNN особенно актуальной из-за его линейной сложности. В данной работе предлагается алгоритм ускоренного заполнения пропущенных значений на основе методов приближённого поиска ближайших соседей (ANN) и анализируется соотношение между скоростью работы и качеством заполнения. Экспериментальные результаты показывают, что использование ANN позволяет существенно сократить время вычислений при сохранении высокого качества заполнения пропущенных значений.

Статья посвящена валидации краткой версии опросника «Типы ориентаций в трудных ситуациях» (ТОРС-36) в качестве инструмента классификации типов восприятия трудных жизненных ситуаций и оценке роли анализа текстовых описаний с привлечением больших языковых моделей в определении этих типов. Решаются следующие задачи: разработка и валидация алгоритма классификации типов восприятия трудных ситуаций на основе профиля ТОРС-36 с привлечением больших языковых моделей для анализа текстовых описаний; сопоставление результатов алгоритмической классификации с экспертной оценкой; сравнение эффективности различных модификаций алгоритма. В выборку исследования вошли 200 текстовых описаний трудных ситуаций, полученных от 200 респондентов (131 женщина, 69 мужчин) в возрасте от 14 до 54 лет. Эталонная классификация выполнялась экспертами-психологами на основе совместного анализа количественных показателей шкал опросника ТОРС-36 и качественных данных (текстовых описаний трудных ситуаций). Проведена серия из шести экспериментов. В экспериментах 1–4 последовательно возрастала роль количественных данных и формальных правил классификации. В эксперименте 5 оценивалась точность классификации при разметке качественных данных с помощью большой языковой модели, в эксперименте 6 – при разметке, выполненной экспертами-психологами. Наиболее эффективным среди алгоритмов, использующих большую языковую модель, оказался гибридный, в котором пороговые правила применяются к количественным показателям, а большая языковая модель анализирует качественные данные. Его точность составила 85% на полной выборке. При этом максимальная точность классификации в серии экспериментов – 85,5% – достигнута при использовании того же алгоритма с экспертной разметкой качественных данных. Полученные результаты подтверждают возможность использования опросника ТОРС-36 как инструмента классификации типов восприятия трудных ситуаций и позволяют рассматривать большие языковые модели как средство поддержки эксперта при классификации типов восприятия трудных ситуаций.

В работе представлен обзор современного состояния исследований, посвященных теоретическим методам оценки сложности моделей машинного обучения и их связи с обобщающей способностью. Методологически работа оформлена как обзор предметной области. Указываются источники библиографического поиска, этапы дедупликации и полуавтоматического сужения корпуса документов, экспертный отбор и состав итогового аналитического набора публикаций. Основной вклад обзора состоит в анализе классических мер сложности из статистической теории обучения и их ограниченности для объяснения поведения современных перепараметризованных глубоких моделей машинного обучения. Показано, что VC-размерность, радемахеровские и PAC-байесовские оценки сохраняют значение как теоретический результат, однако характеризуют мощность класса гипотез в худшем случае и лишь ограниченно учитывают локальные геометрические характеристики решения, траекторию оптимизации и архитектурные особенности. Основное внимание уделено современным направлениям, включающим анализ ландшафта функции потерь, спектральных характеристик гессиана, методов оптимизации и эмпирических законов масштабирования. В результате предложена интерпретация текущего состояния предметной области, согласно которой современная теория сложности должна описывать не только класс моделей, но и эффективную сложность решений, учитывающих как локальные характеристики модели, так и данные, на которых она обучается.

Поиск архитектуры нейронной сети – это метод, позволяющий автоматически подобрать наилучшую архитектуру нейронной сети для данной задачи на представленном алгоритму наборе данных. Одной из разновидностей поиска архитектуры нейронной сети является DARTS – differentiable neural architecture search. DARTS позволяет перейти от дискретного пространства поиска к непрерывному и использовать метод градиентного спуска для подбора параметров, отвечающих за архитектуру сети. В статье будет рассмотрена возможность использования метода DARTS для подбора схемы квантизации и разрядности различных компонентов генеративных языковых моделей и описаны результаты проведенных экспериментов. Код для обучения и оценки квантизованной модели доступен по ссылке: https://github.com/daria1d/Darts-QAT.

Метод построения выпуклых линейных оболочек конечного множества точек часто используется в задачах распознавания. В \(n-\)мерном пространстве для этого перебираются \(n\) элементные подмножества точек. Если оставшиеся точки лежат по одну сторону от гиперплоскости, содержащей выбранные точки, то эта гиперплоскость называется гранью. Проверка новой точки на принадлежность выпуклой линейной оболочке сводится к проверке выполнения системы линейных неравенств, образованных гранями.

Предлагается решать огрублённую задачу, когда координаты точек принимают три значения \(0,1,-1\), интерпретируемые как элементы поля из трёх элементов. При этом линейная функция равна нулю в точках, лежащих на гиперплоскости, равна \(1\) с одной стороны от неё, и равна \(-1\) с другой стороны. Проверка принадлежности точки выпуклой линейной оболочке сводится к проверке условий \(S_a(x)\in \{0,\lambda _a\}\) для всех граней \(S_a\) выпуклой линейной оболочки, где значение \(0\) соответствует принадлежности точки гиперплоскости \(S_a\), а \(\lambda _a\) является общим значением линейной формы на точках множества, не принадлежащих \(S_a\). Таким образом, принадлежность новой точки выпуклой линейной оболочке определяется её положением относительно всех граней оболочки.

Данная работа продолжает изучение вопроса сложности реализуемости автоматов посредством кодирований алфавита состояний. Ранее изучался вопрос простой реализуемости как автоматов, так и отображений на конечном множестве. В данной работе изучаются сложно реализуемые отображения на конечном множестве, т. е. такие отображения, что любое неизбыточное кодирование приводит к булеву оператору максимальной сложности с точки зрения степени полинома Жегалкина. Доказано, что для любой мощности множества \(n=2^k\) существуют сложно реализуемые отображения. Существование таких отображений позволит в дальнейшем доказать существование сложно реализуемых автоматов.

Для систем автоматных функций, образующих замкнутый класс важно определить, базисом от какого минимального числа переменных они могут быть получены операциями суперпозиции. Особый интерес представляют классы, в которых «собственно» автоматы из базиса имеют одну входную переменную, это ограничение не распространяется на булевы функции из базиса, которые являются автоматами с одним состоянием. Примером такого класса является класс всех автоматов. Автор изучает подклассы автоматов, у которых функции переходов и выходов принадлежат некоторому классу Поста.

Рассматриваются одномерные клеточные автоматы с локаторами, у которых полугруппа, заданная на алфавите вещания, является идемпотентным моноидом. Ранее было показано, что такие сложные задачи для клеточных автоматов как задача синхронизации стрелков или задача управления движением точки на прямой в идемпотентных клеточных автоматах с локаторами решаются совсем просто и задачи фактически вырождаются. В данной работе показано, что для задач, где надо сравнивать расстояния, идемпотентные клеточные автоматы с локаторами не дают преимущества по порядку по сравнению с обычными клеточными автоматами. Тогда как использование неидемпотентных клеточных автоматов дает принципиальный выигрыш по времени.

В работе исследована проблема \(K\)-полноты в классе линейных \(p\)-адических автоматов для нечётного простого числа \(p\). Получены критерии полноты для однородных и неоднородных линейных \(p\)-адических функций. Полученные результаты обобщают известные свойства линейных \(2\)-адических автоматов на случай произвольного нечётного простого основания. Кроме того, построена континуальная строго возрастающая цепочка \(K\)-замкнутых классов \(I_\alpha\), \(\alpha \in (0,1]\).

В работе рассматриваются коды Таннера, построенные на графе инцидентности точек и гиперплоскостей проективного пространства, с проективными кодами Рида-Маллера в качестве компонентных кодов. Сопоставление символов локальных кодов рёбрам производится таким образом, чтобы получаемый код Таннера обладал симметрией проективного пространства. В работе получены нижние оценки минимального расстояния и размерности таких кодов. В частности, показано, что при определённых значениях параметров эти коды являются асимптотически хорошими.