কিন্তু গ্রেডিয়েন্ট ডিসেন্ট নামটা শুনলেই আমাদের চোখে ভাসে নিচের মতো কিছু ঝাঝালো 3D সারফেস প্লটের ছবি।

কি ভয়ংকর দেখতে! সাথে আছে এর বিদঘুটে ম্যাথম্যাটিক্যাল ফর্মুলা!

কিন্তু, জিনসটা দেখতে যতোটাই ভয়ংকর, আসলে ততোটাই সহজ, মজার এবং প্র্যাক্টিক্যাল।

চলুন প্রথমেই আমরা এই ঝাঝালো প্লটের ছবি ও গ্রেডিয়েন্ট ডিসেন্ট নিয়ে যতো ভয়ানক অভিজ্ঞতা আছে সব ভুলে যাই। আবার নতুন করে শুরু করি চলুন -

সাধারণ ও বাস্তব ধারণাঃ

ধরুন, আমরা একটি পুকুরের (গ্রীষ্মের কড়া রোদে পানি শুকিয়ে যাওয়া পুকুর) পাড় থেকে একটি ফুটবল ছেড়ে দিলাম। ঠিক নিচের ছবিটির মত। এখন ঘটনাটা কি ঘটবে?

যেহেতু আমরা জানি যে পৃথিবীতে অভিকর্ষজ ত্বরণ কাজ করে তাই বলটি গড়িয়ে গড়িয়ে পুকুরের ঢালু জায়গার দিকে যেতে থাকবে। যখন পুকুরের সবচেয়ে গভীরে / ঢালু জায়গাটিতে পৌঁছে যাবে তখন বলটি স্থির হয়ে যাবে।

বিষয়টিকে আমরা এভাবেও বলতে পারি যে, বলটি পুকুরের সবচেয়ে মিনিমাম পয়েন্টে যেয়ে থামবে।

এবার কিছু বাচ্চাকালের ম্যাথেমেটিকাল জিনিস দেখা যাক -

ধরুন, আমাদের একটি ফাংশন দেয়া হলো f(x) = x² + 5,

সাথে দেয়া হলো x এর কিছু ভ্যাল্যু, x =−6,−5,−4,−3,−2,−1,0,1,2,3,4,5,6

এখন আমাদের কাজ হলো ফাংশনটার সবচেয়ে মিনিমাম ভ্যালুটা বের করা। অর্থাৎ, আমরা এমন একটি ভ্যালু বের করবো যে ভ্যালুটাকে যদি ফাংশনের x হিসেবে ইনপুট দেই তাহলে ফাংশনটা সবচেয়ে মিনিমাম ভ্যালু আউটপুট দিবে।

তাহলে এবার ফাংশনে x এর ভ্যাল্যু গুলো বসিয়ে দেখি আউটপুট হিসেবে কি ভ্যালু পাচ্ছি -

উপরের টেবিল দেখে আমরা সহজেই বুঝতে পারছি যে x এর ভ্যালু 0 এর জন্য আমরা ফাংশনের সবচেয়ে মিনিমাম ভ্যালু 5 পাচ্ছি।

এই জিনিসটুকুকে আমরা পাইথন কোডে নিচের মতো করে লিখতে পারি -

Output:
[-6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6]
[41 30 21 14  9  6  5  6  9 14 21 30 41]

এবার চলুন দেখা যাক ভ্যালু গুলোকে গ্রাফে রিপ্রেজেন্ট করলে কেমন দেখায় -

গ্রাফ থেকেও দেখা যাচ্ছে যে x=0 এর জন্য আমরা ফাংশনের সবচেয়ে মিনিমাম ভ্যালু y=5 পাচ্ছি।

চমৎকার বিষয়টি হলো আমাদের ফাংশনের গ্রাফটি উপরে পুকুরের ছবিটির সাথে মিলে গেছে। এবার শেখা আরো সহজ হয়ে গেলো।

এবার আমরা যদি গ্রাফের উপরের কোন একটা পয়েন্টে ফুটবলটা রাখি, তাহলে কি ঘটনা ঘটবে?

কিছুই ঘটবে না!! বলটা যেখানে রাখা হয়েছ সেখানেই থাকবে। কেননা পৃথিবীতে অভিকর্ষজ ত্বরণ কাজ করে তাই পুকুরের পাড় থেকে বলটি গড়িয়ে ঢালু দিকে নামছিলো কিন্তু আমাদের গ্রাফেতো আর অভিকর্ষজ ত্বরণ কাজ করে না।

তাহলে আমরা কিভাবে বলটাকে গ্রাফের মিনিমাম পয়েন্টে নিয়ে যেতে পারি? এক্ষেত্রে আমাদের ২ টা জিনিস জানা লাগবে -

• গ্রাফের ঢাল কোন দিকে (এই জিনিসটা আমরা জানতে পারবো গ্রেডিয়েন্ট থেকে)
• কতো ইউনিট করে আগাতে হবে (এটা আমরা নিজেরা ঠিক করে নিতে পারবো)

এবার চলুন গ্রেডিয়েন্ট ডিসেন্ট সম্পর্কে কিছু জেনে নেই। দেখি ইহা খায় না মাথায় দেয়।

গ্রেডিয়েন্ট ডিসেন্ট

গ্রেডিয়েন্ট ডিসেন্ট হলো একটি ফার্স্ট অর্ডার আইটেরেটিভ অপ্টিমাইজেশন অ্যালগোরিদম যা কোন একটা ফাংশনের মিনিমাম ভ্যালু খুজে বের করে দেয়।

ফার্স্ট অর্ডার, আইটেরেটিভ এগুলো কি তা একটু পরেই বুঝবো। গ্রেডিয়েন্ট ডিসেন্টে ব্যবহৃত ফর্মুলাঃ

এই ফর্মুলাই আমাদের বলে দিবে বলটি যেখানে আছে সেখান থেকে কোন দিকে কতোটুকু করে আগাতে হবে।

এই ফর্মুলাকে অনেক জায়গায় ভিন্ন নোটেশনেও লেখা হয়। যেমনঃ

এবার ফর্মুলার নোটেশন গুলোর অর্থ বুঝে নেইঃ

γ (লার্নিং রেট) তো আমরা নিজেরা সেট করে দিতে পারবো কিন্তু আমাদের মাথা ব্যাথা হলো কিভাবে x এর জন্য F ফাংশনের গ্রেডিয়েন্ট বের করবো, অর্থাৎ কিভাবে ∇F(Xn) বের করবো।

ফাংশনের গ্রেডিয়েন্ট বের করার নিয়মঃ

কোন একটা ভেরিয়েবলের জন্য কোন ফাংশনের গ্রেডিয়েন্ট হলো সেই ভেরিয়েবলের সাপেক্ষে ফাংশনটিকে একবার ডিফারেনশিয়েট করলে যা পাওয়া যায় তা।

অর্থাৎ, x এর জন্য F এর গ্রেডিয়েন্ট হবে x এর সাপেক্ষে F কে একবার ডিফারেনশিয়েট করলে যা পাবো তা।

ফাংশনটাকে একবার ডিফারেনশিয়েট করলে যা পাবো সেটাকে ওই ফাংশনের ফার্স্ট অর্ডার ডেরিভেটিভ বলে।

তাহলে চলুন দেখি আমরা x এর জন্য f(x) = x² + 5 ফাংশনটার গ্রেডিয়েন্ট বের করে ফেলি।

আমরা যদি ক্যালকুলাস ভুলে যাই তাহলেও কোন ব্যাপার না। পাইথনের sympy প্যাকেজ দিয়ে আমরা কোন একটা ফাংশনের ডেরিভেটিভ বের করতে পারবো।

যেমনঃ নিচে দেয়া পাইথন কোডে আমাদের ফাংশনটার ডেরিভেটিভ বের করে দেখানো হয়েছে।

Output:
2*x

প্রশ্ন হতে পারে যে আমরা এখানে কেনো ফার্স্ট অর্ডার ডেরিভেটিভ নিলাম, ২/৩ বার ডিফারেনশিয়েট করে নেয়া যেতো না?

ফার্স্ট অর্ডার ডেরিভেটিভ নেয়ার কারন হলোঃ

• একটা ফাংশনের ডিরেকশন কোন দিকে, ফাংশনটি ইনক্রিজিং না ডিক্রিজিং সেটা ওই ফাংশনের ফার্স্ট অর্ডার ডেরিভেটিভ থেকে জানা যায়। (এটাই আমার দরকার)
• ফার্স্ট অর্ডার ডেরিভেটিভ দিয়ে ফাংশনের ঢালও প্রকাশ পায়

গ্রেডিয়েন্ট এবং ফার্স্ট অর্ডার ডেরিভেটিভ বুঝে থাকলে এবার আসি গ্রেডিয়েন্ট ডিসেন্টকে আইটেরেটিভ কেনো বলা হয়। গ্রেডিয়েন্ট ডিসেন্টের যে ফর্মুলাটা আমরা উপরে দেখলাম সেটি আমাদের পরবর্তী এক স্টেপের জন্য কোন দিকে কতটুকু করে আগাবো তা বলে দেয়। কিন্তু আমাদের তো শুধু এক স্টেপ আগালেই হবে না। আমাদের ততোক্ষণ পর্যন্ত আগাতে হবে যতক্ষণ না আমরা সবচেয়ে মিনিমাম পয়েন্টে পৌছে যাই। তাই আমাদের এই প্রসেসটা একটা লুপের মাধ্যমে নির্দিষ্ট সংখ্যক বার চালাতে হবে।

তাহলে এবার আমরা গ্রেডিয়েন্ট ডিসেন্ট অ্যালগোরিদমটাকে আরেকটু সুন্দর করে গুছিয়ে লিখি -

এখন গ্রেডিয়েন্ট ডিসেন্টের কোড করার জন্য আমাদের যা যা জানা দরকার সব আমরা জেনে ফেলেছি। এবার ঝটপট কোড লিখে ফেলি চলুন -

• আমরা লার্নিং রেট γ (gamma) এর মান ধরবো 0.001। আমরা যদি লার্নিং রেটের মান খুব বেশি ধরি তাহলে প্রতি আইটেরেশনে আমরা বেশি ইউনিট করে এগিয়ে যেতে পারি, ফলে আমাদের মিনিমাম পয়েন্টকে ক্রস করে যাওার একটা সম্ভাবনা থাকবে। তাই আমরা লার্নিং রেট হিসেবে 0.001 ধরলাম।
• এবার আমাদের কোন একটা ভ্যলু সেট করতে হবে যেখান থেকে আমরা স্টার্ট করবো। তাই x এর ইনিশিয়াল ভ্যালু 6 ধরে নিলাম।
• এবার কতগুলো আইটেরেশন চালাবো সেটা ঠিক করতে হবে। আমরা 5000 বার চালিয়ে দেখবো।

দেখা যাচ্ছে লুপ 5000 বার চালালেই আমরা x এর ভ্যালু 0.00026968555624761565 পেয়ে যাচ্ছি যেটা 0 এর খুবি কাছাকাছি। এটাকে ইন্টিজারে নিলে আসলে আমরা 0 ই পাবো। তাহলে পেয়ে গেলাম আমাদের কাংক্ষিত x এর মিনিমাম ভ্যালু যার জন্য আমাদের ফাংশনটি সবচেয়ে মিনিমাম আউটপুট 5 দিবে।

এবার আমরা গ্রাফে তাকালে দেখবো বলটি ঢালু দিকে গড়িয়ে আগাতে আগাতে মিনিমাম পয়েন্ট 0 তে গিয়ে পৌছাচ্ছে।

তো এই হলো গ্রেডিয়েন্ট ডিসেন্টে!!

এই লেখাটিতে আমার উদ্দেশ্য ছিলো গ্রেডিয়েন্ট ডিসেন্টের খুবি ব্যাসিক ধারনা দেয়া। তাই আমি ম্যাথেমেটিক্যাল বিষয়গুলো নিয়ে খুব বেশি গভীরে যাইনি।

বোঝার সুবিধার জন্য আমি এখানে খুবি সিম্পল একটি ফাংশন নিয়েছি এবং শুধুমাত্র একটি প্যারামিটার নিয়ে কাজ করেছি। কিন্তু গ্রেডিয়েন্ট ডিসেন্টের আসল অ্যাডভান্টেজ অনুভব করা যাবে যখন আমরা মাল্টিপল প্যারামিটারের জন্য কাজ করবো। পরবর্তী লেখাতে আমরা দেখবো কিভাবে লিনিয়ার রিগ্রেশনের ইরর / কস্ট মিনিমাইজ করতে গ্রেডিয়েন্ট ডিসেন্ট ব্যবহার হয়। সেখানে আমরা মাল্টিপল প্যারামিটার নিয়ে কাজ করবো।

সেই পর্যন্ত আপনারা যতটুকু শিখলেন তা ব্যবহার করে আরো ভিন্ন কিছু ফাংশন নিয়ে কাজ করে দেখুন।

Many of us are already familiar with Gradient Descent but have bitter experience in understanding it. When we think about gradient descent, we remember the terrible mathematical formula and see some horrible pictures of the 3D surface plot in our eyes like the following -

How terrifying the picture is as well as it’s formulas! But, it is actually not like how it looks. It is very easy, interesting and very practical concept.

So, let’s forget the terrifying plots, formulas and the bitter experiences and make a new start.

Some Basic Real-World Concept:

Let’s say, we put a ball on the upper edge of a pond and give a little push on it, just like the following picture. Now, what will happen?

As we know, there is a gravitational force on earth, so the ball will roll towards the lower region of the pond. It’ll keep rolling until it reaches the lowest point of the pond. In other words, we can say that the ball will stop when it reaches the minimum point of the pond.

Now, let’s discuss some childhood mathematical concepts.

Let, we have a function, f(x) = x² + 5 and we also have some values of x.
x =−6,−5,−4,−3,−2,−1,0,1,2,3,4,5,6

Now, our task is to find the minimum value of the function. That means, we need to find such an input value for the x for which we’ll get the minimum output value from y.

Now, let’s put all the given values of x into the function and see the output values of y.

From the table, we can see that when we put 0 in x, we are getting the minimum value 5 from y.

We can write the above function and generate it’s output in Python code as below –

Output:
[-6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6]
[41 30 21 14  9  6  5  6  9 14 21 30 41]

Now let’s see, for the given values how the function looks like in graphical representation.

The most interesting fact here is, the plot looks same as the picture of the pond we’ve used above.

That’s great! Our learning has become much easier. 🤘

Now, if we put a ball on the upper edge of the plot and give a little push on it, as we done before in the pond picture. What will happen?

Nothing will happen. Because the gravitational force works on earth, not on our plot. The ball will remain in the same position where it was put before. Then, how can we take the ball to the minimum point of the graph?

To do this, we need to know 2 things-

👉 The direction of the slope (We can know this from the gradient.)

👉 By how many units we need to roll. (We can set this value by our own.)

Now, it’s time to know about the Gradient Descent. Let’s see how can it help us.

Gradient Descent:

Gradient Descent is a first order iterative optimization algorithm that finds the minimum value of a function.

We’ll know what it means by “first order” and “iterative” later.

The formula used in Gradient Descent:

The formula will tell us the next position of the ball. It’ll tell us the direction of the downward slope with the number of units to roll.
You’ll find this formula written with different notation as follows –

Now, let’s learn the meaning of the notations used in the formula-

As we told before, we can set the value of γ (Learning rate) and we can also set the current position of x. The thing we need to think about is how to find ∇F(Xn).

Finding the gradient of a function:

If we want to find the gradient of a function for a point x, we need to differentiate the function for once with respect to x.

The result we’ll get by differentiating the function once is called the first order derivative of that function.

So, let’s differentiate our function f(x) = x² + 5 and see what we get-

If we’ve forgotten calculus, nothing to worry. The sympy package of Python can find the derivative of a function for us.

In the following python code, the sympy package will find the derivative for our function f(x) = x² + 5.

Output:
2*x

You can ask, why do we need to take the first derivate?

Reasons to take the first derivative:

👉 The first derivative tells us the direction of the function, whether the function is increasing or decreasing.

👉 The first derivative also tells us about the slope of the function.

Now, let’s understand why we call the gradient descent algorithm iterative. The formula for gradient descent we discussed above tells us the direction and number of units to roll for the next position. But we can’t reach the minimum point by rolling the ball once. We need to roll the ball for a certain number of times. We need to repeat the process until we achieve the convergence. That’s why we need to use a loop to repeat the process.

Let’s write the formula of the algorithm in a bit more nice way-

Finally, we’ve known all the concepts that we need to write the code for gradient descent.

Let’s code the gradient descent quickly-

👉 We’ll set 0.001 as the value of γ (gamma). If we set the value of learning rate larger, there is a chance to overtake the minimum point. That’s why we’ll take a good value for γ which is 0.001.

👉 Now, we need to set our starting point. That means we need to set an initial value for x, from where we’ll start rolling the ball.
We’ll set the initial point x = 6.

👉 Finally, we need to set the number of iterations for the repeating process. We’ll set it to 5000.

Output:
iterations = 5000 
x =  0.00026968555624761565

Here we see that after 5000 iterations we get a value of 0.00026968555624761565 for x which is very close to 0. Actually, if we convert it to an integer, it’ll turn into 0. So, we’ve got out expected minimum value 0 for x which will cause the function output the minimum value 5.

Now if we look at the plot, we’ll see the ball is rolling down and reaches the minimum point of the plot.

This is the intuition behind the gradient descent algorithm.

In this article, I’ve used a simple function with one parameter. But to feel the real advantage of gradient descent, we need to work with multiple parameterized function. In the next article, I’ll show how can we use gradient descent to minimize the error of Linear Regression. There we’ll work with multiple parameters.

Till then practice what you’ve learned from this article. 😀

** Constructive criticism will be appreciated.

Reading a book is very essential because every topic is described in detail into a book, but in videos/tutorials everything is described in short.

For books I will recommend — 
1: Introduction to Algorithms: Charles E. Leiserson, Clifford Stein, Ronald Rivest, and Thomas H. Cormen
2: Algorithms (4th Edition): Robert Sedgewick, Kevin Wayne
3: The Algorithm Design Manual: Steven Skiena

Some online resources:
Data Science Tutorials
Algorithms — GeeksforGeeks

Resources to practice:
1: http://lightoj.com/volume_problemcategory.php
2: World of Seven — Methods to Solve
3: A2 Online Judge
4: HackerRank
5: CodeForces

Now come to the steps:
I follow “Learning by doing” philosophy.

Step 1: At first you should learn the theory of any particular algorithm from your books/resources.

Step 2: Try to implement the algorithm(theory) you’ve learnt into code without looking at others implementation. After much trying if you can’t implement then take help of others.

Step 3: Now pick up a link from Resources to practice and solve some problems related to the algorithm you’ve learned recently.

To me this my best way to learn algorithms.

Best of luck. :)

This article was also posted in my personal blog.

Now let’s know what IoT actually is — “The Internet of Things (IoT) is a scenario in which objects, animals or people are provided with unique identifiers and the ability to transfer data over a network without requiring human-to-human or human-to-computer interaction. IoT has evolved from the convergence of wireless technologies, micro-electromechanical systems (MEMS) and the Internet.”

There was a time when we were used to use the internet only through the computer. But now we use internet in our mobile, smartphone or in many other smart devices. What if we can provide the connectivity of internet into every objects in our real world? This is the concept from where IoT was originated. It’s all about connecting the physical world to the internet and perform any action as we want.

Although the concept wasn’t named until 1999, the concept of a network of smart devices was discussed as early as 1982, with a modified Coke machine at Carnegie Mellon University becoming the first internet-connected appliance, able to report its inventory and whether newly loaded drinks were cold. Afterwards the term “Internet Of Things”/”IoT”was first proposed by Kevin Ashton in 1999.

Now let’s discuss how the IoT technology works. There are 4 basic steps that makes IoT working. These are shortly described below-

1. Unique Identity of “Things” : Provide an unique identity to every “thing” that needs to be connected. It may be an IP address. However, due to the limited address space of IPv4 (which allows for 4.3 billion unique addresses), objects in the IoT will have to use IPv6 to accommodate the extremely large address space required.

2. Ability to Communicate: Provide these “things” with the ability to share information. It should be the wireless internet, which is keeping the world connected.

3. Senses: Provide these “things” with senses to gather information as required. These are the sensors which are getting smaller and cheaper day by day.

4. End User Interface: An interface that allows us to share the information with these “things”. These may be mobile/smartphone app, TV-Monitor, Laptop etc.

Now let’s think of your chair. Consider your chair as a thing in the IoT. You want to know from anywhere in the world, is this chair occupied and who is sitting on the chair?
So, at first you will provide it an unique id (IPv6). You will use sensors like Pressure sensor which will measure the pressure upon the chair, RFID tag reader which will identify the person who is sitting on the chair. Then you will communicate with the chair with your smartphone and you will be known who is sitting on your chair. So, your chair will become a smart chair! Isn’t it amazing?

Let’s discuss about some sectors where IoT may play some amazing role in near future.

1. Reality Search Engine: Will you find the expected result if you ask Google, “Where is my keys?”, “Where is my shoes” or “Where is my child whom did I lose yesterday in the market?” ? IoT may make it easy for you!

2. e-Health: There will be available smart T-Shirts like “D-Shirt” which will record your heart rate, GPS location, route, speed and altitude. BodyGuardian, A wearable sensor system that can remotely read a patient’s biometrics (ECG, heart rate, respiration rate and activity Level) to keep people out of a hospital monitoring setting.

Here is an infographic of year 2040 in the eyes of IoT:

There are already some fascinating IoT products as Apple Watch, Philips Lighting, Smart TV, Refrigerators, Washing machine etc. There also exist a smart city named Songdo in South Korea, the world’s first smart city.

Security and privacy are major concerns in IoT — and addressing these concerns is a top priority. These are legitimate concerns. New technology often carries the potential for misuse and mischief, and it’s vital to address the problem before it hinders personal privacy and security, innovation or economic growth. Manufacturers, standards organizations and policy-makers are already responding on several levels.

Now, what do you think about the future of IoT?

The technologist assumes that by 2032 each person will be surrounded by 3000–5000 smart things in our everyday life. And the Tech experts also estimate that the IoT will consist of almost 50 billion objects and 25 billion devices by 2020.

So, let’s wait for the smart world of IoT.

This post was originally written into my personal blog.
Link: http://www.abdullahalimran.com/english/smart-world-through-the-eyes-of-the-internet-of-things-iot/