Ха, что это?

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

Сравнение эффективности алгоритмов — сложная задача. Конечно, можно проверить, сколько времени требуется алгоритму для запуска на небольших входных данных, но он сильно зависит от машины и не учитывает асимптотический рост. Итак, у нас есть несколько абстрактных методов для сравнения, таких как модель машины с произвольным доступом и асимптотический анализ наихудшего случая. В эпоху больших данных асимптотический анализ наихудшего случая с использованием нотации big oh более полезен, поскольку он учитывает производительность алгоритма, когда входные данные становятся очень большими.

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

Давайте объясним важность этой модели сравнения. Предположим, у нас есть компьютер, который может обрабатывать 10⁹ инструкций в секунду. Беря алгоритмы разной сложности в худшем случае, мы сравниваем производительность. [n означает количество входных данных]

  • Алгоритм сложности O(n!) в худшем случае будет бесполезен для этого алгоритма при n ≥ 20.
  • O(2^n) будет бесполезен для n>40
  • O(n²) может обрабатывать около миллиона входных данных, но производительность сильно пострадает, если верхний предел равен миллиарду входных данных.
  • O (n) или O (n lgn) пострадают в производительности после миллиарда входов.
  • Но алгоритмы O(lgn) могут обрабатывать любое количество входных данных даже на этой машине.

Как видите, сложность алгоритма важнее, чем даже возможности машины, особенно в контексте больших данных с миллиардами входных данных.

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

Алгоритмы машинного обучения, которые мы обычно используем, пытаются решать проблемы, которые не являются выпуклыми или сложными NP, или и тем, и другим. Они используют эвристику для получения субоптимального решения без каких-либо гарантий точности, но, как правило, с практическим временем выполнения. Например, анализ основных компонентов имеет сложность O(m²n + n³), где m — количество переменных во входных данных. машина опорных векторов с методом Холецкого может быть O (n²), алгоритм k-средних Ллойда на практике имеет полиномиальную сложность и т. д. Таким образом, любой анализ огромного объема данных потребует огромного количества времени выполнения для больших входных данных. Аналогичная сложность в наихудшем случае может быть выполнена для получения требований к пространству для этих алгоритмов относительно размера входных данных. Это приводит к проблемам с требованиями к инфраструктуре для такого анализа данных.

Существуют различные модели вычислений, которые используются в промышленности в зависимости от задач, которые они пытаются решить. Модель распределенных вычислений была разработана для решения объемной части проблемы больших данных. Здесь мы перемещаем обработку в данные, вместо того, чтобы перемещать данные в процессор, избавляя процессор от проблем с заблокированными конвейерами. Но даже в распределенных настройках возникает проблема битов связи. Чтобы получить глобальное решение по всем данным, каждый отдельный сервер в распределенной сети должен взаимодействовать друг с другом или с контроллером. Сложность этих коммуникационных битов также вызывает беспокойство в сценарии больших данных, поскольку они могут блокировать сетевые линии связи, повышать затраты на электроэнергию, а также задерживать время обработки. В настройках потоковой передачи источником проблемы является скоростная часть данных. Когда входные данные поступают с высокой скоростью, алгоритм анализа данных должен обрабатывать их в режиме реального времени с минимальными требованиями к памяти.

Как видите, наука о данных в больших масштабах — это совершенно другой зверь. Иногда даже алгоритмов линейного времени, пространства или сложности связи недостаточно, чтобы справиться с потоком данных. Отсюда необходимость сублинейных алгоритмов для машинного обучения.

Сублинейные алгоритмы основаны на аппроксимации и рандомизации. Требуется принять во внимание только подмножество входных данных, чтобы получить в гарантированных пределах определенное количество раз (т. е. достоверность, например, с достоверностью 95 %), решение, точное в гарантированных пределах оптимального решения (например, 0,6 от оптимального решения), со сложностью, которая является сублинейным относительно входного размера во времени, пространстве или коммуникационных битах. Следовательно, сублинейному алгоритму можно дать одни и те же входные данные, и он даст другой результат, который будет иметь ограничения по точности для большей части времени на основе уровня достоверности алгоритма.

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