Pull to refresh
12
0
Волков Юрий @yurij_volkov

Пользователь

Send message

Краткое руководство по сложным вычислительным задачам

Reading time 5 min
Views 18K

Что компьютеру сделать легко, а что почти невозможно? Эти вопросы лежат в основе вопроса вычислительной сложности. Представляем вам карту этого ландшафта.



Различные классы сложности сортируют задачи в иерархическом виде. Один класс может содержать все задачи другого, плюс задачи, требующие дополнительных вычислительных ресурсов.

Какова фундаментальная сложность задачи? Такова постановка базовой задачи специалистов по информатике, пытающихся рассортировать задачи по т.н. классам сложности. Это группы, содержащие все вычислительные задачи, требующие не более фиксированного количества вычислительных ресурсов – таких, как время или память. Возьмём простой пример с большим числом типа 123 456 789 001. Можно задать вопрос: является ли оно простым числом – таким, которое делится только на 1 и себя? Специалисты по информатике могут ответить на него при помощи быстрых алгоритмов – таких, что не начинают тормозить на произвольно больших числах. В нашем случае окажется, что это число не является простым. Затем мы можем задать вопрос: каковы его простые множители? А вот для ответа на него быстрого алгоритма не существует – только если использовать квантовый компьютер. Поэтому специалисты по информатике считают, что две этих задачи относятся к разным классам сложности.
Читать дальше →
Total votes 30: ↑29 and ↓1 +28
Comments 8

Автоэнкодеры и сильный искусственный интеллект

Reading time 16 min
Views 22K
Теория автоэнкодеров и генерирующих моделей последнее время получила серьезное развитие, но достаточно мало работ посвящено тому, как можно использовать их в задачах распознавания. При этом свойство автоэнкодеров получать скрытую параметрическую модель данных и математические следствия из этого дают возможность связать их с Байесовскими методами принятия решения.

В статье предложен оригинальный математический аппарат «набор автоэнкодеров с общим латентным пространством», который позволяет выделять абстрактные понятия из входных данных и демонстрирует способность к «one-shot learning». Кроме того, с его помощью можно преодолеть многие фундаментальные проблемы современных алгоритмов машинного обучения, основанных на многослойных сетях и подходе «Deep learning».
Читать дальше →
Total votes 22: ↑22 and ↓0 +22
Comments 20

Инструменты Apple для машинного обучения

Reading time 10 min
Views 20K


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


В данной статье мы рассмотрим инструменты для машинного обучения, которые предлагает разработчикам Apple, разберем, что нового в этой области компания показала на WWDC18, и попробуем понять, как можно применить это все на практике.

Читать дальше →
Total votes 33: ↑32 and ↓1 +31
Comments 25

Конференция BLACK HAT USA. «Как федералы поймали русского мега-кардера Романа Селезнёва»

Reading time 19 min
Views 66K
Год назад на Гиктаймс активно обсуждалась эта тема:

Российский кардер Роман Селезнёв, сын депутата, приговорён к 27 годам тюрьмы в США

image

Кардер и сын депутата Роман Селезнёв сказал, что с 2008 года работал под защитой ФСБ

В сегодняшнем переводе мы раскроем подробности того, как федералы поймали русского мега-кардера Романа Селезнёва.
Total votes 68: ↑67 and ↓1 +66
Comments 83

Квантовые вычисления и язык Q# для начинающих

Reading time 13 min
Views 77K
Возможно, вы узнали о выпуске пакета средств квантовой разработки Quantum Development Kit и подумали, что это звучит безумно круто… а потом вспомнили, что про квантовую механику почти ничего не знаете. Но ничего страшного. Через 30 минут вы будете знать о кубитах, суперпозиции и квантовой запутанности достаточно, чтобы написать свою первую программу и, что более важно, неплохо понимать, что она делает.

Читать дальше →
Total votes 50: ↑48 and ↓2 +46
Comments 21

Нужно ли бояться несбалансированности классов?

Reading time 3 min
Views 28K

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


Читать дальше →
Total votes 22: ↑19 and ↓3 +16
Comments 4

Смерть микросервисного безумия в 2018 году

Reading time 12 min
Views 100K
Прим. перев.: Этот материал, написанный опытным разработчиком, не задаётся целью похоронить идею микросервисов, как можно подумать, глядя на заголовок. Статья — разумное предупреждение для тех, кто решил, что микросервисы — это «серебряная пуля», которая сама по себе решает все архитектурные и эксплуатационные проблемы. Для демонстрации этого автор собрал и систематизировал популярные проблемы, зачастую встречающиеся в сегодняшних проектах, уже использующих микросервисы или мигрирующих на них.



