Создание Android Smart Launcher с помощью машинного обучения

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

Постановка задачи

Несколько месяцев назад я решил, что не хочу тратить большую часть своих часов бодрствования на поиск приложений, которые я хочу использовать на своем устройстве - будь то ввод текста в поле поиска или прокрутка длинного списка приложений. Людям необходимо 8–9 часов сна, чтобы нормально функционировать (по крайней мере, мне). Если из оставшихся 15 часов мы потратим 1 час (я всегда преувеличиваю, переживите это 😝) просто на поиск нужного нам приложения для повышения производительности, мы обречены. Некоторые люди могут возразить, почему бы просто не исправить часто используемые приложения на главном экране? Что ж, это может сработать для пользователей, которые ежедневно используют меньшее количество приложений. Но представьте себе тяжелое положение такого пользователя, как я, у которого на устройстве около 200 приложений, многие из которых используются с очень определенным шаблоном (примеры ниже). На главном экране нельзя исправить 30 часто используемых приложений. Я хотел, чтобы мой смартфон был достаточно умен, чтобы «предсказывать», какое приложение я буду использовать в следующий раз. Увы! Если бы это было возможно… или нет?

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

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

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

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

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

Прежде чем мы начнем ... Это не статья о том, как создавать приложения для Android для начинающих. Я буду объяснять документ (кроме той части, которую я сам еще не понял) и как реализовать важные части на Android. Так что основы разработки под Android, Kotlin, машинное обучение (по крайней мере, KNN) и т. Д. Определенно помогут. И самое лучшее, что KNN - один из простейших алгоритмов машинного обучения.

Что говорится в исследовательской статье

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

Вот упрощенная версия алгоритма, упомянутого в статье:

Для каждого экземпляра запуска приложения соберите контекстную (а не контекст Android) информацию и представьте ее как d-мерный вектор Rᵈ
Выполните KNN на датасете таких ранее запущенных векторов приложений. Выберите ближайшие векторы, и соответствующие приложения, скорее всего, будут использоваться пользователем в следующий раз.
Сохраните вектор, сформированный на шаге 1, в набор данных истории с меткой класса в качестве имени пакета приложения (или любого уникального идентификатора для приложения).
Повторите действия с шага 1 для следующего запуска приложения.

Это кажется простым, правда? В каком-то смысле это так. Но давайте не будем слишком волноваться. Я абстрагировался от всех сложностей на шагах 1 и 2, которые, несомненно, составляют основу этого метода. Давайте подробно обсудим каждый шаг.

Формирование признаков

Этот шаг запускается каждый раз, когда пользователь запускает приложение. Мы фиксируем и собираем переменные системы / среды и формируем вектор. На этом этапе мы собираем информацию двух типов - явную и неявную. Явные функции - это переменные среды на момент запуска, такие как время, уровень заряда батареи, состояние Bluetooth и т. д. Все эти значения используются в нормализованной форме (например, уровень заряда батареи можно разделить на 100, чтобы представить его как поплавок [0, 1]). Я тоже использовал дополнительную функцию. Все эти значения объединяются в вектор (массив чисел) - [Xₜᵢₘₑ, .., Xₐₘ,…].

Неявные функции или функция отслеживания использования приложений (ATF), как ее назвали авторы, собирают информацию о предыдущих запусках приложений. Это немного сложно, поэтому обратите внимание.

Предположим, у нас установлено 10 приложений. Каждому приложению должен быть присвоен целочисленный идентификатор от 0 до 9.

Теперь также предположим, что в настоящий момент последовательность ранее использованных приложений - A → C → I. Это означает, что пользователь запустил приложение A, B, а затем I (на основе истории, которую мы вели; шаг 3 выше). Здесь мы рассматриваем только 3 предыдущих приложения (размер окна), который является гиперпараметром и может быть любым, каким вы пожелаете. Длина вектора ATF - это количество установленных приложений (здесь 10), а значение каждого индекса i рассчитывается по следующей логике:

1. Для каждого индекса i проверьте, входит ли соответствующее приложение в число j приложений, которые использовались последними.

2. Если ответ на шаг 1 отрицательный, тогда значение равно 0, повторите для i + 1 и пропустите остальные шаги для текущей итерации. Если да, то проверьте, как давно было запущено приложение iᵗʰ. Например, приложение А было запущено на третьем месте.

