Building Android Smart Launcher With Machine Learning

Photo by Daniel Romero on Unsplash

Building Android Smart Launcher With Machine Learning

Hello Medium Readers. I am back with another interesting project for you. Apologies to my followers for the long break. But it wasn’t due to lack of new projects. I have started quite a few interesting projects in the past year (from Unsupervised text style transfer to Human computer interaction), but unfortunately hit road blocks in them, so I took a pause from them (some are public repositories, so interested folks can still check them out).

Problem Statement

Few months back I decided I don’t want to spend a big chunk of my waking hours searching for the apps I want to use on my device — be it typing in the search box or scroll through the long list of apps. Humans need a good 8–9 hours of sleep to function properly (at least I do). If we spend 1 hour of the remaining 15 hours (I exaggerate always, get over it 😝 ) just looking for that productivity app we need, we are doomed. Some people may argue, why not just fix the frequently used apps on the Home screen? Well, it may work for users who use less number of apps on a daily basis. But imagine the plight of a user like me, who has ~200 apps on the device, many of which are used with a very definite pattern (examples later). One can’t fix 30 frequently used apps on Home screen. I wanted my smartphone to be smart enough to “predict” which app I may be using next. Alas! If only it were possible… or is it?

I don’t use my phone heavily but I have a specific usage pattern — meaning, I have a strong correlation between time of day and used app, and sometimes the sequence of apps used. I will give you some scenarios which will help us understand later why the solution works:

Scenario 1: I don’t use the music/podcast apps on my phone through out the day. But at night I have a ritual of plugging in my earphones, setting the alarm, and then listen to some soothing music or podcasts which are suggested for insomniacs and anxiety afflicted people like me. Device should show previously used audio apps as shortcuts.

Scenario 2: Let’s say you go to a nearby store to buy groceries. You open your note-taking app to check the grocery list. Once you have gathered the items, you open one of your payment/banking apps to make a payment. The device should be able to detect the location coordinates and the grocery app as landmark events to predict payment apps you have used in similar situations on your home screens.

What if our smartphones could learn from these patterns and show up audio applications once Alarm app is launched at night with headphones plugged in or payment apps once note-taking apps are launched? What’s more, the usage patterns could vary for each individual and can’t be practically solved using heuristics.

Is there a way to capture these contexts as variables and some how use them to predict next app usage? This is the question I asked myself and started digging into existing works for any hints. Turns out, this is exactly what the research paper “Mobile App Recommendation with Sequential App Usage Behavior Tracking” does. And we will understand the algorithm and implement it here.

Before we begin… This is not an article on how to build Android applications for beginners. I will be explaining the paper (except the part which I haven’t figured out myself yet) and how to implement the important parts on Android. So basics of Android development, Kotlin, Machine Learning (at least KNN) etc would definitely help. And the best thing is KNN is one of the simplest ML algorithms out there.

What does the research paper say

What I love about this paper is that the authors were cognizant of the limitations of computation power of mobile devices and the privacy concerns of training and hosting a Neural Network on cloud. I think work like these should be paid more attention than the papers which add a billion more parameters/data for slight improvement over existing methods, but are difficult for people like me and you to implement due to cost factors. But I digress.

Here is the simplified version of the algorithm mentioned in the paper:

1. For each app launch instance, collect the context (not the Android context) information and represent it as a d-dimensional vector Rᵈ
2. Perform KNN on the dataset of such previously launched app vectors. Choose the closest vectors and the corresponding apps are most likely to be used by the user next.
3. Save the vector formed in step 1 to the history dataset with class label as app package name (or any unique identifier for an app).
4. Repeat from step 1 for next app launch.

It seems simple, right? Well, in a way, it is. But let’s not get too excited. I have abstracted all the complexities in step 1 & 2, which are undoubtedly the backbone of this method. Let’s discuss each step in detail.

Feature Formation

This step is triggered every time user launches an application. We capture and collect the system/environment variables and form the vector. There are two types of information which we collect in this step — explicit and implicit. Explicit features are the environment variables at the time of launch like time, battery level, Bluetooth state etc. All these values are used in a normalized form (e.g. battery level may be divided by 100 to represent it as a float [0, 1]). I have used an extra feature too. All these values are concatenated to form a vector (array of numbers) — [Xₜᵢₘₑ, .., Xₐₘ, …].

Explicit features from paper.

Implicit features or App-Usage Tracking Feature (ATF), as the authors have named it, captures the information about previous app launches. This is a bit tricky, so pay attention.