В последние годы микросервисы стали очень популярной темой. «Микросервисное безумие» выглядит примерно так:

«Netflix хороши в DevOps. Netflix делают микросервисы. Таким образом, если я делаю микросервисы, я хорош в DevOps».
Читать дальше →
Total votes 90: ↑87 and ↓3 +84
Comments 167

Решение, которое нужно принять, чтобы не жалеть о жизни через 30 лет

Reading time 6 min
Views 134K


«Определение ада: «Тот человек, которым вы стали, в свой последний день на земле встретится с человеком, которым вы могли бы стать».
— Автор неизвестен


Читать дальше →
Total votes 90: ↑72 and ↓18 +54
Comments 173

6 строк глубокого обучения

Reading time 9 min
Views 12K
Привет, Хабр! Такое понятие, как «Глубокое обучение», существует с 1986 года, когда его впервые употребила Рина Дехтер. Развитие технология получила в 2006 после выхода публикации Джеффри Хинтона об эффективном предобучении многослойной нейронной сети. Сегодня deep learning часто живет в связке с распознаванием речи, пониманием языка и компьютерным зрением. Под катом вы узнаете про использование алгоритмов глубокого обучения в SQL. Заглядывайте!

Читать дальше →
Total votes 16: ↑15 and ↓1 +14
Comments 1

Переписать базу сообщений ВКонтакте с нуля и выжить

Reading time 9 min
Views 62K
Наши пользователи пишут друг другу сообщения, не зная усталости.

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

При таком объёме данных критически важно, чтобы логика хранения и доступа к ним была построена оптимально. Иначе в один не такой уж и прекрасный момент может выясниться, что скоро всё пойдёт не так.

Для нас этот момент наступил полтора года назад. Как мы к этому пришли и что получилось в итоге — рассказываем по порядку.
Читать дальше →
Total votes 97: ↑94 and ↓3 +91
Comments 91

Transformer — новая архитектура нейросетей для работы с последовательностями

Reading time 7 min
Views 79K

Необходимое предисловие: я решил попробовать современный формат несения света в массы и пробую стримить на YouTube про deep learning.


В частности, в какой-то момент меня попросили рассказать про attention, а для этого нужно рассказать и про машинный перевод, и про sequence to sequence, и про применение к картинкам, итд итп. В итоге получился вот такой стрим на час:



Я так понял по другим постам, что c видео принято постить его транскрипт. Давайте я лучше вместо этого расскажу про то, чего в видео нет — про новую архитектуру нейросетей для работы с последовательностями, основанную на attention. А если нужен будет дополнительный бэкграунд про машинный перевод, текущие подходы, откуда вообще взялся attention, итд итп, вы посмотрите видео, хорошо?


Новая архитектура называется Transformer, была разработана в Гугле, описана в статье Attention Is All You Need (arxiv) и про нее есть пост на Google Research Blog (не очень детальный, зато с картинками).


Поехали.

Читать дальше →
Total votes 64: ↑61 and ↓3 +58
Comments 7

О классификации методов преобразования Фурье на примерах их программной реализации средствами Python

Reading time 7 min
Views 28K

Введение


Публикации по методу Фурье условно можно разделить на две группы. Первая группа так называемых познавательных публикаций, например, [1,2].

Вторая группа публикаций касается применения преобразований Фурье в технике, например, при спектральном анализе [3,4].

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

Задачи публикации


Провести классификацию методов преобразования Фурье на примерах их программной реализации средствами Python. При этом для облегчения чтения использовать формулы только в программном коде с соответствующими пояснениями.

Гармонический анализ и синтез


Гармоническим анализом называют разложение функции f(t), заданной на отрезке [0, Т] в ряд Фурье или в вычислении коэффициентов Фурье по формулам.

Гармоническим синтезом называют получение колебаний сложной формы путем суммирования их гармонических составляющих (гармоник).

Программная реализация
#!/usr/bin/python
# -*- coding: utf-8 -*
from scipy.integrate import quad # модуль для интегрирования
import matplotlib.pyplot as plt # модуль для графиков
import numpy as np # модуль для операций со списками и массивами
T=np.pi; w=2*np.pi/T# период и круговая частота
def func(t):# анализируемая функция
         if t<np.pi:
                  p=np.cos(t)
         else:
                  p=-np.cos(t)
         return p
