Как ученый-вычислитель (а теперь и специалист по данным) я всю жизнь увлекался числами, особенно списками и таблицами (= базами данных!). Например, в раннем возрасте я подумал, что хочу изучать математику в колледже и изучать теорию чисел, чтобы научиться всем удивительным способам делать крутые вещи с числами. Но я также хотел изучать чудеса Вселенной как астроном, поэтому получил степень доктора астрофизики! Этот карьерный путь позволил мне изучить и применить все дисциплины, которые мне нравятся: математику, физику, астрономию, компьютерное моделирование и науку о данных! Все время это были числа!

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

Пример 1а. Файлы cookie Girl Scout

Я часто давал это задание своим студентам, изучающим компьютерные науки о данных: если в каталоге файлов cookie девочек-скаутов указано 25 различных типов файлов cookie (который представляет собой конечный набор объектов), и у вас достаточно денег только на пять коробок файлов cookie (что является ограничением). ), то сколько различных комбинаций пяти различных типов файлов cookie вы должны рассмотреть, если хотите изучить все такие комбинации? Прежде чем мы найдем ответ на этот вопрос, давайте начнем с более простой версии проблемы: предположим, что существует всего четыре различных типа файлов cookie (A, B, C и D), и у вас есть средства только на две коробки. Вот различные уникальные комбинации, которые существуют в этом простом случае: AB, AC, AD, BC, BD, CD. Следовательно, в этом случае есть шесть различных уникальных комбинаций.

Комбинаторная теорема из математики дает общее решение нашей проблемы для любого набора чисел. Мы применим эту теорему к нашему случаю с «25 типов файлов cookie, выберите 5». Чтобы вычислить это быстро, нам нужно использовать специальную математическую функцию - факториал, выраженный восклицательным знаком (N!). N-факториал относится к произведению N умноженных на каждое положительное целое число меньше N, пока вы не достигнете 1. Например: 5! = 5 * 4 * 3 * 2 * 1 = 120. И 25! = 25 * 24 * 23 *… * 3 * 2 * 1, что является очень большим числом, больше 10 в степени 25. Итак, комбинаторная теорема (в которой используется факториальная функция) определяет количество способов выбора k элементов из набора N: значение может быть вычислено как (N!) деленное на (k!) * (Nk) !.

Для нашей девочки-скаута проблема с печеньем результат 25! делится на 5! 20! составляет 53 130. Мы можем проверить это, применив теорему к нашему простому случаю, в котором было 4 типа файлов cookie, выберите любые 2: результат - 4! (24) делится на 2! 2! (4), что равно 6. Итак, если вы рассматриваете все возможные комбинации 5 различных типов печенья Girl Scout из каталога 25 типов, то вам необходимо рассмотреть более 53 000 комбинаций. Если вы потратите одну секунду на обдумывание каждого из этих вариантов, вам понадобится около 15 часов, чтобы выполнить задачу - если вы не выполняете оценки параллельно, а не последовательно. Если над проблемой работает параллельный компьютер, возможно, со 100 вычислительными узлами в кластере, которому требуется всего одна миллисекунда для оценки каждой комбинации, тогда вся задача (53 130 оценок) может быть выполнена за полсекунды! Ка-цзин! Получите один балл за распределенные параллельные вычисления!

Пример 1b. Еще файлы cookie для девочек-скаутов

Теперь рассмотрим ту же проблему, что и выше, но с одной изюминкой. Вот почему: мне не обязательно нужны файлы cookie пяти разных типов. Мне могут понадобиться дубликаты. Итак, новая проблема заключается в следующем: с учетом 25 различных типов файлов cookie и финансирования, достаточного только для пяти коробок (любого типа), сколькими способами я могу выбрать пять коробок? Давайте начнем снова с простого примера четырех типов (A, B, C, D), выберите два (включая дубликаты). Доступны 16 вариантов: AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD. Обратите внимание, что в этом списке есть несколько дубликатов (например, BA и BA называются вырождением: они соответствуют двум различным способам выбора, который приводит к одному и тому же конечному результату) - это нормально, поскольку оно отражает фактическое распределение вероятностей. Например, представьте себе бросание двух кубиков (6 значений, выберите 2): существует 36 возможных результатов, но есть несколько вырождений, например, есть два способа получить «1» и «6», а там шесть способов суммирования суммы значений до «7» (1–6, 6–1, 2–5, 5–2, 3–4, 4–3).

В общем, чтобы выбрать k элементов (включая дубликаты) из набора N, существует N вариантов выбора для каждого из k вариантов, поэтому общее количество комбинаций равно N в степени k. Следовательно, для нашей проблемы с печеньем Girl Scout существует 25 * 25 * 25 * 25 * 25 (= 25 в 5-й степени = 9 765 625) комбинаций «дано 25 вещей на выбор, выберите 5 ( включая дубликаты) ». Это намного большее число, чем в нашем первом примере выше (более чем в 180 раз больше), и это очень важный факт, о котором следует помнить. Как мы отмечали ранее, параллельное вычисление этих типов комбинаторных выборок намного быстрее, чем их последовательное вычисление.

Пример 2а. Ведение блога