Let’s assume we have 10 apps installed. Each app has to be assigned an integer id from 0–9.

Example of apps and app ids

Now, also assume that at the moment the sequence of previously used apps is A→C→I. Meaning, user has launched app A, B and then I (based on the history we have maintained; step 3 above). We are considering only 3 previous apps here (window size), which is a hyperparameter and can be anything you wish. The length of ATF vector is the number of apps installed (10 here) and value at each index i is calculated by following logic —

1. For each index i check if the corresponding app is among the j most recently used apps.

2. If the answer to step 1 is no then value is 0, repeat for i+1 and skip rest of the steps for current iteration. If the answer is yes, then check how far in the past was the iᵗʰ app launched. For instance app A was launched in the third place.

3. Let’s assume the iᵗʰ app was launched at jᵗʰ place in the past. Then we calculate the value at i index using following formula: γʲ⁻¹ * 1, where γ is the decay rate with range [0, 1]. So for our recent app sequence, ATF vector would have 0.5² *1 at 0th index (with γ=0.5), since app A has id 0 and was launched in the 3rd place. The intuition here is that, the further the app was launched in the past, the lesser is it’s impact on the next app launch prediction.

Here are the relevant equations from the paper explaining the same:

ATF construction with decay rate

Once we have calculated the explicit features and ATF we need to concatenate both to get the final feature vector for an app launch

Clustering and Recommendation

Once we have the feature vector for the current app launch, we need to apply clustering algorithm to find the closest app launch vectors, which would be our prediction results. For this we will apply KNN in a slightly different way.

Let R̂ be the launch vector for a new app launch event and Rᵢ be the iᵗʰ launch vector in the history or dataset. For each i :

1. Find the Euclidean distance between R̂ and Rᵢ
2. Select the “K” nearest vectors and their respective distances (past app launches with corresponding launch vectors most similar to current launch vector)
3. For each of the K vectors do the following:

• Convert the distances into similarity by finding it’s reciprocal (along with small value added to the denominator to prevent division by zero).
• Then find the group-by-sum of each app in the KNN found above. Meaning, if app A occurs twice in the extracted KNN, then we assign app A with score = similarity_score1 + similarity_score2.
• Then we select the top most N apps as predictions. N could be any number like 5 or 8.

This algorithm is represented by following equations in the paper:

equations for score calculation for each candidate app

That’s it! We have successfully understood the algorithm’s crux. Please note that I have skipped the part where they use “Largest Margin Nearest Neighbour” algorithm to enhance the performance. They use “distance metric” learning to learn a matrix which transforms each launch vector in such a way that vectors belonging to same app launch are closer to each other and different app vectors are pushed further apart. So, in a way it follows similar concept as Support Vector Machine. But I have not yet figured out how the loss function for LMNN is optimized by them. Once I figure that out, maybe I will implement it as well.

Android Implementation

The project can be found on my GitHub repository. I won’t got through the code of whole project here. I will just mention the important bits.

First step is to request/declare the needed permissions:

Manifest permissions

These permissions are mostly required to read the state of device while generating the launch vectors (exception is storage, which is needed to backup the data and use it later in case of reinstall. It helps me quite a lot during dev/test, but is not critical)

The launcher UI is drawn by “MainActivity” which follows MVVM pattern. Next step is to declare the activity as a Launcher screen:

For Android to know that an Activity is capable of being a Launcher screen, above categories have to be defined.

The layout of launcher screen is defined like this:

The “app_list_sheet” is a bottom sheet which holds all the installed apps list and a search box. Users can drag the bottom sheet up to see all the apps. Our goal is to reduce the number of drag and search operations.

The core of the application is handled by a singleton class called “SmartLauncherRoot”. This class maintains a list of all the installed apps on the device (while filtering out system/internal apps). To achieve this I have filtered out any packages, which have no “launch intents”.

This list of apps is then shown to the users as normal launchers do. Every time a user clicks on an app from apps list or home screen suggestions, a call is made to “appLaunched” function which “processes” the event. Meaning, it generates a launch vector for the particular app launch event, then compares it with historical vectors, updates the suggested apps list on Launcher screen and then finally adds the current launch vector to historical data. Here is the function which finds the K nearest neighbours for given vector:

Tuple holds a key-value pair of package name of app and corresponding launch vector for when the app was launched. ArrayRealVector is a data structure in apache.commons.math package. The result of above function is then used to find a “group-by-sum” on package names and then sorted.

finding top N neighbours apps

From the above “appScoresMap” choose the top “N” apps. That’s it! We have our predictions.