def func_1(t,k,w):# функция для расчёта коэффициента a[k] 
         if t<np.pi:
                  z=np.cos(t)*np.cos(w*k*t)
         else:
                  z=-np.cos(t)*np.cos(w*k*t)
         return z
def func_2(t,k,w):#функция для расчёта коэффициента b[k] 
         if t<np.pi:
                  y=np.cos(t)*np.sin(w*k*t)
         else:
                  y=-np.cos(t)*np.sin(w*k*t)
         return y
a=[];b=[];c=4;g=[];m=np.arange(0,c,1);q=np.arange(0,2*np.pi,0.01)# подготовка списков для численного анализа
a=[round(2*quad(func_1, 0, T, args=(k,w))[0]/T,3) for k in m]# интеграл для a[k], k -номер гармоники 
b=[round(2*quad(func_2, 0, T, args=(k,w))[0]/T,3) for k in m]# интеграл для b[k], k -номер гармоники
F1=[a[1]*np.cos(w*1*t)+b[1]*np.sin(w*1*t) for t in q]#функции для гармоник
F2=[a[2]*np.cos(w*2*t)+b[2]*np.sin(w*2*t) for t in q]
F3=[a[3]*np.cos(w*3*t)+b[3]*np.sin(w*3*t) for t in q]
plt.figure()
plt.title("Классический гармонический анализ функции \n при t<pi  f(t)=cos(t)  при t>=pi  f(t)=-cos(t)")
plt.plot(q, F1, label='1 гармоника')
plt.plot(q, F2 , label='2 гармоника')
plt.plot(q, F3, label='3 гармоника')
plt.xlabel("Время t")
plt.ylabel("Амплитуда А")
plt.legend(loc='best')
plt.grid(True)
F=np.array(a[0]/2)+np.array([0*t for t in q-1])# подготовка массива для анализа с a[0]/2
for k in np.arange(1,c,1):
         F=F+np.array([a[k]*np.cos(w*k*t)+b[k]*np.sin(w*k*t) for t in q])# вычисление членов ряда Фурье
plt.figure()
P=[func(t) for t in q]
plt.title("Классический гармонический синтез")
plt.plot(q, P, label='f(t)')
plt.plot(q, F, label='F(t)')
plt.xlabel("Время t")
plt.ylabel("f(t),F(t)")
plt.legend(loc='best')
plt.grid(True)
plt.show()

Читать дальше →
Total votes 14: ↑10 and ↓4 +6
Comments 1

Лекции Техносферы. 2 семестр. Методы распределенной обработки больших объемов данных в Hadoop

Reading time 5 min
Views 35K
Предлагаем вашему вниманию новый курс лекций Техносферы. Он представляет собой введение в Hadoop, фокусируясь на проектировании и реализации распределенных алгоритмов, которые могут применяться в различных сферах: обработка текстов, графов, связанных данных и т.п. Также рассматриваются различные компоненты платформы Hadoop и программные модели. Целью курса является знакомство студентов со стеком технологий Hadoop, применяемых для хранения, доступа и обработки больших объемов данных. Преподаватели курса: Алексей Романенко, Михаил Фирулик, Николай Анохин.

Лекция 1. Введение в Big Data и MapReduce


Что такое «большие данные». История возникновения этого явления. Необходимые знания и навыки для работы с большими данными. Что такое Hadoop, где он применяется. Что такое «облачные вычисления», история возникновения и развития технологии. Web 2.0. Вычисление как услуга (utility computing). Виртуализация. Инфраструктура как сервис (IaaS). Вопросы параллелизма. Управление множеством воркеров. Дата-центры и масштабируемость. Типичные задачи Big Data. MapReduce: что это такое, примеры. Распределённая файловая система. Google File System. HDFS как клон GFS, его архитектура.


Читать дальше →
Total votes 34: ↑34 and ↓0 +34
Comments 3

Управление памятью в Python

Reading time 9 min
Views 112K


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


Начнём с размеров объектов. В Python есть много примитивных типов данных: целые числа (int), long (версия int с неограниченной точностью), числа с плавающей запятой (они же числа с двойной точностью, double), кортежи (tuple), строковые значения, списки, словари и классы.

Читать дальше →
Total votes 73: ↑71 and ↓2 +69
Comments 58

Нестандартная кластеризация, часть 3: приёмы и метрики для кластеризации временных рядов

