Что такое информация, как найти скрытый в ней смысл, что вообще есть смысл? В большинстве толкований информацию сопоставляют с сообщением или с данными, используя эти слова как синонимы. Сообщение обычно подразумевает конкретную форму. Например, устная речь, текстовое послание, сигнал светофора и тому подобное. Термин «сообщение» чаще используют, когда  говорят об информации в связи с ее передачей. Под данными обычно подразумевают информацию, для которой определена форма ее хранения или передачи. Например, мы говорим о данных, когда упоминаем записи в базе данных, массивы в памяти компьютера, сетевые пакеты и тому подобное. Сам термин «информация» мы предпочитаем использовать, когда  нет необходимости заострять внимание на способе ее передачи или  форме представления.

Информация, чтобы быть использованной, должна получить интерпретацию. Например, красный сигнал светофора можно интерпретировать как запрет ехать, улыбку как сигнал хорошего расположения и тому подобное. Конкретная интерпретация называется смыслом информации. По крайней мере, такой трактовки придерживается международная организация по стандартизации: «knowledge concerning objects, such as facts, events, things, processes, or ideas, including concepts, that within a certain context has a particular meaning».

Интро

Этой статьей я начинаю цикл статей об известных и не очень структурах данных а так же их применении на практике.

В своих статьях я буду приводить примеры кода сразу на двух языках: на Java и на Haskell. Благодаря этому можно будет сравнить императивный и функциональный стили программирования и увидить плюсы и минусы того и другого.

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

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

Пожалуй, во время теста не особо интересно спрашивать у машины: когда была Куликовская битва. Гораздо интереснее что она скажет, например, о том: зачем мы нажимаем сильнее на кнопки пульта, у которого садятся батарейки?

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

Первая статья цикла

Интро

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

Когда с нами что-то происходит наш мозг фиксирует это, создавая воспоминания. Изменения, которые при этом происходят с мозгом, принято называть энграммами или следами памяти.

Вполне естественно, что понимание того, как выглядят следы памяти – основной вопрос изучения мозга. Без этого невозможно построить никакую биологически достоверную модель его работы. Понимание строения памяти непосредственно связано с пониманием того, как мозг кодирует информацию и как он ей оперирует. Все это, пока, — неразгаданная загадка.

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

На презентации Google I/O 15, компания Google представила новую версию библиотеки поддержки которая реализует несколько компонентов, сильно связанных со спецификациями Material Design, среди этих компонентов вы можете найти новые типы ViewGroup такие как AppbarLayout, CollapsingToolbarLayout и CoordinatorLayout.

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

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

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

Автомат, который мы описываем обладает памятью. Точнее, памятью обладают все его элементы. Память элемента специфична. Единственное, что видит элемент автомата – это узор, составленный из активности своих соседей. Единственное, как элемент может отреагировать на тот или иной узор – это либо самому стать активным, либо, наоборот, выключиться. Память элемента – это набор запомненных им узоров с указанием, как на них реагировать: включаться или выключаться.

Начнем разговор о мозге с несколько отвлеченной темы. Поговорим о клеточных автоматах. Клеточный автомат – это дискретная модель, которая описывает регулярную решетку ячеек, возможные состояния ячеек и правила изменений этих состояний. Каждая из ячеек может принимать конечное множество состояний, например, 0 и 1. Для каждой из ячеек определяется окрестность, задающая ее соседей. Состояние соседей и собственное состояние ячейки определяют ее следующее состояние.
Наиболее известный клеточный автомат – это игра «Жизнь». Поле в игре «Жизнь» состоит из ячеек. Каждая ячейка имеет восемь соседей. Задается начальная комбинация. Затем начинается смена поколений. Если у занятой ячейки два или три занятых (живых) соседа, то ячейка продолжает жить. Если соседей меньше 2 или больше 3, то ячейка умирает. Когда у пустой ячейки оказывается ровно 3 соседа в ней зарождается жизнь. Задав произвольную начальную комбинацию можно пронаблюдать ее эволюцию.

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

В свое время на Хабре был опубликован цикл статей «Логика мышления». С тех пор прошло два года. За это время удалось сильно продвинуться вперед в понимании того, как работает мозг и получить интересные результаты моделирования. В новом цикле «Логика сознания» я опишу текущее состоянии наших исследований, ну а попутно попытаюсь рассказать о теориях и моделях интересных для тех, кто хочет разобраться в биологии естественного мозга и понять принципы построения искусственного интеллекта.

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

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

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

Kaggle — это платформа для проведения конкурсов по машинному обучению. На Хабре частенько пишут про неё: 1, 2, 3, 4, и.т.д. Конкурсы на Kaggle интересные и практичные. Первые места обычно сопровождаются неплохими призовыми (топовые конкурсы — более 100к долларов). В последнее время на Kaggle предлагали распознавать:

• Диабет по сетчатке глаза
• Фотографии со спутников и их порядок
• Одинаковые рекламные объявления

И многое-многое другое.

Мне давно хотелось попробовать, но что-то всё время мешало. Я разрабатывал много систем, связанных с обработкой изображений: тематика близка. Навыки более лежат в практической части и классических Computer Vision (CV) алгоритмах, чем в современных Machine Learning техниках, так что было интересно оценить свои знания на мировом уровне плюс подтянуть понимание свёрточных сетей.

И вот внезапно всё сложилось. Выпало пару недель не очень напряжённого графика. На kaggle проходил интересный конкурс по близкой тематике.Я обновил себе комп. А самое главное — подбил vasyutka и Nikkolo на то, чтобы составить компанию.

Сразу скажу, что феерических результатов мы не достигли. Но 18 место из 1.5 тысяч участников я считаю неплохим. А учитывая, что это наш первый опыт участия в kaggle, что из 3х месяц конкурса мы участвовали лишь 2.5 недели, что все результаты получены на одной единственной видеокарте — мне кажется, что мы хорошо выступили.

О чём будет эта статья? Во-первых, про саму задачу и наш метод её решения. Во-вторых, про процесс решения CV задач. Я писал достаточно много статей на хабре о машинном зрении(1,2,3), но писанину и теорию всегда лучше подкреплять примером. А писать статьи по какой-то коммерческой задаче по очевидным причинам нельзя. Теперь наконец расскажу про процесс. Тем более что тут он самый обычный, хорошо иллюстрирующий как задачи решаются. В-третьих, статья про то, что идёт после решения идеализированной задаче в вакууме: что будет когда задача столкнётся с реальностью.

Недавно ZlodeiBaal писал о достижениях в сверточных нейронных сетях (CNN) (и, кстати, тут же успешно настроил и обучил сеть для поиска области автомобильного номера).
А я хочу рассказать про принципиально иную и, наверное, более сложную модель, которую сейчас развивает Алексей Редозубов (@AlexeyR), и про то, как мы, конечно проигнорировав некоторые важные элементы, и ее применили для распознавания автомобильных регистрационных знаков!

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

Статья-гипотеза. Описанное нигде не было реализовано, хотя, в принципе, ничто не мешает запилить такое в Фантоме.

Эта идея пришла мне в голову очень давно и даже где-то была мной описана. Триггер к тому, чтобы её описать сегодня — обсуждение сетевых драйверов Линукса в комментариях к Анатомии драйвера.

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

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

То есть хотелось бы такого вызова функции, который при необходимости можно конвертировать в старт нити. Но по цене вызова функции, если нить реально не оказалась нужна.

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

Как это.

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

Что такое LLVM?

LLVM — это по-настоящему удобный для разборки и сборки «ранний» компилятор для таких традиционных языков программирования, как C и C++.

LLVM настолько хорош, что считается «больше, чем просто компилятором» (это динамический компилятор, он работает с языками, не относящимися к семейству C, он представляет собой новый формат доставки для App Store и т. д. и т. п.). Все перечисленное верно, но для нашей статьи важно лишь приведенное выше определение.

LLVM имеет несколько ключевых отличий от других компиляторов:

• Главное новшество — промежуточное представление (ПП). LLVM работает с ПП, которое действительно можно прочитать (если вы умеете читать ассемблерный код). Возможно, кому-то это не покажется столь уж большим откровением, однако это свойство очень важно. ПП других компиляторов обычно имеют настолько сложную структуру, что их невозможно записать вручную, трудно понять и использовать.

Я стараюсь чередовать статьи про разработку ОС вообще и специфические для ОС Фантом статьи. Эта статья — общего плана. Хотя, конечно, я буду давать примеры именно из кода Фантома.

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

Начнём с того, что есть два довольно мало связанных модуля — собственно подсистема переключения задач (контекстов) и подсистема шедулинга. Вторую мы сегодня обсуждать почти не будем, просто опишем кратко.

Шедулер — это функция, которая отвечает на вопрос «какой нити отдать процессор прямо сейчас». Всё. Простейший шедулер просто перебирает все нити (но, конечно, готовые к исполнению, не остановленные) по кругу (RR алгоритм). Реальный шедулер учитывает приоритеты, поведение нити (интерактивные получают больше, чем вычислительные), аффинити (на каком процессоре нить работала в прошлый раз) и т.п., при этом умеет сочетать несколько классов приоритетов. Типично это класс реального времени (если есть хотя бы одна нить этого класса — работает она), класс разделения времени и класс idle (получает процессор только если два предыдущих класса пустые, то есть в них нет нитей, готовых к исполнению).

На сём пока про шедулер закончим.

Перейдём к собственно подсистеме, которая умеет отнять процессор у одной нити и отдать его другой.

На прошлой неделе в компании Clarifai мы формально анонсировали нашу модель распознавания непристойного контента (NSFW, Not Safe for Work).

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

---

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

Привет всем. Продолжу о Фантоме. Для понимания полезно прочесть статью про персистентную оперативку, а так же общую статью про Фантом на Открытых Системах. Но можно и так.

Итак, мы имеем ОС (или просто среду, не важно), которая обеспечивает прикладным программам персистентную оперативную память, и вообще персистентную «жизнь». Программы живут в общем адресном пространстве с управляемыми (managed) пойнтерами, объектной байткод-машиной, не замечают рестарта ОС и, в целом, счастливы.

Очевидно, что такой среде нужна сборка мусора. Но — какая?

Есть несколько проблем, навязанных спецификой.

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

Во-вторых, нас категорически не устраивают stop the world алгоритмы. Если для обычного процесса остановка в полсекундны может быть приемлема, то для виртуальной памяти, которая, большей частью, на диске, это будут уже полчаса, а то как бы не полсуток!

Наконец, если считать, что полная сборка мусора составляет полсуток, нас, наверное, это не устроит — было бы здорово иметь какой-то быстрый процесс сбора мусора, хотя бы и не полностью честный, пусть он часть мусора теряет, но если удаётся быстро вернуть 90% — уже хорошо.

Тут нужна оговорка. Вообще говоря, в системе, которая располагает парой терабайт виртуальной памяти, это не так уж критично — даже если не делать освобождение памяти полсуток, возможно, не так много и набежит — ну, например, истратится 2-3, ну 5 гигабайт, ну даже и 50 гигабайт — не жалко, диск большой.

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

Ок, итого у нас две задачи.

Встала передо мной задача – сделать постинг ссылок из Андроида в пару-тройку соцсетей. Причем, максимально простой и легкий – чтобы не плодить сущности и как можно меньше заморачиваться с токенами, сессиями и прочая. Задача, действительно, минимум – только размещение ссылки в собственном аккаунте пользователя. Если к ссылке можно легко добавить описания или картинки – сделать, но не упираться.

В силу разных причин были выбраны Facebook, Vkontakte и Google+. Планировала добавить Twitter, но его Fabric к тому времени еще не вышел, а использовать стороннюю библиотеку не хотелось (см. п.2 ниже). Позже добавлю.

В итоге, задача для этих трех соцсетей получилась следующей:

1. Максимально простой программный интерфейс постинга ссылок.
2. Использование только нативных SDK (из тех соображений, что эти знания пригодятся в дальнейшем).
3. Минимум кода – только самое необходимое для работы.
4. Работать все должно вне зависимости от наличия у пользователя установленного клиента соцсети. Но если он есть – использовать диалоговые окна клиента.
5. Пользователю должно выводиться сообщение об успешном или нет размещении записи.
6. Должна быть возможность программно реагировать на успешное размещение записи.

Прямо сейчас в Кремниевой долине проходит GPU Technology Conference. Это важнейшее событие для всех тех, кто занимается технологиями параллельных вычислений, нейронными сетями и искусственным интеллектом. Текущий 2016 год особенный для этой конференции. То к чему готовились и шли долгое время именно сейчас приобретает законченные формы. Причем, как и предопределено развитием технологий, прорыв происходит сразу по всем направлениям:

• нейронные сети, построенные на обучении с подкреплением, берут следующую высоту после шахмат и побеждают человека в го, игру, которая превосходит шахматы по своей комбинаторной сложности;
• беспилотные автомобили проходят проверку на дорогах и доказывают свою состоятельность;
• платформы искусственного интеллекта от IBM, Amazon, Google и Microsoft готовы для интеграции в реальный мир;
• виртуальная и дополненная реальность уже реализованы и готовы к масштабному внедрению от Oculus, HTC, Sony и Samsung;
• решения на базе HPC (High Performance Computing) интегрируются практически повсеместно.

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

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

В прошлом году я протестировал 198 аккумуляторов (44 модели AA и 35 моделей AAA). Тогда я измерял ёмкость аккумуляторов сразу после зарядки, а так же через неделю и месяц хранения.

Я провёл дополнительный тест большинства моделей аккумуляторов через семь месяцев после зарядки. Результаты получились интересными.