Saturday, September 17, 2016

EDX 6.008.1X Computational Probability and Inference Notes (Week 1)

EDX 6.008.1x Computational Probability and Inference Notes (Week 1)

Recently, I started doing the EDX 6.008.1x Computational Probability and Inference online course on EDX. This course is offered as part of the MITx and is similar to the MIT 6.008 Introduction to Inference course offered at MIT by Prof. Polina Golland. As a way to motivate myself keeping on track with the course, I decided to save my notes on the course content and publish them online. I hope you they can be useful for other students who are doing the course now, or in later sessions, and for anyone looking for information about topics related to the course subjects.

Course topics:

The course provides an introduction to probability theory and probabilistic graphical models and how to use to perform inferences. Probabilistic models are used in different application domains including information retrieval, data mining, computer vision, natural language processing, financial analysis, robotics, medical diagnosis, …….. The list goes on and on.

In addition to the theoretical topics covered by the course, it also includes 3 mini projects and one final project in Python programming language.  The programming assignments and project were a strong reason for me to decide doing this course :)

Course Requirements

The course assumes good knowledge of calculus and being comfortable with python programming language. No prior knowledge of probability is required.

Week 1

What is probability?

Probability is the science of representing and computing with uncertainty. It appears in our everyday life, especially when making decisions. For example, In the morning you may decide to take an umbrella because there is high chance that it will rain today.

The goal of the course is to learn how to build computer programs that can perform reasoning under uncertainties by using probabilities.

Simplest example of probability is flipping a fair coin, fair coin is a coin that has equal chance of landing heads or tails when being tossed, the probability of head = ½ and the probability of tail is also ½.  But what does this mean ?

There is two interpretations for probability:

Frequentist interpretation: If you repeat the process of tossing the coin for N times (where N is a very large number, say 10,000 times), Approximately N/2 times the result will be heads and approximately N/2 times the result will be tails.

Bayesian Interpretation: It is hard to use the frequentist approach to explain the meaning of probability in some scenarios where the experiment cannot be repeated. For example, the probability that the a patient will die after being given a certain drug. Of course, this experiment cannot be repeated more than one time. Therefore, the frequentist approach does not help a lot in this scenario. The bayesian interpretation of probability is the that probability value is equal to the state of belief in the experiment outcome.
For example, the probability of heads when tossing a coin = ½ means that if you toss a coin once, then before tossing the coin your belief that the result will be heads is equal to ½.

Luckily, it does not make any difference which interpretation you choose to follow, because all probability laws are the same under the two interpretations.

Two ingredients to model uncertainty

When we represent an uncertain world, we call the process that we observe its result an experiment. To model the uncertainty of the experiment we need to define two things:

  • Sample Space : The set of all possible outcomes of the experiment. The sample space can be either finite or infinite set.
  • Probability of each outcome: Define a probability function that assigns a probability value for each possible outcome .
For example, in the experiment of tossing a fair coin:
  • Sample space:
  • Probability values:

Any subset of the sample Space is called an Event.

The probability of an event   is the sum of probabilities of the possible outcomes that belong to .

Programming Note: representing a probability model

The course recommends using the Python dictionary to represent a probability model, where the keys of the dictionary are the elements of the sample space and the values assigned to them are their probability values.
Example: representing the probability model of a fair coin.
model = {'heads' : 0.5, 'tails' : 0.5}

The following can be used to sample 10 outputs from the preceding model

import numpy as np

items, p_values = zip(*model.items())
samples = np.random.choice(a = items, size = 10, p = p_values)

Three axioms of probability

The probability value assignment has to comply with the following three rules (known as three axioms of probability)
  • If A and B are disjoint events ( ) , then

Random Variables

Random variables, strangely enough despite their name, are functions that map the experiment outcomes to another set of  values.
The course uses the python dictionary to represent a random variable that maps a finite sample space to another finite set of values.

weather_model = {'sunny': 0.7, 'rainy' : 0.25, 'snowy': 0.05}
random_variable_mapping = {'sunny': 1, 'rainy' : 1, 'snowy': 0 }

Saturday, March 19, 2016

Integrating cpplint with Vim

Vim is a light-weight, yet powerful editor. Although it may be quite frustrating for developers that it does not, by default, support features such as nice syntax highlighting or keyboard shortcuts,  It is really too easy and straightforward to enable such developer friendly features into it. Here I am showing how to setup a keyboard shortcut to use cpplint with Vim in order to perform code style checking.

cpplint is a code style checker that checks how much your code matches the Google C++ Style guidlines. The feedback returned by cpplint can be valuable for developers to practice writing good code according to Google C++ style guidelines (or others).

  1. Download cpplint from here.
  2. copy cpplint to one of your path directories, make sure it is executable. For example:
sudo cp /usr/local/bin/
sudo chmod usr/local/bin/

3. To setup a keyboard shortcut in VIM to run against your cpp file. Add the following line into your ~/.vimrc file

autocmd BufRead *.cpp map <F7> :w<enter>:!/usr/local/bin/ %<enter>

4. Now, you can use the F7 keyboard shortcut to run cpplint while editing any *.cpp file.

Monday, April 27, 2015

Running MATLAB 2012b on MAC OS X Yosemite

I have been trying to install the MATLAB 2012b on MAC OS X 10.10.3 (Yosemite), however, starting the application after installation keeps gives an error message "Unexpected Exception: There was an unexcepted exception" that refers to the path of log file with error details.

I checked what was inside the log file, and I have found the following message about the reason of the exception:

 com.mathworks.instutil.JNIException: java.lang.UnsatisfiedLinkError: Cant load library: /Applications/  
 java.lang.UnsatisfiedLinkError: Cant load library: /Applications/  

Doing a quick search about problems starting MATLAB on MAC OS X, I have found out that the reason might be the version of java that I am running.

I checked the version of java installed on my machine using

 java -version  

and the output was 
 java version "1.8.0_40"  
 Java(TM) SE Runtime Environment (build 1.8.0_40-b27)  
 Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)  

as I am running Oracle Java 1.8. 

I followed the instructions from this stack overflow answer, to remove the existing installation of Java 1.8 from my Mac.
sudo rm -rf /Library/Java/JavaVirtualMachines/jdk<version>.jdk
sudo rm -rf /Library/PreferencePanes/JavaControlPanel.prefPane
sudo rm -rf /Library/Internet\ Plug-Ins/JavaAppletPlugin.plugin

then I installed the Java for OS X from Apple:

Now, I tried again launching the MATLAB. I noticed that the error message have changed as now the application runs and I can view the splash screen but by the time when it is supposed to display the MATLAB desktop environment, it shows another error message instead.

The new error message is 

