дата сциентист обучение бесплатно
7 бесплатных курсов по Data Science для начинающих
Большие данные перестали быть просто модным словом и теперь применяются в сферах от IT до ритейла. Самое время начать разбираться в моделях анализа данных, погрузиться в массивы информации и получить опыт в интересном направлении — Data Scientist. Держите курсы, в которых изучите теорию и наберетесь практики. Профи не станете, но первый шаг сделаете.
1. A crash course in Data Science
Курс хочет быстро научить разбираться в работе с большими данными. Здесь не будет кучи технических терминов — всё сосредоточено на понимании общих принципов больших данных: основные термины, роль больших данных в бизнесе, основные инструменты, используемые для работы с большими объемами информации. В общем, хороший курс для знакомства с темой.
2. Building a Data Science Team
На этом курсе речь пойдет о команде аналитики больших данных. Узнаете какие роли должны быть в команде, как управлять такими командами, как подобрать подходящих специалистов и эффективно выстроить рабочий процесс.
3. The Data Scientist’s Toolbox
Время практики! Авторы курса дают обзор типов данных, рассказывают о подходах и методологиях обработки информациии. После вводной теории, вас познакомят с инструментами для работы: Git, R и RStudio — самые популярные штуки, которые помогают обрабатывать массивы информации, и украсят резюме дата майнера!
4. Stepic Contest. Data Science
Еще одно обзорное путешествие в мир больших данных. Крутизна курса заключается в его умении автоматически адаптироваться под любой уровень знаний студента. Stepik недавно запустили самонастраиваемые программы, поэтому советуем скорее оценить на благо знаний и улучшения сервиса 🙂
5. Data Science Essentials
Как собирать данные, подготавливать массивы к обработке, извлекать из них пользу и визуализировать результаты — всему научат на курсе! Будет много практики с применением Microsoft Azure Machine Learning, R и Python. Познакомитесь с процессами передачи данных между хранилищами, поработаете со статистикой больших данных и даже прокачаетесь в машинном обучении.
6. Data Science
Если с программированием у вас не очень — не отчаивайтесь. Не одним R и Python можно проложить путь в Data Science, потому что на помощь придет Excel. В этом курсе узнаете всё про обработку данных с помощью старого доброго Excel.
Самообучение в Data science, с нуля до Senior за два года
Хочу поделиться методами освоения Data science с нуля человеком из другой ИТ специальности. Цель: дать понять, подходит ли Вам эта специальность в принципе, и рассказать про эффективные подходы к самообучению, которые мне помогли (отдельно планирую потом детальные статьи по отдельным темам).
Отличные материалы уже существуют по большинству конкретных тем, я сам по ним учился.
Думаю, многим будут полезны «мета» материалы о том, как выбирать курсы и статьи, по которым учиться. Например, я пересмотрел десятки статей и книг, пробовал много разных он-лайн курсов, но полезной оказалась лишь малая часть всего доступного. Надеюсь, что смогу серьезно сэкономить вам время и помочь достигнуть большего, показав более эффективный путь самообучения.
И важно сказать сразу: я верю, что любой человек с аналитическими способностями и структурным мышлением может стать специалистом по машинному обучению/data science. Еще 4 года назад я сомневался, потеряв веру в свои математические способности из-за преподавателей университета. Теперь верю: основы машинного обучения и минимально необходимую математику сможет выучить любой сильно замотивированный человек.
Когда я понял, что скоро мне стукнет 30 лет, решил уйти в другую сферу и переехать из РФ. В своей сфере (1С) я был карьерно успешен, но стало ясно, что дальнейший рост очень затруднителен и требует выполнять работу, которая мне неинтересна и почти противна.
Через полгода перебора вариантов решил, что Data science мне интереснее всего.
Ещё через год имел достаточную квалификацию и прошёл собеседование на работу в Чехии (оговорка: у меня еще до этого было неплохое знание английского).
Ещё через год стал Senior Data scientist в Vodafone (мой LinkedIn).
Мне помогло то, что до этого я сформировал привычки к самообразованию, а экономность не позволила мне пойти по самому простому пути: найти онлайн курс с именитыми преподами, заплатить им много денег и довериться, что они всему научат лучше всего. В итоге я перебирал много бесплатно доступных книг и курсов (книги часто были найдены на b-ok.org). Из всех курсов и книг отбирал самые лучшие, забрасывая то, что казалось слишком теоретизированными или плохо структурированным.
На основе этих десятков книг и курсов я и сформировал то мнение, которым хочу поделить. Вероятно, существует еще более эффективный и быстрый способ научится этому всему. То, как учился я, было всего-лишь быстрее большинства платных программ, которые я видел, и заодно бесплатным (на многие лучшие англоязычные курсы всегда можно записаться бесплатно; покупал я только книги русских авторов и пару книг, которые иначе не смог найти).
Сначала надо понять, что такое Data science/машинное обучение и подойдет ли оно вам
Потому что если это просто модное слово и вы хотите получать много денег или работать в Гугл, то легче заработать на позиции маркетолога или веб-аналитика, и это тоже достаточно аналитичная работа.
Если вы человек творческий, возможно, разработка интерфейсов (фронтенд, мобильные приложения) вам подойдёт больше.
Если вы от природы аналитик и любите разбираться в данных, но программирование вас не заинтересует, а на изучение всей математики вам не хватает времени, стоит выбрать тот же самый учебный путь! Просто сделать акцент на мнее математических задачах, и не лезть в программироване сложных систем. Аналитики, знающие основы data science, тоже нужны в компаниях.
Важно, чтобы работа зажигала. Без искреннего интереса «грызть» Data science будет тяжело, потому что надо разобраться в куче нюансов, особенно если у вас нет за плечами хороших знаний в статистике, линейной алгебре и мат.анализе.
Как понять, будет ли вам интересно заниматься именно data science?
Мне кажется, что идеально эту роль выполняет книга Datasmart (выше писал сайт, на котором я нашёл её бесплатно). На русский она тоже переведена: «Много цифр. Анализ больших данных при помощи Excel, Джон Форман». Хотя, если вы хотите работать в data science, знание английского необходимо (технический английский выучить намного легче разговорного, и это будет очень полезно для любой работы в ИТ).
Эта книга показывет многие из технических методов Data science на уровне интуиции и даёт сразу достаточно детальное представление о решаемых задачах и где в бизнесе можно применить данные модели.
Если эта книга не вызовет интерес разобраться во всех указанных алгоритмах детальнее, вероятно, работа в data science не для вас.
Если книга интересн вызовет, но вам также хочется больше программировать, скорее всего, вам интересно будет стать machine learning engineer. Разница между data scientist и machine learning engineer в том, что первый должен общаться с людьми и понимать, какую задачу имеет смысл решать, а второй должен уметь состыковать программы с «искусственным интеллектом» с другими ИТ системами, мобильными телефонами или требованиями обрабатывать огромные объемы данных.
Что учить
Если вы решили, что готовы «грызть гранит науки», то в образовании специалиста data science есть два кита:
Непосредственные методы Data science, которые стоят на трёх математических черепахах: теории вероятностей и статистике, линейной алгебре и основах мат.анализа (только основах, там требуется минимум сверх школьного курса «алегбра и начало анализа»). Кстати, вся эта математика далеко не так сложна. Проблема в том, что её плохо и неинтересно объясняют во многих вузах. Позже поделюсь советами, как её можно легче освоить.
Программирование на Python (+SQL и подобные), которое позволит применить все изученные методы с помощью логичных и простых в своей сути библиотек готовых функций.
Даже примерный учебный план для изучения методов Data science требует отдельного поста. Ниже напишу чуть подробнее про Python и SQL
Английский необходим!
Принципы эффективного обучения
Программирование: что и как учить?
Что такое SQL и зачем его учить?
SQL является стандартом для получения данных в нужном виде из разных баз данных. Это тоже своеобразный язык программирования, который дополнительно к своему основному языку используют многие программисты. Большинство самых разных баз данных использует один и тот же язык с относительно небольшими вариациями.
Как учить SQL:
Наберите в Гугле «sql tutorial» и начните учиться по первой же ссылке. Если она вдруг окажется платной, выберете другую. По SQL полно качественных бесплатных курсов.
На русском языке тоже полно курсов. Выбирайте бесплатные.
На изучение достаточно всего лишь от 10 часов (общее понимание), до 20 часов (уверенное владение большей частью всего необходимого).
Почему именно Python?
У всех других языков программирования какие-либо специализированные библиотеки для машинного обучения есть только в зачаточном состоянии.
Как учить Python
Прочитать основы и пройти все упражнения с этого сайта можно за 5-40 часов, в зависимости от вашего предыдущего опыта.
После этого варианты (все эти книги есть и на русском):
Learning Python, by Mark Lutz (5 издание). Существует и на русском.
Есть много книг, которые сразу обучают использованию языка в практических задачах, но не дают полного представления о детальных возможностях языка.
Эта книга, наоборот, разбирает Python досконально. Поэтому по началу её чтение будет идти медленнее, чем аналоги. Но зато, прочтя её, вы будете способны разобраться во всём.
Я прочёл её почти целиком в поездах в метро за месяц. А потом сразу был готов писать целые программы, потому что самые основы были заложены в pythontutor.ru, а эта книга детально разжевывает всё.
В качестве практики берите, что угодно, когда дочитаете эту книгу до 32 главы, и решайте реальные примеры (кстати, главы 21-31 не надо стараться с первого раза запоминать детально. Просто пробежите глазами, чтобы вы понимали что вообще Python умеет).
Не надо эту книгу (и никакую другую) стараться вызубрить и запомнить все детали сразу. Просто позже держите её под рукой и обращайтесь к ней при необходимости.
Прочитав эту книгу, и придя на первую работу с кучей опытных коллег, я обнаружил, что некоторые вещи знаю лучше них.
Python Crash Course, by Eric Matthes
Automate the Boring Stuff with Python
Книга хороша примерами того, что можно делать с помощью Python. Рекомендую просмотреть их все, т.к. они уже похожи на реальные задачи, с которыми приходится сталкиваться на практике, в том числе специалисту по анализу данных.
Какие трудозатраты?
Путь с нуля до уровня владения Python, на котором я что-то уже мог, занял порядка 100ч. Через 200ч я уже чувствовал себя уверенно и мог работать над проектом вместе с коллегами.
Следующие статьи по данной теме
Для желающих могу выступить в роли ментора
Как самостоятельно выучиться на дата-саентиста — адаптированная подборка
Меня зовут Айра, я веду блог про математику, продукты и ML, делаю проекты в DS/ML, а также курсы по созданию ML-проектов. От своей аудитории блога и знакомых часто получаю вопросы в духе «Cтоит ли тратить деньги на тот или иной дорогой курс с codename «Стань DS за два месяца» или все же выучиться на дата-саентиста самостоятельно и бесплатно, и в таком случае, с чего начать?»
Недавно собрала ответ на этот вопрос достаточно развернуто, на мой взгляд, чтобы поделиться им с широкой аудиторией. Не все платные курсы плохие (хотя большинство — да — из-за механизмов отбора, продаж и слабой программы), но о них напишу отдельно. Мне кажется, нужно учитывать больше персонализированных параметров для того, чтобы грамотно выбирать хороший курс за деньги.
Во-первых, в список вошли бесплатные онлайн-курсы и ресурсы для самостоятельного обучения, которые проходила сама или советует профессиональное сообщество аналитиков и дата-саентистов (часто упоминающиеся в ODS.ai), где не нужно проходить какой-то отбор или быть ограниченным офлайн-посещением.
Во-вторых, конечно, это далеко не полный список онлайн-курсов, который вы можете встретить, зато в него попали лучшие курсы от сильных математических и Computer Science-школ мир и другие распространенные ресурсы среди профи из того, что я смогла отфильтровать на свой вкус.
В-третьих, начну с короткого списка, с которого, как мне кажется, стоит начинать обучение предмету, и он идет сразу же следующим абзацем.
С чего советую начать, чтобы тратить время эффективно?
Предполагая, что начинающий дата-саентист уже прошел подготовительные курсы а-ля гарвардский CS50 по основам программирования, pythontutor.ru или курс на Stepik от Института Биоинформатики, посоветую несколько шагов, которые должны стать твердой базой. Далее ссылки все полные, чтобы было легче копировать:
Зарегистрироваться в самом популярном в СНГ профессиональном slack-сообществе Open Data Science ODS.ai, вступить в как можно больше чатов, в том числе про менторство, обучение и карьеру и общаться с местными, чтобы расширить свой кругозор относительно работодателей, требований к прохождению интервью, к позиции и их различиях в разных компаниях и др, найти хороших наставников, тк. такие в сообществе есть!
Пройти вводный курс «Математика и Python для анализа данных» на Coursera — платный, недорогой и хороший. www.coursera.org/learn/mathematics-and-python
По программированию — пройти в leetcode.com все релевантные упражнения: это бесплатные или недорогие в премиальной версии в соотношении цена/качество тренажеры (в нем есть в том числе упражнения на интервью в FAANG).
Пройти mlcourse.ai — это открытый курс машинного обучения от ODS. Авторы смогли разработать курс машинного обучения с балансом между теорией и практикой, когда в лекции вы разбираете достаточно подробно математику, а затем упражняетесь сначала в блокноте, затем на Kaggle.
Для обучения решению разнообразных задач и оптимизации кода — участвовать в соревнованиях по анализу данных и машинному обучению на платформе kaggle.com.
Математика для DS/ML
Приятный курс Стэнфорда по DS «Introduction to Statistics» www.coursera.org/learn/stanford-statistics
Коротенький интерактивный курс по теории вероятностей и математической статистике «Seeing Theory» seeing-theory.brown.edu/
Хороший вводный курс по математике для анализа данных, более объёмный «Специализация Математика для анализа данных:. Можно послушать только интересную тему: дискретная математика / линейная алгебра / математический анализ / теория вероятностей. www.coursera.org/specializations/maths-for-data-analysis
Довольно подробная и читаемая книга по теорверу и матстату «Dekking, A Modern Introduction to Probability and Statistics» cis.temple.edu/
Python&SQL для DS/ML
Упомянутый выше бесплатный тренажер по Python с нуля: pythontutor.ru/
Отличный курс по инструментам по DS от IBM «Специализация Data Science Fundamentals with Python and SQL» www.coursera.org/specializations/data-science-fundamentals-python-sql
Упомянутый выше русский курс по питону и математике (платный, недорогой и хороший) «Математика и Python для анализа данных (Coursera)» www.coursera.org/learn/mathematics-and-python
Упомянутый выше https://leetcode.com/: пройти все релевантные упражнения, это бесплатные или недорогие в премиальной версии в соотношении цена/качество тренажеры (в нем есть в том числе упражнения на интервью в FAANG).
Начальные курсы по ML
Как бы этот курс не ругали из-за устаревшего языка программирования Octave (на котором пишут на Matlab), на мой вкус — это пока что самый простой и понятный курс по ML. Машинное обучение (Coursera) https://www.coursera.org/learn/machine-learning — стэнфордский курс по машинному обучению от Andrew Ng
mlcourse.ai — это открытый курс машинного обучения от ODS. Авторы смогли разработать курс машинного обучения с балансом между теорией и практикой, когда в лекции вы разбираете достаточно подробно математику, а затем упражняетесь сначала в блокноте, затем на Kaggle.
Более продвинутые курсы по ML
Если хочется погрузиться в математические доказательства методов машинного обучения, то есть прекрасные ШАДовские лекции К.В. Воронцова: плейлист «Курс «Машинное обучение» 2019” на YouTube-канале “Компьютерные науки», www.youtube.com/watc? v=SZkrxWhI5qM&list=PLJOzdkh8T5krxc4HsHbB8g8f0hu7973fK&index=2
Также хорош ежегодный гарвардский курс «Advanced Topics in Data Science CS109B». harvard-iacs.github.io/2020-CS109B/
Или курс по углубленным алгоритмам Advanced ML от ВШЭ: «Специализация Продвинутое машинное обучение» www.coursera.org/specializations/aml
Deep learning
(Мне кажется, можно пройти один курс из списка, а остальные смотреть на предмет дополнений)
Рекомендованный Стэнфордовский курс по DL «CS231n: Convolutional Neural Networks for Visual Recognition» cs231n.github.io/
Хороший курс от Университета Карнеги—Меллон «11-785 Introduction to Deep Learning» deeplearning.cs.cmu.edu/F21/index.html
Курс от MIT: «Practical Deep Learning for Coders» https://course.fast.ai/
ШАДовский курс по глубокому обучению доступен в github: «Practical_DL» github.com/yandexdataschool/Practical_DL
Бесплатные классные курсы от МФТИ: dlschool.org/
Также есть курс по DL у ODS.ai, который тоже советуют проходить в самом сообществе: «Deep Learning на пальцах» dlcourse.ai/
А еще есть курс у Samsung AI Research Center на Stepik.org stepik.org/course/50352/info
Natural Language Processing
Стэнфордовский «CS224n: Natural Language Processing with Deep Learning » web.stanford.edu/class/cs224n/
Второй курс у Samsung AI Research Center на Stepik.org https://stepik.org/course/54098/promo
Reinforcement Learning & Self-driving cars
От Deepmind «RL Course by David Silver» www.youtube.com/watc? v=2pWv7GOvuf0
Австралийский курс StarAi «Deep Reinforcement Learning Course » www.starai.io/course/
Data Engineering & MLOps
Бесплатный курс по DE от Дмитрия Аношина, дата-инженера из Microsoft, ex-Amazon: Getting start with Data Engineering and Analytics https://datalearn.ru/ (курс готовится in progress)
Соревнования
Ну, и для обучения решению разнообразных задач и оптимизации кода — участвуйте в Kaggle. https://kaggle.com/
Кроме Kaggle, есть еще несколько соревнований:
План обучения Data scientist на 6 месяцев ( только из бесплатных курсов на русском)
В этом видео, мы разберем план обучения, по которому я бы учился data science, если бы начинал сейчас. Все ссылки на курсы ниже или в описании к видео. Все ресурсы на русском языке и абсолютно бесплатные.
Основы линейной алгебры
на английском, но есть субтитры на русском
Введение в DS и машинное обучение:
Плейлист с лекциями на русском.
Более новые лекции на английском и домашние задания на самом сайте mlcourse.ai
Учебные соревнования на kaggle:
Набиваем руку на kaggle:
Сайт с шаблонами для резюме:
Искусственный интеллект
422 поста 5.1K подписчиков
Правила сообщества
Здесь вы можете свободно создавать посты по теме Искусственного интеллекта. Добро пожаловать 🙂
— Делиться вопросами, мыслями, гипотезами, юмором на эту тему.
— Делиться статьями, понятными большинству аудитории Пикабу.
— Делиться опытом создания моделей машинного обучения.
— Рассказывать, как работает та или иная фиговина в анализе данных.
— Век жить, век учиться.
I) Невостребованный контент
I.1) Создавать контент, сложный для понимания. Такие посты уйдут в минуса лишь потому, что большинству неинтересно пробрасывать градиенты в каждом тензоре реккурентной сетки с AdaGrad оптимизатором.
I.2) Создавать контент на «олбанском языке» / нарочно игнорируя правила РЯ даже в шутку. Это ведет к нечитаемости контента.
II) Нетематический контент
II.1) Создавать контент, несвязанный с Data Science, математикой, программированием.
II.2) Создавать контент, входящий в противоречие существующей базе теорем математики. Например, «Земля плоская» или «Любое действительное число представимо в виде дроби двух целых».
II.3) Создавать контент, входящий в противоречие с правилами Пикабу.
III) Непотребный контент
Спасибо большое. Как раз подумывал, что неплохо бы глянуть основы «высшей» математики, ибо соответствующего образования нет.
А можете обновить ссылочку на курс по линейной алгебре на Ютуб?
Товарищ автор, нашел несколько годных постов насчет Roadmap, мне очень понравился твой пост. Беру его для себя на вооружение.
Скажи, пожалуйста, в каком городе нашел работу в DS в итоге? Когда это было? На какую ЗП смог вначале рассчитывать? Было ли уже продвижение?
Шагаю в эту область, но придется искать работу с оглядкой на свою маленькую семью (мне 27 почти) и на мой текущий доход, город НН. Наверное в МСК придется перебираться за лучшей долей.
Опоздали, индийцы сбили рейты. Теперь ты зубришь математику до посинения, но заработаешь меньше чем на javascript
Плюс за дубляж видео текстом. Заодно видим, что все ссылки порублены движком.
Лежит не линейка, а нейронки. Линейка, может быть, эта? https://stepik.org/course/2461/
Почему дата, когда дэйта?
Просто тупо писнес.. Просто тупо..
Как воссоздать изображение всего по нескольким пикселям
Эта статья дает возможность познакомиться с такой методикой получения и восстановления сигнала, как Compressive Sensing.
Множество всех возможных изображений 2 на 2 с цветами, закодированными одним битом
Пространство изображений огромно, невероятно огромно, но при этом очень мало. Задумайтесь об этом на минуту. Из сетки размером всего 8 на 8 пикселей можно создать 18 446 744 073 709 551 616 различных чёрно-белых изображений. Однако из этих 18 квинтиллионов изображений очень немногие покажутся осмысленными человеческому взгляду. Большинство изображений, по сути, выглядит как QR-коды. Те, которые покажутся человеку осмысленными, принадлежат к тому множеству, которое я называю естественными изображениями. Они представляют крошечную долю пространства изображений 8 на 8. Если мы рассмотрим мегапиксельные изображения, то доля естественных изображений становится ещё меньше, почти ничтожной, однако содержит любое изображение, которое можно придумать. Так чем же эти естественные изображения так уникальны? И можем ли мы использовать эту фундаментальную разницу в собственных интересах?
Рассмотрим два представленных ниже изображения. Оба изображения имеют размер 512 на 512 пикселя. Если вычислить гистограмму значений пикселей, то можно понять, что эти распределения идентичны. И это на самом деле так. Левое изображение такое же, как правое, только пиксели перемешаны случайным образом. Тем не менее между ними есть фундаментальное отличие. Одно выглядит как «снег» на экране старого телевизора, а другое — это лицо человека.
Слева: случайное изображение. Справа: классическое тестовое изображение женщины с тёмными волосами. Оба изображения принадлежат к пространству изображений 512 на 512
Чтобы понять фундаментальную разницу между этими изображениями, нам нужно покинуть пространство пикселей и войти в мир частотного диапазона. С точки зрения математики, преобразование Фурье — это линейное сопоставление пиксельного описания изображения с описанием в виде суммы синусов и косинусов, колеблющихся в двух измерениях. Вместо задания изображения значениями, принимаемыми каждым пикселем, мы задаём его по амплитудам каждого из составляющих его двухмерных синусов и косинусов.
Описание этих двух изображений в пространстве Фурье представлено ниже. Для отображения величины коэффициента Фурье использована логарифмическая шкала. Разница между двумя изображениями теперь очевидна. Одно имеет гораздо больше ненулевых коэффициентов Фурье, чем другое. На языке математики говорится, что естественное изображение является разреженным по базису Фурье. Именно разреженность отличает естественные изображения от случайных. Давайте же используем эту разницу с пользой для себя!
Амплитуда преобразований Фурье обоих изображений. Использована логарифмическая шкала
Воссоздание изображений по нескольким пикселям, задача с высокой степенью неопределённости
Записано всего 10% пикселей
Рассмотрим следующую ситуацию: по какой-то неизвестной причине большинство фотодатчиков камеры оказалось неисправным. Скопировав на компьютер только что сделанную фотографию своей жены (или матери, или друга), вы обнаружили, что изображение получилось таким, как показано выше. Можно ли как-то восстановить изображение?
Допустим, что мы точно знаем, какие фотодатчики исправны. Обозначив как x ∊ ℝⁿ неизвестное изображение (где n — общее количество пикселей, и мы считаем, что оно представлено в виде вектора), а как y ∊ ℝᵐ ненулевые яркости пикселей, зафиксированные датчиками, мы можем записать
Здесь C — это разреженная матрица измерений m × n. Все элементы, соответствующие неисправным фотодатчикам, равны нулю, и она содержит только m ненулевых элементов, соответствующих исправным датчикам. Следовательно, наша задача — выяснить, каким был x исходного изображения, учитывая, что мы наблюдаем только несколько его пикселей.
С точки зрения математики, это задача с высокой степенью неопределённости. У нас гораздо больше неизвестных, чем уравнений. Эта задача имеет бесконечное количество решений. Значит, вопрос сводится к тому, какое решение из бесконечного множества является тем, которое мы ищем. Естественным способом решения такой задачи было бы принятие того, что решение имеет наименьшую норму ℓ₂. Это можно формализовать как следующую задачу оптимизации:
решение которой задаётся так:
Матрица C соответствует измерениям единичных пикселей, её строки получены из единичной матрицы n × n. В такой ситуации решение задачи оптимизации не особо нам поможет, поскольку оно вернёт только повреждённое изображение (произведение матриц справа сводится к Cᵀ). Очевидно, что это нам не подходит. Но можно ли найти решение получше?
Используем разреженность в спектральном пространстве
При обсуждении уникальных особенностей естественных изображений мы увидели, что они являются разреженными в пространстве Фурье, поэтому давайте этим воспользуемся. Обозначив как Ψ отображение матрицы n × n из пространства Фурье в пространство пикселей, мы получим следующий вид уравнения измерений:
где s — преобразование Фурье x (т. е. x = Ψs). Это по-прежнему задача с высокой степенью неопределённости, но теперь у нас есть дополнительная информация о решении, которое мы ищем. Мы знаем, что оно должно быть разреженным. Введя псевдонорму ℓ₀ для s (т. е. его число ненулевых элементов), мы сможем сформулировать следующую задачу оптимизации:
К сожалению, это задача комбинаторики, очень быстро становящаяся нерешаемой. Чтобы найти её решение, потребуется проверить все возможные сочетания. К счастью в своей революционной работе 2006 года Канде et al. [1, 2] показал, что при условии разумных допущений решение изложенной выше задачи можно получить (с высокой вероятностью) при помощи решения более простой задачи:
Здесь норма ℓ₁ — это сумма абсолютных значений вектора s. Сегодня хорошо известно, что использование нормы ℓ₁ кроме превращения задачи оптимизации в выпуклую, склонно отдавать предпочтение разреженным решениям. Несмотря на свою выпуклость, эту задачу всё равно может быть достаточно сложно решить на стандартном компьютере. В дальнейшем мы используем более ослабленную версию, задаваемую следующим образом:
где λ — это задаваемый пользователем параметр, управляющий равновесием между соответствием ограничениям и необходимой разреженностью решения. Эту задачу оптимизации называют Basis Pursuit Denoising. При помощи проксимальных операторов она решается чрезвычайно быстро. Ниже представлена реализация на Julia с использованием StructuredOptimization.jl.
Кроме того, мы можем воспользоваться тем фактом, что для спектральных преобразований произведение матрицы и вектора Ψs при помощи алгоритма быстрого преобразования Фурье можно вычислить за O(n log n) операций вместо O(n²).
Хотя до сих пор мы предполагали, что Ψ является преобразованием Фурье, в этом фрагменте кода мы использовали косинусное преобразование, являющееся более эффективным преобразованием для изображений. Теперь у нас есть всё необходимое, поэтому давайте вернёмся к исходной задаче. На изображении ниже сравнивается истинное изображение с его реконструкцией при помощи ℓ₁.
Слева: оригинал изображения. Справа: изображение, воссозданное при помощи compressive sensing на основании данных всего 10% пикселей
Даже несмотря на то, что исправно работало всего 10% фотодатчиков камеры, формулировка этой задачи восстановления изображения в рамках Compressed Sensing позволяет нам воссоздать достаточно точное приближение к тому, каким было исходное изображение! Очевидно, что оно всё равно неидеально, однако учитывая обширность пространства изображений и бесконечное количество решений нашей задачи, нужно признать, что результат довольно хорош!
Методика Compressed Sensing совершила революцию в сфере обработки сигналов. Если мы заранее знаем, что сигнал, с которым работаем, разрежен по указанному базису, то compressed sensing позволяет восстановить его по гораздо меньшему количеству сэмплов, чем предполагается по теореме выборки Найквиста-Шеннона. Кроме того, она позволяет значительно сжимать данные непосредственно на этапе получения, уменьшая таким образом необходимый объём хранилища данных. Также Compressed Sensing привела к возникновению неожиданных новых технологий, например, однопиксельной камеры, разработанной Университетом Райса, или новых техник обработки для создания визуализаций МРТ в медицине. Я не сомневаюсь, что в ближайшие несколько лет мы станем свидетелями множества новых способов применения этой методики.
Compressed sensing — это гораздо более глубокая область математики, чем можно судить по этому ознакомительному посту. Существует ещё множество не рассмотренных нами вопросов, например:
— Каково наименьшее количество необходимых измерений?
— Могут ли некоторые измерения быть информативнее других?
— Как выбирать эти измерения, имея базис Ψ?
— Существуют ли другие нормы, лучше подходящие для изображений?
Для ответа на эти вопросы потребуется гораздо больше математики, чем можно представить в посте. Если вы хотите знать больше, то крайне рекомендую изучить оригиналы статей, ссылки на которые я указал в конце. Также стоит изучить потрясающий веб-сайт Numerical Tours Габриеля Пейре или последнюю книгу Брантона и Кутца [3], а также соответствующий канал на YouTube (здесь и здесь).
Ссылки на научные работы
[1] Candès E., Romberg J., Tao T. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied mathematics. 58(8): 1207–1223. 2006.
[2] Candès E. Compressed sensing. IEEE Transactions on Information Theory. 52(4): 1289–1306. 2006.
[3] Brunton S. L. and Kutz J. N. Data-driven science and engineering: machine learning, dynamical systems, and control. Cambridge University Press, 2019.