3. Предположим, приложение iᵗʰ запускалось в jᵗʰ place в прошлом. Затем мы вычисляем значение индекса i по следующей формуле: γʲ⁻¹ * 1, где γ - скорость распада в диапазоне [0, 1]. Итак, для нашей недавней последовательности приложений вектор ATF будет иметь 0,5² * 1 при 0-м индексе (с γ = 0,5), поскольку приложение A имеет идентификатор 0 и было запущено на 3-м месте. Интуиция заключается в том, что чем дальше запускалось приложение в прошлом, тем меньше оно влияло на прогноз следующего запуска приложения.

Вот соответствующие уравнения из статьи, объясняющие то же самое:

Конструкция ATF со скоростью разложения

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

Кластеризация и рекомендации

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

Пусть R̂ будет вектором запуска для нового события запуска приложения, а Rᵢ будет вектором запуска iᵗʰ в истории или наборе данных. Для каждого i:

Найдите евклидово расстояние между R̂ и Rᵢ
Выберите «K» ближайших векторов и их соответствующие расстояния (прошлые запуски приложения с соответствующими векторами запуска, наиболее похожими на текущий вектор запуска)
Для каждого из K векторов выполните следующие действия:

Преобразуйте расстояния в сходство, найдя его обратным (вместе с небольшим значением, добавленным к знаменателю, чтобы предотвратить деление на ноль).
Затем найдите группировку каждого приложения в найденном выше KNN. Это означает, что если приложение A встречается дважды в извлеченном KNN, мы присваиваем приложению A оценку = подобие_score1 + подобие_score2.
Затем мы выбираем N самых популярных приложений в качестве прогнозов. N может быть любым числом, например 5 или 8.

Этот алгоритм представлен в статье следующими уравнениями:

Вот и все! Мы успешно поняли суть алгоритма. Обратите внимание, что я пропустил ту часть, где они используют алгоритм «Наибольшая маржа ближайшего соседа» для повышения производительности. Они используют «метрику расстояния» для изучения матрицы, которая преобразует каждый вектор запуска таким образом, чтобы векторы, принадлежащие одному запуску приложения, были ближе друг к другу, а векторы разных приложений раздвигались дальше друг от друга. Таким образом, в некотором смысле он следует той же концепции, что и машина опорных векторов. Но я еще не разобрался, как они оптимизируют функцию потерь для LMNN. Как только я это выясню, возможно, я тоже это реализоваю.

Реализация Android

Проект можно найти в моем репозитории на GitHub. Я не разобрался здесь с кодом всего проекта. Я просто упомяну важные моменты.

Первый шаг - запросить / объявить необходимые разрешения:

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

Пользовательский интерфейс средства запуска отрисовывается с помощью «MainActivity», который следует шаблону MVVM. Следующим шагом является объявление активности как экрана запуска:

Чтобы Android знал, что Activity может быть экраном Launcher, необходимо определить указанные выше категории.

Внешний вид экрана запуска определяется следующим образом:

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

Ядро приложения обрабатывается одноэлементным классом под названием «SmartLauncherRoot». Этот класс поддерживает список всех установленных приложений на устройстве (при фильтрации системных / внутренних приложений). Для этого я отфильтровал все пакеты, у которых нет «намерений запуска».

Этот список приложений затем отображается пользователям, как это делают обычные программы запуска. Каждый раз, когда пользователь нажимает на приложение из списка приложений или предложений на главном экране, выполняется вызов функции «appLaunched», которая «обрабатывает» событие. Это означает, что он генерирует вектор запуска для конкретного события запуска приложения, затем сравнивает его с историческими векторами, обновляет список предлагаемых приложений на экране Launcher и, наконец, добавляет текущий вектор запуска к историческим данным. Вот функция, которая находит K ближайших соседей для данного вектора:

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

Из приведенного выше «appScoresMap» выберите верхние «N» приложений. Вот и все! У нас есть свои прогнозы.

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

Приложение также выполняет другие обязанности, такие как:

сохранение векторов истории запусков и других данных в хранилище
перезагрузка данных в коллекции и переменные каждый раз при воссоздании Launcher.
возможность резервного копирования файла данных в папку «Загрузки», чтобы выжить после повторной установки приложения. В будущем я найду другой способ. Во время разработки он много раз спасал мой тыл. Вы можете долго нажимать на пустом месте экрана запуска, чтобы увидеть параметры отладки. Значок «скачать» означает резервное копирование данных из личного каталога приложения в «Каталог загрузок». Значок «загрузить» (нижний) означает, что вы можете заменить файл в личном каталоге своим собственным файлом. Вы можете использовать его, когда переустанавливаете приложение и хотите использовать данные, которые вы создали ранее.
Удалите некоторые векторы истории, когда размер превышает пороговое значение (на данный момент 2 КБ).
Обработка изменения размера вектора из-за установки / удаления приложения.

Скопировать и вставить сюда весь код не имеет смысла. Код довольно прост для понимания и доступен в моем репозитории GitHub. Если же, однако, многим читателям будет интересна статья с подробным объяснением кода, я напишу отдельную статью.

Вот несколько гифок приложения в действии:

В первом примере показаны прогнозы после запуска приложения Часы / Будильник без подключенных наушников:

Следующий GIF показывает прогнозы после запуска того же приложения Alarm, но при подключенных наушниках:

Как видите, прогнозы различаются, хотя запуски производились в течение 5 минут. Это потому, что «наушники подключены» - одна из особенностей нашего вектора запуска.

Примечание. Обои не являются частью средства запуска. Это живые обои, которые я разработал в прошлом году. Он есть в Play Store - Matrix LiveWallpaper. Вы увидите обои, которые вы установили на своем устройстве.

Давайте посмотрим на данные

Все это выглядит хорошо, но как выглядят данные? Векторы хранятся в файле в формате JSON:

[{“key”: “com.google.android.calendar”, “value”: {“data”: [0.7741935483870968, 0.75, 0.06698729810778065, 0.035977799166666664, 0.21588112083333333, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.75, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]}}, …]

Я написал сценарий Python для применения PCA к векторам (для уменьшения размеров) и визуализации его на диаграмме рассеяния:

Я выполнил эту операцию с данными / векторами, сгенерированными с измерением «время» (час дня) как час / 24, а также с измерением времени, рассчитанным по формуле, которую использовали авторы:

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

Как видите, значения для time = 1 ближе к значениям time = 0, что логично, поскольку 1 час ночи ближе к полуночи. Поэтому я решил попробовать приложение с этим представлением, хотя необработанные значения тоже работают нормально.

Ограничения

Приложение было разработано для личного пользования в качестве развлекательного проекта. Таким образом, многие «навороты», которые можно найти в коммерческих приложениях Launcher или в приложении Android Launcher по умолчанию, отсутствуют. Также могут быть проблемы, связанные с фрагментацией устройства (проблемы, характерные для некоторых производителей / брендов), поскольку я использовал его только на своих устройствах (я использовал его на нескольких устройствах, и все они кажутся хорошими). Я могу выпустить его бета-версию для заинтересованных пользователей, но может быть сложно добавить все функции обычной программы запуска Android при самостоятельной разработке (это тоже работает только по выходным!). Спасибо за ваше терпение.

Я фиксирую только запуски приложений, сделанные через список приложений и список прогнозов приложений. Поскольку они запускаются внутри приложения запуска. Некоторые другие источники, которые не записываются / не фиксируются, - это запуск приложения из уведомления и недавние задачи. Теперь уведомления не следует рассматривать в любом случае, потому что эти запуски приложений на самом деле не являются шаблонами использования пользователями, а скорее запускаются при получении уведомления. Однако недавние задачи являются ограничением.
Повторная загрузка резервной копии данных после переустановки приложения запуска не удастся, если установленные приложения на устройстве были изменены. Найдет способ справиться с этим. (установка / удаление приложения во время установки и использования Launcher обрабатывается)
В исследовательской статье упоминается алгоритм под названием «Ближайшее соседство с большим запасом» для преобразования векторов таким образом, чтобы похожие векторы были сближены, а разнородные - раздвинуты дальше друг от друга. Функция потерь для него кажется простой, но я не стал думать об оптимизации функции потерь, которая фактически находит матрицу, преобразующую векторы. Они используют «выпуклую оптимизацию» для минимизации функции потерь. Как только разберусь, буду реализовывать. Если у вас есть опыт работы с этой частью, свяжитесь со мной. Предполагается, что это еще больше повысит производительность.
Нет поддержки для добавления виджетов на главный экран. Это скорее вращающиеся диски, но в ближайшем будущем мы добавим их.
У некоторых пользователей может быть очень неустойчивая модель использования. Не уверен, насколько хорошо это может сработать для них! Хотелось бы услышать отзывы от этих пользователей.

Спасибо, что остались до конца этого длинного поста. Я не был уверен, следует ли мне разделить это на 2 части. Как обычно, не стесняйтесь связываться со мной в LinkedIn или Twitter (стараюсь быть активным в эти дни) или оставьте здесь комментарий, если у вас есть какие-либо вопросы относительно этого проекта или каких-либо новых идей, или если вы просто хотите сказать "Привет". Я люблю обсуждать новые идеи.

Оставайся в безопасности, оставайся внутри.

Создание Android Smart Launcher с помощью машинного обучения