Error Starting Desktop:

  at com.mathworks.widgets.WindowsWidgetFactory$SearchAndClearButton.anyText(   
  at com.mathworks.widgets.WindowsWidgetFactory$SearchAndClearButton.getIcon(   
  at javax.swing.plaf.basic.BasicButtonUI.installUI(   
  at javax.swing.JComponent.setUI(   
  at javax.swing.AbstractButton.setUI(   
  at javax.swing.JButton.updateUI(   
  at javax.swing.AbstractButton.init(   
  at javax.swing.JButton.<init>(   

At this moment, I was able to start the MATLAB from the command line, but without the desktop GUI environment using the commands:
 sudo /Applications/ --nodesktop  
 sudo /Applications/ --nojvm  

I tried installing X11 which is claimed to be required by MATLAB on OS X as stated here  but still the problem persists to happen.

Finally, I noticed that there is a bug report for this issue on MathWorks website that provides a patch for solving this issue. I downloaded the patch from , and  run at as described in the instruction on the page and now I can run MATLAB normally on my MAC Yosemite! :D :D

Sunday, April 26, 2015

Dissecting Android Permissions

What are Android Permissions ?

Android uses a fine-grained permission to control the application access to resources. APIs for accessing sensitive resources are actions are protected by permissions, the application developer must declare what permissions the application needs to operate correctly within the application manifest file “manifest.xml”. The syntax for that is :

<uses-permission android:name="string"
       android:maxSdkVersion="integer" />

where  android:name is the name of the required permission, and android:maxSdkversion is the highest API level at which the application needs to be granted this permission. Ths attribute is useful if the permission declared is no longer needed after a certain API level.

The list of all permissions defined by the base Android operating system can be found here:

In addition to those, the application developer can also define new permissions to control what other applications can interact with his application.


    android:maxSdkVersion="18" />

This indicates that the application asks for being granted the “android.permission.WRITE_EXTERNAL_STORAGE” when installed on API level 18 or lower.

At  the time of application installation, the user will presented with a list of all permissions requested by the application (as declared in the manifest file) and it is up to him to proceed with the installation process, therefore granting it all permissions it needs, or cancel the installation process.

How permissions are maintained in Android ?

In Android, the PackageManger is responsible for managing the packages installation and permissions. You can use the package manager to view all installed packages on your Android system:

pm list packages

or list all permissions (including those that are defined by 3rd party application developers):

pm list permissions

Or you can also use it to install an application

pm install <APK_filename>

or to grant/ revoke permission to a package ?


When you attempt to install an application, The PackageInstallerActivity invokes the PackageManager that is starts the installation process. The package manager communicates with the PackageManagerService to get the app installed via the installd daemon. The PackageManager runs within the “system_server process and the installd runs as a native service. Both of install daemon (installd) and system_server are started at the boot time.

( Figure Courtesy of )

How does the installation process happen ?

A major difference between Android and Linux is that Android isolates each application from other applications to prevent malicious applications from snooping or crashing other installed application. This approach is known as “Sandboxing”, Android achieves this by considering each application as a different user.

At installation time, the PackageManager copies the APK file and any native libraries within the app to “/data/app/<package name>” directory (or “/system/app/<package name>” for system applications). Then, it decides a unique identifiers (UID) for the new application. The application UIDs are chosen in the range between 10,000 and 99,999 . As defined in ANDROID_FILESYSTEM_CONFIG

#define AID_APP          10000  /* first app user */

In addition to the UID, the application is also assigned a username to the maps to the UID (For example application with UID 10032 is assigned the user name u0_a32 )  and a data directory at “/data/data/<package name>”. Permissions for the data directory are set appropriately such that it is owned by the new created user for this application.

Although that by default Android assigns to each application a unique UID, two application can request to be running under the same UID by setting the same value of android:sharedUserId in their manifest files, this is only possible if both application are going to be signed by the same developer certificate. The two applications that share the same user id will share the same data directory and , if desired, run in the same process. The role of code signing in Android Security model is explained in more detail in this article.

For example,  the  application “” has been assigned the UID : 10057 and the user name “u0_a57”. The data directory for that app /data/data/” is therefore owned by “u0_a57” user.

Also during the installation, the PackageManager adds new entries for the new installed package in “/data/system/packages.xml” and “/data/system/packages.list” files.

The “packages.xml”  also maintains information about installed packages, including the packagename, app directory (location of apk, and native libraries), their user ID, version number (as extracted from the manifest file), the certificate key by which the APK was signed and the list of permissions that have been granted to the application. Permissions are stored under the <perms> tag. Adding or removing items from this section may grant or revoke permission to the application. However, modification will not be reflected until the system_server (hosting the PackageManagerService) is restarted since the application permissions are cached as we will see later.

<package name="" codePath="/data/app/" nativeLibraryPath="/data/app/" flags="572998" ft="14cca4e4b58" it="14cca4cf54b" ut="14cca4e4ea5" version="1" userId="10057">
       <sigs count="1">
           <cert index="6" />
           <item name="android.permission.CAMERA" />
       <proper-signing-keyset identifier="48" />
       <signing-keyset identifier="48" />

while the “packages.list” file lists all installed packages their user identifiers (UID),  the location of their data directory, and the identifier of any groups (GIDs) they are member of. 10058 1 /data/data/ default 3003 10057 1 /data/data/ default none

Note that granting some permissions to an application results in adding the applications UID into a members group. For example the package “”  (u0_a58) is a member of 3003 group (inet) because it has been granted the “android.permission.INTERNET” permission. The mapping between permissions and group IDs can be found at:
/etc/permissions/platform.xml” while the group identifier (GID) values for the groups are defined in ANDROID_FILESYSTEM_CONFIG.. Those kinds of permissions are enforced by at the low-level byl kernel itself.

Where does permission checking happen?

When the android device boots, the first process started by the linux kernel is init  (PID: 1) process that executes shell scripts defined inside /init.rc.

This goal of init.rc is to initialize the system environment by executing a series of commands.
The init.rc defines the user under each each service is going to run (for example: Zygote will run under the root user, while keystore service will be started under the keystore user).

One of the early processes started by init is the Zygote. Zygote is a daemon whose goal is to start additional services and to load libraries. It acts as a loader for each Dalvik process by creating a copy of itself (e.g. forking it self). The zygote is started by executing the “system/bin/app_process” command.

Then it is the  Zygote’s rule to start the system_server” process.  Therefore, the Zygote acts as the parent process oft he “system_server” and for any later running process.

ps | grep Zygote

Here, we notice that the Zygote is running the “root” user with PID = 3085 and PPID = 1

We also note that other running processes including the system_server have the Zygote’s PID (3085) assigned as their PPID.

ps -t -p 3339

Looking inside the source code of PackageMangerService

Within the constructor, PackageManagerService instantiates an object (mSettings) of Settings class

1300        mSettings = new Settings(context);

The object mSettings will be used deserialize package configurations from “packages.xml” file by calling:

 mRestoredSettings = mSettings.readLPw(this, sUserManager.getUsers(false),
1393                    mSdkVersion, mOnlyCore);

Also: updates to the package settings are serialized to the “packages.xml” file using the mSettings instance.

1125                        mSettings.writeLPr();

The packageManagerService  exposes two public methods: checkPermission, and checkUidPermission  function that is given a package name or application UID have been granted the permission identified by permName, it will return either PackageManager.PERMISSION_GRANTED or PackageManager.PERMISSION_DENIED.

public int checkPermission(String permName, String pkgName) {
2373        synchronized (mPackages) {
2374            PackageParser.Package p = mPackages.get(pkgName);
2375            if (p != null && p.mExtras != null) {
2376                PackageSetting ps = (PackageSetting)p.mExtras;
2377                if (ps.sharedUser != null) {
2378                    if (ps.sharedUser.grantedPermissions.contains(permName)) {
2379                        return PackageManager.PERMISSION_GRANTED;
2380                    }
2381                } else if (ps.grantedPermissions.contains(permName)) {
2382                    return PackageManager.PERMISSION_GRANTED;
2383                }
2384            }
2385        }
2386        return PackageManager.PERMISSION_DENIED;
2387    }

2390    public int checkUidPermission(String permName, int uid) {
2391        synchronized (mPackages) {
2392            Object obj = mSettings.getUserIdLPr(UserHandle.getAppId(uid));
2393            if (obj != null) {
2394                GrantedPermissions gp = (GrantedPermissions)obj;
2395                if (gp.grantedPermissions.contains(permName)) {
2396                    return PackageManager.PERMISSION_GRANTED;
2397                }
2398            } else {
2399                ArraySet<String> perms = mSystemPermissions.get(uid);
2400                if (perms != null && perms.contains(permName)) {
2401                    return PackageManager.PERMISSION_GRANTED;
2402                }
2403            }
2404        }
2405        return PackageManager.PERMISSION_DENIED;
2406    }

Case Analysis : LocationManager

Within the LocationManagerService, the function getAllowedResolutionLevel is used to return finest resolution level allowed for the calling application. It returns RESOLUTION_LEVEL_NONE if the application is not granted location access at all.

private int getAllowedResolutionLevel(int pid, int uid) {
1006        if (mContext.checkPermission(android.Manifest.permission.ACCESS_FINE_LOCATION,
1007                pid, uid) == PackageManager.PERMISSION_GRANTED) {
1008            return RESOLUTION_LEVEL_FINE;
1009        } else if (mContext.checkPermission(android.Manifest.permission.ACCESS_COARSE_LOCATION,
1010                pid, uid) == PackageManager.PERMISSION_GRANTED) {
1011            return RESOLUTION_LEVEL_COARSE;
1012        } else {
1013            return RESOLUTION_LEVEL_NONE;
1014        }
1015    }