Once the steps explained in the theory section are performed, the suggested apps are notified back to MainActivity using live data for users HomeScreen as shortcuts.

The app also handles other responsibilities like:

• saving the launch history vectors and other data to storage
• reloading the data into collections and variables every time Launcher is recreated.
• option to backup the data file to “Downloads” folder to survive through app re-installs. In future I will find some other way. During development it saved my rear a lot of times though. You can long press on the Launcher screen empty space to see debugging options. The “download” icon mean backing up the data from app private directory to “Downloads directory. The “upload” icon (bottom one) means you can replace the file in private directory with your own file. You can use it when you reinstall the app and want to use the data you had backed up earlier.
• Delete some history vectors when the size grows beyond a threshold (2K as of now).
• Handle vector size change due to app install/uninstall.

Copy pasting all of the code here won’t make sense. The code is fairly simple to understand and is available on my GitHub repo. If however, if many readers seem interested for an article on detailed code explanation, I will write a separate article.

Here are some GIFs of the app in action:

First sample shows the predictions after launching the Clock/Alarm app without earphone plugged in:

Launcher prediction after clock app launch without earphones

Next GIF shows predictions after launching the same Alarm app but while earphones are plugged in:

Launcher prediction after clock app launch with earphones

As you can see the predictions differ even though the launches were made within 5 mins. This is because “earphone plugged in” is one of the features in our launch vector.

Note: The wallpaper is not part of the launcher. It’s a Live Wallpaper I had developed last year. It’s on Play Store — Matrix LiveWallpaper. You will see the wallpaper you have set on your device.

Let’s see the Data

This all looks good, but what does the data look like? The vectors are stored in a file in JSON format:

[{“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]}}, …]

I wrote a Python script to apply PCA on the vectors (to reduce the dimensions) and visualize it on scatter plot:

I performed this operation on data/vectors generated with “time” (hour of day) dimension as hour/24 and also with time dimension calculated by the formula which the authors used :

cyclic representation of time dimension

plot with raw hour of day (hour/24)

plot after cyclic representation of time dimension

As you can see the raw time dimension forms more prominent clusters than cyclic representation. This could be because by using second approach the time dimension values are converted into continuous values without any hard breaks after midnight (value changing from 1 to 0 after midnight). But with converting this raw value to periodic values it looks like this:

cyclic representation of time 0..1 values looks like this for sin and cos

As you can see the values for time=1 are closer to time=0 values, which is logical since 1 AM is closer to midnight. So I decided to try the app with this representation, although the raw values work just fine too.

Limitations

The app was developed for personal use as a fun project. So a lot of “bells & whistles” found in commercial Launcher apps or the default Android Launcher app are missing. There could also be device fragmentation related issues (issues specific to some manufacturers/brands), since I have been using it on my devices only (I have been using on a few devices and all seem good). I may release a beta version of it for interested users, but it may be tough to add all the features of a regular Android launcher while developing alone (that too working only on the weekends!). So your patience is really appreciated.

• I am only capturing the app launches made through apps list and apps predictions list. Since those are triggered inside the launcher app. Some other sources which are not recorded/captured are app launch from notification and recent tasks. Now, notifications shouldn’t be considered anyway because those app launches are not really users’ usage patterns but rather triggered whenever notification arrives. Recent tasks are a limitation though.
• Reloading the data backup after a reinstall of the launcher app will fail if installed apps on device have changed. Will find a way to handle it. (app install/uninstall while Launcher is being installed and used is handled though)
• The research paper mentions an algorithm called “Large Margin Nearest Neighbour” to transform the vectors such that similar vectors are pulled closer, while dissimilar vectors are pushed further apart. The loss function for it seems straight forward, but I haven’t wrapped my head around the optimization of the loss function, which actually find the matrix which transforms the vectors. They use “convex optimization” for minimizing loss function. Once I figure it out, I will implement it. If you any experience with this part, please connect with me. This is supposed to improve the performance further.
• No support for adding widgets to Home screen. This is more of spinning rims, but will be adding it in near future.
• Some users may have very erratic usage pattern. Not sure how well it may perform for them! Would love to hear feedbacks from those users.

Thanks for staying till the end of this long post. I was not sure whether I should split this into 2 parts. As usual, feel free to connect with me on LinkedIn or Twitter (trying to be active there these days) or drop a comment here, if you have any queries regarding this project or any new ideas or if you simply wanna say “hi”. I love discussing new ideas.

Stay safe, stay inside.