Связанные понятия
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Семплирование по Гиббсу — алгоритм для генерации выборки совместного распределения множества случайных величин. Он используется для оценки совместного распределения и для вычисления интегралов методом Монте-Карло. Этот алгоритм является частным случаем алгоритма Метрополиса-Гастингса и назван в честь физика Джозайи Гиббса.
Проклятие размерности (ПР) — термин, используемый в отношении ряда свойств многомерных пространств и комбинаторных задач. В первую очередь это касается экспоненциального роста необходимых экспериментальных данных в зависимости от размерности пространства при решении задач вероятностно-статистического распознавания образов, машинного обучения, классификации и дискриминантного анализа. Также это касается экспоненциального роста числа вариантов в комбинаторных задачах в зависимости от размера исходных...
Оператор Кэнни (детектор границ Кэнни, алгоритм Кэнни) в дисциплине компьютерного зрения — оператор обнаружения границ изображения. Был разработан в 1986 году Джоном Кэнни (англ. John F. Canny) и использует многоступенчатый алгоритм для обнаружения широкого спектра границ в изображениях.
Гистогра́мма в математической статистике — это функция, приближающая плотность вероятности некоторого распределения, построенная на основе выборки из него.
Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов, в которой один элемент (такой как вершина графа) добавляется в задачу на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Тест на следующий бит (англ. next-bit test) — тест, служащий для проверки генераторов псевдо-случайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью, неравной ½.
Двоичная, бинарная или дихотомическая классификация — это задача классификации элементов заданного множества в две группы (предсказание, какой из групп принадлежит каждый элемент множества) на основе правила классификации. Контекст, в котором требуется решение, имеет ли объект некоторое качественное свойство, некоторые специфичные характеристики или некоторую типичную двоичную классификацию, включает...
В криптографии
атака по энергопотреблению является одной из форм атак по сторонним каналам, при которой криптоаналитик изучает потребляемую мощность устройства, выполняющего криптографические задачи (как например смарт-карта, устойчивый к взлому «черный ящик», интегральная схема и тому подобное). С помощью такой атаки возможно извлечь криптографические ключи или другую секретную информацию из устройства, не оказывая на него непосредственного воздействия.
Многочасти́чный фильтр (МЧФ, англ. particle filter — «фильтр частиц», «частичный фильтр», «корпускулярный фильтр») — последовательный метод Монте-Карло — рекурсивный алгоритм для численного решения проблем оценивания (фильтрации, сглаживания), особенно для нелинейных и не-гауссовских случаев. Со времени описания в 1993 году Н. Гордоном, Д. Салмондом и А. Смитом используется в различных областях — навигации, робототехнике, компьютерном зрении.
Функция приспособленности (англ. fitness function) — вещественная или целочисленная функция одной или нескольких переменных, подлежащая оптимизации в результате работы генетического алгоритма, направляет эволюцию в сторону оптимального решения. Является одним из частных случаев целевой функции.
Переобучение (переподгонка, пере- в значении «слишком», англ. overfitting) в машинном обучении и статистике — явление, когда построенная модель хорошо объясняет примеры из обучающей выборки, но относительно плохо работает на примерах, не участвовавших в обучении (на примерах из тестовой выборки).
Сдвиг среднего значения — это непараметрическая техника анализа пространства признаков для определения местоположения максимума плотности вероятности, так называемый алгоритм поиска моды. Область применения техники — кластерный анализ в компьютерном зрении и обработке изображений.
Ме́тод моме́нтов — метод оценки неизвестных параметров распределений в математической статистике и эконометрике, основанный на предполагаемых свойствах моментов (Пирсон, 1894 г.). Идея метода заключается в замене истинных соотношений выборочными аналогами.
Байесовское программирование — это формальная система и методология определения вероятностных моделей и решения задач, когда не вся необходимая информация является доступной.
Аппара́тный генера́тор случа́йных чи́сел (генератор истинно случайных чисел) — устройство, которое генерирует последовательность случайных чисел на основе измеряемых, хаотически изменяющихся параметров протекающего физического процесса. Работа таких устройств часто основана на использовании надёжных источников энтропии, таких, как тепловой шум, дробовой шум, фотоэлектрический эффект, квантовые явления и т. д. Эти процессы в теории абсолютно непредсказуемы, на практике же получаемые из них случайные...
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем.
Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством.
Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.
Вычисления с памятью — способ построения вычислительных платформ, в которых используются принцип хранения результатов функций в массивах памяти, одномерных или двухмерных, в виде таблиц поиска, а вычисление функций заменяется извлечением значения из таблиц. Такие вычислительные платформы могут следовать как чисто пространственной модели вычислений, как в ПЛИС, так и временно́й модели вычислений (процедурной), когда функция вычисляется за множество тактов. Второй подход нацелен на уменьшение избыточности...
Выделение признаков — это процесс снижения размерности, в котором исходный набор сырых переменных сокращается до более управляемых групп (признаков) для дальнейшей обработки, оставаясь при этом достаточным набором для точного и полного описания исходного набора данных.
Спектральные методы — это класс техник, используемых в прикладной математике для численного решения некоторых дифференциальных уравнений, возможно, вовлекая Быстрое преобразование Фурье. Идея заключается в переписи решения дифференциальных уравнений как суммы некоторых «базисных функций» (например, как ряды Фурье являются суммой синусоид), а затем выбрать коэффициенты в сумме, чтобы удовлетворить дифференциальному уравнению, насколько это возможно.
Подробнее: Спектральный метод
Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.
Сети адаптивного резонанса — разновидность искусственных нейронных сетей, основанная на теории адаптивного резонанса Стивена Гроссберга и Гейла Карпентера. Включает в себя модели обучения с учителем и без учителя, которые используются при решении задач распознавания образов и предсказания.
Подробнее: Адаптивная резонансная теория
Оператор Ротуэлла , в дисциплине компьютерного зрения — оператор для обнаружения границ, представленный Чарлзом Ротуэллом (англ. C. A. Rothwell) на Симпозиуме IEEE по компьютерному зрению в 1995 году.
Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).
Техники спектральной кластеризации используют спектр (собственные значения) матрицы сходства данных для осуществления понижения размерности перед кластеризацией в пространствах меньших размерностей. Матрица сходства подаётся в качестве входа и состоит из количественных оценок относительной схожести каждой пары точек в данных.
Подробнее: Спектральная кластеризация
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Атака методом бумеранга – криптографическая атака на блочный шифр, основанная на методах дифференциального криптоанализа. Алгоритм атаки был опубликован в 1999 году профессором университета Беркли Дэвидом Вагнером, который использовал его для взлома шифров COCONUT98, Khufu и CAST-256 .
Самоорганизу́ющаяся ка́рта Ко́хонена (англ. Self-organizing map — SOM) — нейронная сеть с обучением без учителя, выполняющая задачу визуализации и кластеризации. Идея сети предложена финским учёным Т. Кохоненом. Является методом проецирования многомерного пространства в пространство с более низкой размерностью (чаще всего, двумерное), применяется также для решения задач моделирования, прогнозирования, выявление наборов независимых признаков, поиска закономерностей в больших массивах данных, разработке...
В математической статистике
семплирование — обобщенное название методов манипулирования начальной выборкой при известной цели моделирования, которые позволяют выполнить структурно-параметрическую идентификацию наилучшей статистической модели стационарного эргодического случайного процесса.
В обучении машин вероятностный классификатор — это классификатор, который способен предсказывать, если на входе заданы наблюдения, распределение вероятностей над множеством классов, а не только вывод наиболее подходящего класса, к которому наблюдения принадлежат. Вероятностные классификаторы обеспечивают классификацию, которая может быть полезна сама по себе или когда классификаторы собираются в ансамбли.
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем...
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Нейрокриптография — раздел криптографии, изучающий применение стохастических алгоритмов, в частности, нейронных сетей, для шифрования и криптоанализа.
Поиск с возвратом , бэктрекинг (англ. backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.
Цикломати́ческая сло́жность програ́ммы (англ. cyclomatic complexity of a program) — структурная (или топологическая) мера сложности компьютерной программы. Мера была разработана Томасом Дж. Маккейбом в 1976 году.
В обучении машин и распознавании образов признак — это индивидуальное измеримое свойство или характеристика наблюдаемого явления. Выбор информативных, отличительных и независимых признаков является критическим шагом для эффективных алгоритмов в распознавании образов, классификации и регрессии. Признаки обычно являются числовыми, но структурные признаки, такие как строки и графы, используются в синтаксическом распознавании образов.
Подробнее: Признак (обучение машин)
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения...