Gradient Descent Algorithm.

Gradient Descent is a very important algorithm that is used in Machine learning. There are numerous variations of GD and is an active research area. This post is part of the notes that I wrote down while learning various variations of Gradient Descent. It is not complete. I will be adding more details as I explore more interesting parts of Gradient Descent.

 

What’s Gradient Descent?

Image result for bowl

In simple terms, Gradient Descent is an algorithm that is used to find the minimum of a function.

You can imagine the function to be like the bowl here. We need to find the minimum of the function, which is the bottom of the bowl.

Imagine you roll a small spherical ball from the top. It follows the most curved path and reaches the bottom. Gradient descent also works the same way. It follows the negative gradient(slope) and tries to reach a minimum of the function.

You can see the algorithm moving along the path to reach the minimum in this picture.

 

 

 

 

 

 

 

 

Python Implementation.

Let’s try to find the minimum of a function using Gradient Descent. (This example is taken from wiki page for Gradient descent)

The gradient descent algorithm is applied to find a local minimum of the function f(x)=x4−3x3+2, with derivative f'(x)=4x3−9x2

# From calculation, it is expected that the local minimum occurs at x=9/4

cur_x = 6 # The algorithm starts at x=6
gamma = 0.01 # step size multiplier
precision = 0.00001
previous_step_size = cur_x

def df(x):
    return 4 * x**3 - 9 * x**2

while previous_step_size > precision:
    prev_x = cur_x
    cur_x += -gamma * df(prev_x)
    previous_step_size = abs(cur_x - prev_x)

print("The local minimum occurs at %f" % cur_x)

 

Mathematical representation

Image result for gradient descent formulaHere  Slope Parameter(alpha) is known as learning rate in neural network training.

is called as the cost function. It is the output value computed by the neural networks, which we try to minimize.

 

 

 

 Stochastic gradient descent (SGD)

Vanilla gradient descent runs over the whole dataset to find the next update for the parameters. When it comes to large datasets this approach might become intractable in a machine. So Stochastic gradient descent is a slight modification of the vanilla gradient descent algorithm.

SGD

Vanilla descent estimates the expectation of the function with all items in the dataset. SGD uses a single sample to update the values

Selection_001

Mini batch Gradient Descent

Simple samples used by gradient descent has a lot of noise in the update. So a small subset of the samples is used as mini-batch. A common mini batch size in 256. Mini batches tend to average a little of the noise out.

Selection_002
Gradient is calculated with a mini-sample

 

 

Advertisements

Apply for Google Summer of Code 2018

gsoc-2014-600x540Google Summer of Code 2018 has been announced. I participated and completed GSoC  2017. This blog is for all who are trying to apply this year.

What is Google Summer of Code?

Google Summer of Code (GSoC) is a 3 month internship sponsored by Google. Many organisations participate in GSoC and allow students from across the world to work on their open source projects. Google will pay you for the work. In India the stipend is $2400 dollars(2016). It will be paid each month during the program. Complete information can be found here

What’s the timeline of the program?

Google has announced this year’s GSoC. They will announce the organisations that are participating, by next January. Application period for students to apply will likely start by next February. You can find the complete timeline here

How to apply?

Students need to choose the organisation they are going to apply . The application process starts by creating a  proposal for the project idea you are planning to work on. This will include the details about the project. The timeline (important) of the project etc. You can refer my proposal here.

What are the benefits?

Google pays a stipend of $2400 dollars for your work in GSoC to every selected participant. Once the program is completed the student gets a direct job interview offer from Google(One time applicable). Participation in GSoC is something that makes your resume stand out.

How to prepare for GSoC ?

This is a tough question to answer. The first thing you need to have is a great interest in open source contribution. If you have been already contributing to some organization, you are half way there. This is not a competition or an exam, so there is no syllabus or preset instructions. You need to be comfortable in some programming languages based on the project you choose. There are many blogs available with good articles on preparations . I have listed some which helped me in applying last year ,below.

https://www.quora.com/How-do-I-prepare-for-the-Google-Summer-of-Code-GSoC

https://shivamdixit.com/gsoc/cracking-google-summer-of-code/

https://www.sitepoint.com/google-summer-code-10-minutes-crash-course/

http://teom.org/blog/kde/how-to-write-a-kick-ass-proposal-for-google-summer-of-code/

https://github.com/solettaproject/soletta/wiki/Accepted-proposals-for-Google-Summer-of-Code-2016

My Advice from experience in 2016 GSoC?

  • Start early. Learn more about the program if you are a new comer.
  • Go through last year GSoC website and see all organization that participated and the ideas they presented.
  • Go through the proposal of previous students.
  • Go to IRC of the organization and ask how you can contribute
  • You can apply for upto 3 organizations at a time.So dont stick around with one org.
  • Some organizations require you to work on 2-3 bug fixes before you can submit proposal. Starting early  helps here.
  • Select ideas that you can implement.
  • Be really nice to people in IRC or any chat. Ask politely and help will always be there.

 

 

GSoC 2017. Final submission report

It’s been 3 months since GSoC started and finally its submission time. My work on building Strava Library in Lua is also completed. Its been very challenging to work this year on GSOC because of  health problems i faced during the summer. I am very happy that I could complete most of the work as per my proposal.

Overview

For the GSOC, I implemented a client library for Strava REST API from scratch. Using the library a user can retrieve various data from Strava,create new activities and do many more things. The following functionalities have been implemented in the Library.

Library Link

Commits link

Authorization and authentication functions 
Athletes feature (Following Functions are   implemented)
            - Retrieve current athlete  

            - Retrieve another athlete

            - Update current athlete

            - Totals and  stats

            - List Athletes

            - Documentation for the module.

   Activities feature(Following functions   implemented)

            -Create,Retrieve,Delete,Update activities

            -Comments (List activity comments)

            -Kudos (List activity kudoers)

            -List athletes activities

            -List related activities

            -List friend’s activities        

            -Documentation for the module      

    Clubs feature(Following functions are implemented) 
            - Retrieve a club

            - List club announcements

            - List athlete clubs

            - List Club members

            - List club activities   

            - Join and Leave club        

             -Documentations for the module

Gear feature(Following functions implemented)

            -Retrieve gear details

Routes feature(Following functions are  implemented)    

            -Retrieve routes

            -List route

 Running race feature(Following functions are implemented)    

            -List races

            -Retrieve race details

 

Examples    

Some examples of using the library. Full details can be found in the documentation.

Installing the library using luarocks.

 luarocks install luastrava

Importing the library.   

local strava_client = require('luastrava.client').Client

Requesting authorization

local strava=require('luastrava.client').Client
local client=strava:new()
local url=client:authorization_url{client_id=CLIENT_ID,
redirect_uri='http://strava_app.example.com/authorization'}

Fetching Token (code example is from Lapis framework based app)

 app:get("/auth",function(self)
  
   local code=self.params.code --Fetch the code sent via url parameter
            
   client:exchange_code_for_token(client_id,client_secret,code) --fetch token

  self.session.token=client:get_access_token() -- token is saved in session 

   return "Authorized token=".. client:get_access_token() --Display the token  as a proof for authorization. 
                            
end)

Retrieving Athlete details

  local athlete=client:get_athlete()
  print(athlete.firstname)

Documentation

Documentation for the library has been provided here

Demo project example

I have built a demo web project using the library to list races from Strava in google maps. This was as proposed in the proposal. A user can see the races as markers in Map in their corresponding locations. The races data is  fetched from Strava API using the library.Link

screenshots of demo app which lists races from strava in google maps. (Due to map API limitation only 10 races can be listed)

Remaining work

  • Create  functions for segments effort and streams.
  • Support uploading files from tracking devices to create activity
  • Fetching photos
  • Implement pagination support( Currently first 200 results are retrieved by api as default)

I couldn’t complete these features in time because of the health issues i had during the summer

First 2 weeks of GSoC

Related imageTwo weeks has passed since GSoC coding season started. I am working this year for organisation LabLua in building Strava Client Library.The work is progressing fast and i am updating the progress here.My mentor Andre has helped me a lot to reach here.

 

Basic functionalities

Since its a Client for REST API , i decided to start with the basic REST functionalities.(GET,POST,PUT,DELETE). Generic functions has been designed for these basic functions. Lua requests module made it extremely easy to write these functions.

API AUTHENTICATION.

Next step was to setup functions for authentication.Strava uses OAuth2 as the authentication protocol. It allows external applications to request authorization to a user’s private data without requiring their Strava username and password. It allows users to grant and revoke API access on a per-application basis and keeps users’ authentication details safe.

The authentication sends an authorize request. ClientId and Client_secret_key is required to send request for token. Once token is retrieved it is used with all other requests.

The scope parameter is used to define access rights like read,write etc.

ATHLETE FUNCTION

Strava is the site for athletes. Its API has set of functions that helps to retrieve the details of athlete .Following functions has been created for this in the library.

  1. -Retrieve current Athlete
  2. -Retrieve another athlete
  3. -Update current Athlete
  4. -Get athlete zones
  5. -Get athlete K/QOM
  6. -Get athlete stats
  7. -List athlete friends
  8. -List athlete followers
  9. -List both following

 

Plans for next two weeks

First evaluation is on June 26.I have to complete functions for retrieving Athlete activities and do the  documentations. I am planning to create github webpage for documentation and instructions to use the library .

 

 

 

 

 

 

Articulation Point.

Image result for articulation point

In graph theory, articulation point is a vertex upon its removal disconnects the graph into two components. Articulation point is very important in communication networks since it tell which all nodes upon damage will cause failure to network.

Modified DFS can be used to efficiently find the articulation point in the graphs. The idea is very simple.

  1. We start with one node as root.Run the DFS on the root node.
  2. For each node maintain two time values.
    • DiscoveryTime- Time in which the node was first reached.
    • Low Time- Low Time of a node is the lowest discovery time of all of its adjacent nodes
  3. A node is an articulation point if it satisfy any of the following properties.
    • If node is root node and node has two children.
    • If node's low time is lower than the low time of all other adjacent nodes

Lets start coding:

Lets create two functions for finding articulation point  Ap() and ApUtil();

Ap() is used to initialize all the structures we need and ApUtil() does the real work. We will write it as recursive functions.


void Ap(vector<int> adj[],int src,int V)
{
    vector<int> parent(V,-1);
    vector<int> ap(V,false);
    vector<int> visited(V,false);
    vector<int> disc;
    vector<int> low;

    APUtil(adj,src,visited,parent,ap,low,disc); //Here we call the APUtil() with root node as src

}

APUtil() function is used to carry out the actual work of finding the articulation point


void APUtil(vector<int> adj[],int src,vector<int> visited,vector<int>parent,vector<int> ap,vector<int>low,vector<int>disc)
{
    visited[src]=true;

    static int time =0;

    int children=0;

    disc[src]=time+1;

    low[src]=time+1;

    time=time+1;
    int u=src;

    for(auto i=adj[u].begin();i!=adj[u].end();i++)
    {

        int v=(*i);

        if(visited[v]==false)  {
               children++;
               parent[v]=u;
               APUtil(adj,v,visited,parent,ap,low,disc); 

               low[u]=min(low[u],low[v]);

               //conditions to check for the articulation points

               if(parent[u]==-1 && children>1)
                             ap[u]==true;

               if ( parent[u]!=-1 && disc[u]<=low[v])
                             ap[u]=true;

                               }
         else if(v!=parent[u])
               {

                  low[u]=min(low[u],disc[v]);
               }

     }

}

Complete code:

#include <bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define INF 1000000

void addEdge(vector<int>adj[],int u,int v)
{
	adj[u].pb(v);
}	

void APUtil(int u,vector<bool> visited,vector<int> disc,vector<int> parent, vector<bool>ap,vector<int> adj,int V)
{
	static int time=0;

	int children=0;

	visited[u]=true;

	disc[u]=low[u]=++time;

	for(auto i=adj[u].begin();i!=adj[u].end();i++)
	{
		int v=(*i);

		if(!visited[v])
		{
			children++;

			parent[v]=u;
			APUtil(v,visited,disc,parent,ap,

			 low[u]  = min(low[u], low[v]);

            if (parent[u] == NIL && children > 1)
               ap[u] = true;

            if (parent[u] != NIL && low[v] >= disc[u])
               ap[u] = true;
		}

		 else if (v != parent[u])
            low[u]  = min(low[u], disc[v]);

	}

}

void ap(vector<int> adj[],int s,int V)
{
	vector<bool> ap;
	vector<int> parent(V,-1);
	vector<int> low;
	vector<int> disc(V,0);
	vector<bool> visited(V,false);

	for(int i=0;i<V;i++) 		if(!visited[i]) 			APUtil(i,visited,disc,parent,ap,adj,V); 	 	 } int main() { 	int V; 	cin>>V;

	vector<int> adj[V];

	return 0;
}

Reference : https://www.youtube.com/watch?v=2kREIkF9UAs

Goals for next 5 years.

I will list all the goals for next 5 years in my life as a todo list here and tick off the ones that are completed.

 

  • Learn Car and Bike
  • Hit Gym 
  • Commit to gihub for a month continuosly
  • Lose fat and build 6 pack abs
  • Read top 5 must read books
  • Donate blood
  • Build an android program
  • Start sport programming
  • Learn martial arts
  • Learn Yoga
  • Get decent score in GATE with minimal preparation
  • Participate in ACM ICPC
  • Participate in Fb hackercup 2017
  • Participate in Google codejam 2017
  • Do google summer of code
  • Solve a problem in codeforces
  • Solve a problem in Topcoder
  • Learn machine learning
  • Build a chat bot
  • Start a new venture
  • Pitch a product and get funding.
  • Get self-independent financially.
  • Travel to a European nation
  • Gift something to achan , amma and kannan
  • Buy a luxury car/ bike
  • Buy food for someone who is starving
  • Donate money to a charity/ orphanage