Reading time 16 min
Views 41K
Часть первая — Affinity Propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — Self-Organizing Maps (SOM)
Часть пятая — Growing Neural Gas (GNG)

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

Кластеризация временных рядов — неблагодарное дело. Даже при группировке статических данных часто получаются сомнительные результаты, что уж говорить про информацию, рассеянную во времени. Однако нельзя игнорировать задачу, только потому что она сложна. Попробуем разобраться, как выжать из рядов без меток немного смысла. В этой статье рассматриваются подтипы кластеризации временных рядов, общие приёмы и популярные меры расстояния между рядами. Статья рассчитана на читателя, уже имевшего дело с последовательностями в data science: о базовых вещах (тренд, ARMA/ARIMA, спектральный анализ) рассказываться не будет.

Читать дальше →
Total votes 18: ↑18 and ↓0 +18
Comments 5

Табы, пробелы и ваша зарплата — какая связь?

Reading time 11 min
Views 41K

image


Пару дней назад Дэвид Робинсон опубликовал на Stack Overflow статью с очень провокационным названием: Разработчики, использующие пробелы, зарабатывают больше использующих табуляцию (перевод на Хабре). Автор взял данные из исследования разработчиков, проведённого Stack Overflow, и в самом деле показал, что использование пробелов ассоциируется с более высокими зарплатами, даже принимая в расчёт одинаковый уровень опыта. Так что, нужно вместо табуляций использовать пробелы, чтобы увеличить свою зарплату?

Читать дальше →
Total votes 75: ↑70 and ↓5 +65
Comments 143

Подбор закона распределения случайной величины по данным статистической выборки средствами Python

Reading time 6 min
Views 47K

О чём могут «рассказать» законы распределения случайных величин, если научиться их «слушать»


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

К основным характеристикам законов распределения относятся: наиболее вероятное значение измеряемой величины под названием математическое ожидание (mean); мера рассеивания случайной величины вокруг математического ожидания под названием среднеквадратическое отклонение (std).

Дополнительными характеристиками являются – мера скученности дифференциальной формы закона распределения относительно оси симметрии под названием асимметрия (skew) и мера крутости, огибающей дифференциальной формы под названием эксцесс (kurt). Читатель уже догадался, что приведенные сокращения взяты из библиотек scipy. stats, numpy, которые мы и будем использовать.
Читать дальше →
Total votes 18: ↑14 and ↓4 +10
Comments 3

Библиотеки для глубокого обучения Theano/Lasagne

Reading time 14 min
Views 44K

Привет, Хабр!


Параллельно с публикациями статей открытого курса по машинному обучению мы решили запустить ещё одну серию — о работе с популярными фреймворками для нейронных сетей и глубокого обучения.


Я открою этот цикл статьёй о Theano — библиотеке, которая используется для разработки систем машинного обучения как сама по себе, так и в качестве вычислительного бекэнда для более высокоуровневых библиотек, например, Lasagne, Keras или Blocks.


Theano разрабатывается с 2007 года главным образом группой MILA из Университета Монреаля и названа в честь древнегреческой женщины-философа и математика Феано (предположительно изображена на картинке). Основными принципами являются: интеграция с numpy, прозрачное использование различных вычислительных устройств (главным образом GPU), динамическая генерация оптимизированного С-кода.

Читать дальше →
Total votes 53: ↑53 and ↓0 +53
Comments 11

Сам себе Microsoft

Reading time 3 min
Views 5K
Мы уже рассмотрели способ создания встраиваемого скриптового движка на основе CodeDom.Compiler и класса CSharpCodeProvider. Поставим теперь более амбициозную задачу, где не будем полагаться на готовый компилятор. Будем писать свой собственный генератор, который строит MSIL-код «на лету» и исполняет его.

Для начала, попробуем сложить два числа и распечатать результат как бы на C#, но не пользуясь его языковыми конструкциями:
Читать дальше →
Total votes 16: ↑8 and ↓8 0
Comments 10

Быстрое вычисление факториала — PrimeSwing

Reading time 3 min
Views 15K
Наткнувшись недавно на эту статью, я понял, что редко упоминаются способы вычисления факториала, отличные от банального перемножения последовательных чисел. Нужно эту ситуацию исправить.
Предлагаю рассмотреть «асимптотически наиболее быстрый» алгоритм вычисления факториала!
Читать дальше →
Total votes 21: ↑18 and ↓3 +15
Comments 21

Information

Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Date of birth
Registered
Activity