When Randomness meets Automation- The Intersection of Cryptography with Machine Learning

Author- Anuj Srivastava

Here is a brief summary, or rather the cornerstone of what Dr. Arpita Patra, a renowned faculty and esteemed researcher of IISc Bangalore had rendered us in her motivating lecture on 26/06/19 along with some farrago of my outlook. The 16th day of ACM India summer school(IIIT Bangalore).

We are talking about two stalwarts of Computer Science. Yes! the Machine Learning and the Cryptography. With the unprecedented use of machine learning in almost every domain like facial recognition, medical, finance, banking, etc. So, machine learning is touching our lives and making it better. But recall one thing, an ML algorithm can build a very good model only when it is fed with a sufficiently huge amount of data. Otherwise, it will be not suitably accurate. But the question is from where do you get the data? Data is the private property of individuals or organizations. It is often said that "Data is the new Currency" They generally don’t like to share. So, its where the cryptography comes into play. It promises the person or the organization to keep their data secure and private. It gives us a technique where we can jointly run a cryptographic protocol that will allow us to train a model on the joint database altogether hold but without compromising the privacy of the individual databases. This is called as Federated learning or Secure ML. That’s the promise that cryptography gives to ML. The data on which ML algorithms are used are not unlawfully used. For instance in the area of self-driving cars Companies like Tesla, BMW, Volkswagen, etc are coming together to make this possible and all of them hold their individual databases and want to build a model but at the same time, they are in business competitors so they don’t want to share their databases with each other. But cryptography is a technique which can and is bringing them together to train their model on a joint database and they need not compromise the privacy of their databases. To make life more comfortable.

There are many techniques like practical instantiations of secure multi-party computation (MPC), fully homomorphic encryption (FHE), etc. by which this can be achieved.

Cryptography can safely be said as "The Science of Secrets"

From art to science, from informal to become a part of formal computer science. Randomness is very important in cryptography as water in our lives. 

Let’s say there is a smart guy called X who secretly got access to your communication channel. Since this guy has access to your communication, he can do much more than just eavesdropping, for example, he can try to change the message.  Now, this is just a small example. What if Eave gets access to your private information? The result could be catastrophic.

So, Encryption is essentially important because it secures data and information from unauthorized access and thus maintains confidentiality. 

Cryptocurrencies use cryptography for three main purposes; to secure transactions, to control the creation of additional units, and to verify the transfer of assets. To accomplish all of these things, cryptocurrencies rely on what is called “public key cryptography.” With the advent of Bitcoin and the recent launch of Facebook's Libra as cryptocurrencies. I believe the responsibility of cryptography has increased and at the same time, it has to explore new possibilities to make the world a better and safer place.

 Machine Learning  "The art of automating automation"

Thanks to machine learning, there's never been a more exciting time in the history of computer science. Every day, new breakthroughs are changing what's possible with computers. 

ACM India Summer School on Algorithmic and Theoretical Aspects of Machine Learning

Author: Amit Rajashekhar Lambi

The ACM summer school conducted at IIIT Bangalore between 10th to 28th June 2019 was a awesome experience, I will try my best to summarize my experience as below.


ACM India Summer School Objectives:

Inculcating problem solving as a skill, which is not emphasized much in the undergraduate curriculum Providing exposure to leading experts, advanced topics and taste of research to motivated students Exposing students to research opportunities in the career, whether in academia or industry Conducted by faculty comprising leading experts from academia and industry on advanced topics in computer Science


TFoCS School at IIIT Bangalore  :

This school which was on theoretical aspects of machine learning, which is aimed to give a very brief insights on multitude of topics relevant in the industry and research, the school starts off with brushing your basics in linear algebra and probability theory, I would recommend having a read through this topics beforehand for having a more enjoyable experience.

The topics covered include supervised and unsupervised learning, Artificial neural networks, algorithmic design strategies, program synthesis meets ML, optimization, reinforcement learning, Intro to cryptography, compressed/ sparse coding, Enterprise Application of ML, computational learning theory, privacy preserving using ML, finite state Automata and deep learning.

The Speakers
we've had speakers from most prestigious universities/IT industry professionals in India and guest lectures from Sriram Rajamani who is the Managing Director of  Microsoft Research India Lab, his lecture on program synthesis was an eye opener and the fact that he shared a research paper with us which was yet to be published made it even better, we also had a guest lecture by Dr. Jai Ganesh who works with Mphasis, he gave us a very crucial insight on the trends of ML applications in the Industry,  Dr. Arpita Patra from IISc has taught us Cryptography and Secure ML. Finally, Prof. Meenakshi D'Souza from IIITB has taught us Learning on Automata and Decision Tree.

I would also like to thank the Organizing  team who have been very helpful with our tutorial sessions and syncing with summer school participants  thru social media group


I would like to conclude by saying that don's miss these kind of summer school opportunity as It will surely open up good avenue in your career.


Thanks & Regards,
Amit

Journey From Spiritual Capital of India Varanasi ( BHU ) To Silicon Valley Of India Bengaluru ( IIITB )

Summarization of ACM India Summer School 2019

Author: Kumar Ritu Raj Bharti

Travel:

Whenever we plan to go at unknown place that we never visited before. First thing strike in our mind is that what is the best place there for excursion. Like that I also have the same mentality ( Searched and planned the excursion, how to visit all beautiful place in the short period of time ). Now the story begins. While travelling from Banaras Hindu University to IIITB, we* faced so many problem but it did not impact on us due to the excitement we* have to come to attend the ACM Summer School 2019. We* started travelling from June-06-2019 and reached by June-09-2019. Finally got Hostel inside the campus, took rest and was thinking that as time will pass --> how the class will go because by the next day we were about to attend the class.

Journey of Summer Class in IIITB:

Now the time came to attend the first class of this summer school. there was so many thing happening inside mind. The first lecture is delivered by the renowned faculty of IITB named as Prof. Amit Chattopadhyay on Linear Algebra. Oh Sorry, I forgot to mention the time of the class, class is divided in number of slots, there are four(4) slots, which we have to attend. It is not mandatory that all the slot is provided to the same faculty, there was a mix order of faculty so that the student did not feel bore at any point of time. After attending the first slot, i understood that Yes it is going in right direction so that i can learn deeply a basic view of such area which will be helpful in determining the career in Machine Learning. The one and only Prof. G. Srinivasaraghvan sir ( My Favourite ) from IIITB, what i spoke about him, will lead to small and small. The way he taught us "Probability Theory and Learning Theory" was absolutely charmed. There were so many renowned faculty from different part of India. Prof. Ganesh Ramakrishnan who is from IITB has taught us Supervised Learning, Unsupervised Learning and Artificial Neural Network. Prof. Pradeesha Ashok from IIITB has taught us Algorithm Design Strategy. The one, Prof. Sriram Rajamani who is a distinguished scientist and managing director of Microsoft Research India has taught us "Program Synthesis meets ML" the most exciting topic for me after knowing something. Dr. Praneeth Netrapalli who is researcher at Microsoft Reseach India has taught us about Optimization. Prof. Prasanth L.A who is from IIT madras has taught us Reinforcement Learning. Prof. Srinivas Vivek who is from IIITB has taught us Cryptography. Prof. Ajit Rajwade from IITB has taught us Compressed Sensing. Dr. Jai Ganesh who is president of Mphasis Next Lab has taught us about Application of Machine Learning and i feel goosebump so many times when he was teaching us because i was knowing for the first time the application that he was telling. Dr. Arpita Patra from IISC has taught us CRIS( Cryptography and Information Security ). Finally, Prof. Meenakshi D'Souza from IIITB has taught us Learning on Automata and Decision Tree. Last but not the list Thanks to all the TA who guide us during the tutorial session, they are very supportive and behave like elder brother and sister.

Weekend:

On the first saturday of the Summer School, we watched INSOMNIA (means Poor Sleeping Habit) movie and the next day become the sunday as funday for us by watching the special match between INDIA vs PAKISTAN which was screening on five(5) multiple screen at the same time, its feel like live watching the special match. On the second saturday, we had went for Excursion (GUHANTRA) in bengaluru, there by we enjoyed as much as possible. We played Dumbshiraz, Truth and Dare, Volleyball, Tug of War, Cricket and the special one "Rain dance" as well as we bath their in Swimming Pool and these are possible because of the presence of Prof. Srinivas Vivek sir.

Conclusion:

I would like to conclude by saying that if you get the opportunity to attend the Summer School, feel free to come here by not bothering about anything beacause you have a chance to interact with the renowned faculty of india and your thinking level may boom to the next level. Also the important part is the food and room you get here is fantastic.

FINALLY, thank you ACM INDIA and IIITB for giving me such a good opportunity to participate in the ACM SUMMER SCHOOL 2019.

Note:- i used we* so many times because we came here four participant from the same department of BHU.

ACM summer school 2019

Author: Jay gaglani
 
The summer school conducted at IIIT Bangalore between 10th to 28th was a mixed ride, I will try my best to summarize my experience below for people looking to enjoy this experience in the future.

The Summer school
This school which was on theoretical aspects of machine learning, which is aimed to give a very brief insights on multitude of topics relevant in the industry and research, the school starts off with brushing your basics in linear algebra and probability theory, I would recommend having a read through this topics beforehand for having a more enjoyable experience.

The variety of topics are very vast and you are bound to find one which piques your interest.
the topics covered include supervised and unsupervised learning, Artificial neural networks, algorithmic design strategies, program synthesis meets ML, optimization, reinforcement learning, Intro to cryptography, compressed/ sparse coding, Enterprise Application of ML, computational learning theory, privacy preserving using ML, finite state automaton and deep learning.

The Speakers
Hands down the most outstanding part of this school, we've had speakers from most prestigious universities in India and guest lectures from Sriram rajamani who is the Managing Director of  Microsoft Research India Lab, his lecture on program synthesis was an eye opener and the fact that he shared a research paper with us which was yet to be published made it even better, we also had a guest lecture by Dr. Jai Ganesh who works with Mphasis, he gave us a very crucial insight on the trends and demands in the Industry.

I would also like to thank the TA's who have been nothing but helpful with our tutorial sessions and doubts even outside of the summer school hours

Other Participants
you'll find participants from all over the country, participants who are pursuing their B.tech, M.tech, Bsc, Msc, PhD and even other teachers, this was very surprising but most welcome.

Logistics and food
the rooms and food was way better than your average hostel mess, there isn't much to say except you don't need to worry about accommodation and food

I would like to conclude by saying that don's miss this school, you won't become an overnight expert but your career will sure open up to endless possibilities you didn't know before. 

Cryptography

ACM Summer School - IIIT Bangalore
Author: Ananth Adiga



I wanted to summarize what happened on the 10th day of summer school i.e 21st of June. Prof. Srinivas Vivek started the day by giving out a formal definition and break down of the word " cryptography ".
Krypto's - Hidden/Secret
Graphia- To write
So basically hiding your message so that only the person who knows the secret can access it.
The very same definition is can modified to fit in the field of computer science. Encrypting the message to stop unwanted access. Without cryptography, safe banking wouldn't be possible, your credit card details would be surfing around the internet.
cryptography provides us with the following
->Authentication
->Confidentiality
Authentication guarantees that only person with access can read/use the message.
Confidentiality guarantees the safety of the message. To keep the message secret in other words.

Cryptography overlaps with four fields namely social science, politics, law, economics. All these are interlinked and it is very much needed. Consider cryptography without law, what will happen? It's really hard to imagine cryptography without law. If there is no law that governs cryptography then it crumbles. Example- Postcard if there is no law that governs the illegal access of your postcard then anyone can open it and read sensitive details.

let's consider the first use of cryptography, it was in the 16th century a person called cypher introduced cryptography to the world. The concept was simple, you take a message and use a key to convert that to a non-human readable form and pass it, only the person with the key can read it. Key basically can be visualized as actual key and a lock. You place the message inside and lock it and the person with the key can open it.
To give a better explanation I would take a simple example. Consider John who wants to send a message to Ted but to do so he should ask Alex who is a messenger to deliver it to Ted and John wants the message to be encrypted. So he decided he in encrypts the message with a key
Message-                        " I ran out of money "
The encrypted message  "D udq rxw ri prqhb"
Key 3
What do you think of the encrypted message? It seems to be encrypted right? So how did the message  " I ran out of money " converted into "D udq rxw ri prqhb"? That's a big question mark. But the answer to that question is simple, you take the message and add 3 to each and every letter, a+3 is converted to 'd' same way all the rest of the letter.
This was a prolific method for some time but soon people started to crack it and they needed a better method so slowly one by one new method which was robust were built and in some time people started to crack it so this war of creating a robust method and cracking it continued, even today this war exists.
Today we have a method called RSA 1024 which stands for Rivest, Shamir, and Adelman. These three are the creator of this method. It all started with with a number less than 1024 maybe 128 but people started to crack it and then they moved to RSA 512 and then it was cracked and now we are at 1028 which quantum computers can solve easily.
So what does this number quantifies to? This number indicates a 1024 long prime number. p=1024 bits long prime number which is really huge and you multiply with q which is also a 1024 bit prime number so what you get is 2 power 11-bit number 'n' which is a composite number. A composite number is a number which can be divided by 2 or more numbers but prime numbers can only be divided by 1 and itself. So we use this  'n' in the future calculation. The important thing here is that if you know p and q from n then you can crack RSA 1024, let's be practical its really difficult to know p and q cause n is huge.
This was a short summary of the day, I haven't covered many topics which was taught that day, so by this I want to end this blog.
Thank you.

Probability Tail Bounds/ Concentration bounds

Author: Pooja Yadav

A variable with good concentration is one that is close to its mean with good probability. A "concentration inequality" is a theorem proving that a random variable has good concentration. Such theorems are also known as "tail bounds".

In a variety of settings, it is of interest to obtain bounds on the tails of a random variable or two-sided inequalities that guarantee that a random variable is close to its mean or median.

The role of inequalities is that you get bounds on probabilities of certain events. Inequalities are a definite fact about the randomness of an event. For instance, one can be able to say that the probability of an event happening is less than or equal to a definite number. 

In this blog, we explore a few elementary techniques for obtaining concentration inequalities.

1. Markov's Inequality

The most elementary tail bound or the simplest concentration inequality: Markov's Inequality.

It is often useful in scenarios where not much concentration is needed, or where the random variable is too complicated to be analyzed by more powerful techniques. The downside is that it only gives very weak bounds, but the upside is that it needs almost no assumptions about the random variable.

Theorem: Let X be a random variable that takes only non-negative values, then for any real number a>0, 

Pr[X ≥ a] ≤ E[X]/a

Proof: Let I be the indicator variable such that

                                                                  I = 1      if X ≥ a

 = 0      otherwise

           Now, X ≥ a 

                ⇒ 1 ≤ X/a

                ⇒  I ≤ X/a

          Taking expectation on both sides, we get

          E[I] ≤ E[X/a] = E[X].(1/a) (inequality remains unchanged as X takes only non-negative values)

          Therefore, we get

          Pr[X ≥ a].1 + Pr[X < a].0   ≤   E[X].(1/a)   (Using the definition of Expectation)

          i.e.  Pr[X ≥ a]   ≤   E[X]/a

          Hence, proved.

  
                       

2. Chebyshev's Inequality

Chebyshev's Inequality states that the difference between X and E[X] is somehow limited by Var(X). This is intuitively expected as variance shows on average how far we are from the mean.

Theorem: If X is a random variable with finite mean μ and variance σ², then for any k>0,

Pr(|X-μ| ≥ k) ≤  σ²/k²

Proof: Let Y =(X-μ)² ≥ 0 and a = k²

            Using Markov's inequality gives 

                            Pr((X-µ)² ≥ k²)  ≤  E[(X-µ)²]/k²

            But (X-μ)² ≥ k²  holds iff |X-μ| ≥ k holds, since k>0

            Therefore,                           

                             Pr(|X-μ| ≥ k) ≤  σ²/k²   

            ^{Often, we are asked to obtain a bound for} Pr(|X-μ| > k).

            Since, Pr(|X-μ| ≥ k) ≤ Pr(|X-μ| > k), Chebyshev's bound of σ²/k² is valid for Pr(|X-μ| > k)                     also.

Sample Problems

Que 1. Let X = exp(λ). Using Markov's inequality, find an upper bound for P(X≥ a). Compare the upper bound with the actual value of P(X ≥ a).

Solution: If X = exp(λ)  ⇒ E[X]=1/λ

                 Using Markov's Inequality, we get

                 P(X ≥ a) ≤ E[X]/a = 1/λa

                 The actual value of P(X ≥ a) is e^-ƛa, and we always have 1/λa ≥ e^-ƛa

                 

Que 2. Let X = exp(λ). Using Chebyshev's inequality, find an upper bound for P(|X-μ| ≥ b).
Solution: We have, E[X] = 1/λ and Var(X) = 1/λ^{2
                     Using Chebyshev's Inequality, we get} 
                                                   P(|X-μ| ≥ b) ≤ Var(X)/b2 = 1/λb²
                                        

Algorithm Design Techniques

Author: Harsha P Dixit


"Algorithms are to computer programs as recipes are to cooking"

The lecture on Algorithm Design Techniques was taken by Prof. Pradeesha Ashok, and covered the following -

Divide and Conquer

As the name suggests, divide and conquer method reduces a given problem into smaller problems recursively until they are small enough to be solved directly, and then appropriately combines the solution.

Example - Merge Sort. 

The two important tasks in Merge Sort are dividing the array into smaller units, and merging two sorted units into a larger sorted array. It divides the array into smaller units recursively until only one element is in each unit (single element is trivially sorted), and then merges the sorted smaller units into larger sorted array.
For example - consider an array [4 5 1 2 7 8] which needs to be sorted.
Dividing and merging step by step:

1. [4 5 1]    [2 7 3]
2. [4 5]    [1]     [2 7]    [3]
3. [4]    [5]    [1]    [2]    [7]    [3]
4. [4 5]    [1]    [2 7]    [3]
5. [1 4 5]    [2 3 7] 
6. [1 2 3 4 5 7]

Time complexity of Merge Sort is O(nlogn)

Greedy

Greedy algorithms arrive at the final solution by making the best possible choice at every step. Since they cant back-track, it is critical that they make the correct choice in every step. Greedy algorithms can be applied only if the global optimal solution for the problem is obtained by choosing the local optimal solution for every sub problem. Generally, if applicable, greedy algorithms are more efficient than other techniques.
This is how a greedy algorithms work -

1. Select greedy choice
2. Convert problem into subproblem of smaller size
3. Repeat

Example - Fractional Knapsack problem

Assume you are carrying food for everyone in a picnic. Your bag can only carry 4 KG, and you have to choose between three food items, Pizza (2 KG), Tacos(2 KG) and Cake (3 KG) which give 100, 10 and 120 KCal of energy respectively. Since you want everyone to have sufficient nutrition, you want to maximise the amount of calories you carry, while not exceeding 4 KG. You can carry a fraction of items too.

Greedy approach to solve this is by first calculating Calories per KG, and making the greedy choice at every step. 

Calories per KG: Pizza: 100/2 = 50 (How I wish this was true in real life!) , Tacos: 10/2 = 5 and Cake: 120/3 = 40.

The most greedy choice is to first load up on Pizza, and then as much Cake as possible. So, the greedy solution is to carry 2KG of Pizza and 2 KG of cake, totalling 180 KCal.

Greedy approach may not work for every problem. For instance, it fails for 0-1 Knapsack problem - which can be solved by Dynamic Programming.

Dynamic Programming

Like divide and conquer, Dynamic programming also divides the given problem into smaller subproblems, solves them, stores the results and then combines the solutions. However, this method is only useful when the following conditions are satisfied:

• Overlapping Subproblems : This method is useful when overlapping subproblems exist as it avoids solving the same problems again by storing the results.
• Optimal Substructure : A given problem has Optimal Substructure if the optimal solution to it can be obtained using optimal solutions to its subproblems. 

When to use Dynamic Programming -

• Small number of sub problems
• When solution to larger problem obtained by solving smaller ones
• When natural ordering exists

Dynamic programming algorithm design-

• Identify subproblem
• Define Recurrence
• Implement in bottom up manner 

Example: Maximum Independent Set in a path

Consider a vertex weighted path consisting of n vertices. The goal is to obtain a set of vertices which are not adjacent to one another and whose sum of weights is maximum.

Let G be the graph with n vertices - G(v_1, v_2, ..... , v_n), with w_i representing the weight of i-th vertex.

Let MIS(i) be the value of Maximum Independent Set of vertices {v_1, v_2 ... v_i}. (this is the subproblem)

We know that if v_i is in not in the solution :

MIS(i) = MIS(i-1)

If v_i is in the solution:

MIS(i) = w_i + MIS(i-2) (because v_(i-1) can't be in solution if v_i is there)

If we try to solve this by recursion (top down approach), it takes exponential time to run as subproblems are solved multiple times (because of overlapping subproblems). However, if we store the solutions to sub problems, we can obtain linear running time.

The algorithm to solve this -

MIS(1) = w_1

MIS(2) = maximum(w_1,w_2)

for i=3 to n:

   MIS(i) = maximum(w_i+MIS(i-2), MIS(i-2))