При описании приведенного выше примера на ум пришел связанный с ним пример. Мне пришло в голову, что есть как минимум четыре аспекта написания хороших блогов: творческий (оригинальный), интересный (увлекательный), информативный (образовательный) и полезный (применимый к реальному варианту использования). Предположим для простоты, что существует пять возможных оценок по каждому из этих параметров: одна звезда (плохо), две звезды, три звезды (средний), четыре звезды или пять звезд (лучший). Таким образом, существует 625 (= 5 в степени 4) возможных общих рейтингов блога, поскольку существует пять вариантов рейтинга в четырех категориях (5 * 5 * 5 * 5). Только 16 из этих общих рейтингов блогов имеют четырехзвездочный или пятизвездочный рейтинг во всех четырех категориях: два рейтинга на выбор для каждой из четырех категорий (= 2 * 2 * 2 * 2 = 16). Следовательно, сложно написать блог, который получил бы 5 звезд во всех категориях: креативном, интересном, информативном и полезном. Фактически, это примерно в 40 раз (625/16) сложнее, чем блог произвольного качества. Это напоминает мне старую пословицу "Если 100 обезьян достаточно долго будут печатать на клавиатуре, в конечном итоге они создадут Гамлета Шекспира". Оказывается, вероятность того, что это произойдет, бесконечно мала.

Пример 2b: больше блогов

Несколько лет назад я разговаривал с коллегой по науке о данных о множестве сотен новых алгоритмов машинного обучения, которые исследователи машинного обучения постоянно представляют на исследовательских конференциях машинного обучения каждый год в течение последних 10–20 лет. Я знаю об этом, потому что видел это, когда около 20 лет назад начал ходить на конференции SIGKDD KDD, SIAM SDM, ICML и IEEE ICDM. Во время моего разговора с моим коллегой мы отметили, что некоторые из этих новых алгоритмов были существенно разными смесями и комбинациями некоторых из более фундаментальных алгоритмов - например, одним из таких составных алгоритмов может быть байесовская регрессия на графовых нейронных сетях. (Я только что придумал, но потом нашел это.)

Существует примерно 10 основных алгоритмов машинного обучения (см. Книгу, проиллюстрированную ниже), включая 10, перечисленные в этой статье о средстве: деревья решений (включая случайные леса и C4.5), кластеризация K-средних, классификация SVM, ассоциация Apriori. интеллектуальный анализ, вероятность максимизации ожидания (EM), PageRank, Adaboost, классификация KNN, наивный байесовский метод, классификация CART и деревья регрессии. Я уверен, что вы заметите в этих старых списках, что некоторые из лучших алгоритмов машинного обучения сегодня даже не перечислены, например, множество различных форм нейронных сетей (CNN, RNN, LSTM, GAN, капсульные сети и т. Д.).

Итак, мой коллега и я представили себе использование генеративного алгоритма для автоматического создания всех возможных комбинаций этих 10 основных алгоритмов, затем создание составного алгоритма для каждой из этих комбинаций, а затем отправку исследовательской работы для каждого из этих составных алгоритмов одному из них. этих ежегодных конференций ML. Для этого нам потребовалось бы много конференций, и это звучало слишком болезненно, поэтому вместо этого мы решили, что, возможно, мы могли бы использовать что-то вроде GPT-3 для создания одного нового блога для каждого нового составного алгоритма.

Сколько это было бы блогов? Мы можем использовать биномиальную теорему, чтобы ответить на этот вопрос: общее число равно 2 в N -й степени (минус 1). Для N = 10 ответ будет 1023. (Почему эта комбинация? См. Следующий абзац.) Вау! Приложив немного магии GPT-3, мы можем создать множество статей. Конечно, о некоторых композитах уже известно и написано, и, конечно же, об исходных 10 алгоритмах уже очень хорошо написано. Так что, возможно, мы разместим всего около 900 блогов. Неплохо для рабочего дня! Я уже вижу, как прибыль от блога растет.

Итак, почему биномиальная теорема? Эта теорема сообщает нам общее количество подмножеств набора из N элементов. Это легко увидеть в более простом случае. Предположим, что существует всего 3 основных алгоритма. Тогда любой блог, который вы пишете, будет включать или не включать каждый из них. Мы можем закодировать каждый блог трехзначным индексом {i, j, k}, где один из этих (i, j, или k ) равно «1», если тема освещена в блоге, и равно «0», если тема не освещена в блоге. Итак, полный набор индексов, представляющих уникальные составные блоги, которые мы могли бы написать и которые охватывают хотя бы одну из трех основных тем, составляет: {100, 010, 001, 110, 101, 011, 111}. Это 7 = 2 в степени 3 минус 1. Мы вычитаем 1, потому что случай {000} - пустой блог. Как видите, для каждого места в индексе {i, j, k,…} есть 2 варианта: 0 или 1. Итак, для N = 10 биномиальная теорема говорит нам, что есть выбор от 2 до 10-й степени (1024).

Пример 3. Графическая аналитика

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

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

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

В таких приложениях мы узнали, что быстрые параллельные вычисления не только важны, но и необходимы! Быстрые вычислительные приложения, архитектуры и алгоритмы необходимы для расширенной аналитики и науки о данных. Считайте эти вещи убийцами комбинаторики! Подробнее о комбинаторном взрыве здесь.

Следуйте за мной в Твиттере на @KirkDBorne

Узнайте больше о моем внештатном консалтинговом / обучающем бизнесе: ООО Data Leadership Group

Посмотрите, что мы делаем в AI-стартапе DataPrime.ai

Узнайте больше о мощи графиков и графической аналитики в этой замечательной книге: