<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Vision and Language Group - Medium]]></title>
        <description><![CDATA[Vision and Language Group, is a student-run deep learning centric group of IIT Roorkee. We meet up regularly to take up discussions on latest advancements in the deep learning field by reviewing various papers accepted in various tier-1 DL/CV/NLP conferences. - Medium]]></description>
        <link>https://medium.com/vlgiitr?source=rss----e4bec4e4cc37---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Vision and Language Group - Medium</title>
            <link>https://medium.com/vlgiitr?source=rss----e4bec4e4cc37---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 00:15:40 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/vlgiitr" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Ascending the Research Trail]]></title>
            <link>https://medium.com/vlgiitr/ascending-the-research-trail-89a8503749ce?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/89a8503749ce</guid>
            <category><![CDATA[research]]></category>
            <category><![CDATA[experience]]></category>
            <category><![CDATA[student-life]]></category>
            <dc:creator><![CDATA[Jitesh Jain]]></dc:creator>
            <pubDate>Wed, 15 Mar 2023 20:32:02 GMT</pubDate>
            <atom:updated>2023-03-08T16:25:15.521Z</atom:updated>
            <content:encoded><![CDATA[<blockquote><em>This is my third blog on Research Experience, check out the previous blogs: </em><a href="https://jitesh-j.medium.com/why-research-if-i-can-develop-c90bd3ce3540"><strong><em>Why Research if I can Develop?!</em></strong></a><strong><em> </em></strong><em>and </em><a href="https://medium.com/vlgiitr/riding-the-noisy-research-track-4035e64e7ea8"><strong><em>Riding the Noisy Research Track</em></strong></a><strong><em>.</em></strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Zh3hgcjmf1SqUyjCr7Z3GQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@pueblovista?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Paul Pastourmatzis</a> on <a href="https://unsplash.com/photos/4i97n6L0XuY?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>Hey there, long time no see! Long hiatus, I know. I have been busy unifying image segmentation, traveling, applying to grad schools, binging web series, reading, and spending time with COCO (mostly my pet dog, the dataset, a little, haha). No worries, I am back (at least for this one :P).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BNxq0S_0edVxBpwBmXafCg.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nW9Qd1cEDCV5dvXljuHrKA.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YLvIPP0n181reVAM_CuEWg.jpeg" /><figcaption>Hola, meet COCO, the dog! 🐶</figcaption></figure><p>In case you missed it, I shared my experience as a rookie undergrad researcher in a previous blog: <a href="https://medium.com/vlgiitr/riding-the-noisy-research-track-4035e64e7ea8">Riding the Noisy Research Track</a>. Since then, I have grown from a rookie researcher into a more mature beginner researcher with a better outlook on the bigger picture in research (thinking beyond publishing a paper) owing to my close collaboration with the <a href="https://www.shi-labs.com/">SHI Labs</a> in the last couple of years. I have had several realizations that I will be sharing through this article. A few of those to get your interest piqued are:</p><ul><li><strong>🤔 I went from &quot;Ph.D., Me? Nooooooo&quot; to &quot;I primarily applied to Ph.D. programs for grad school.&quot; What changed?</strong></li><li><strong>💭 Is publishing/releasing a paper a good <em>&quot;Why?&quot;</em> for research?</strong></li><li><strong>📖 Is open-source in A.I. a boon or a bane?</strong></li><li><strong>🎗 What is the importance of the advisor and collaborators?</strong></li><li><strong>⚓️ How vital is the authenticity of research?</strong></li></ul><p>I faced a lot of confusion and uncertainty while deciding whether to continue with the research. Having chosen research as a career, I hope to provide apt reasoning and factors that could contribute to your decision on your career choice. Right then, it&#39;s blog time!</p><h3>Why did I decide to apply to Ph.D. programs?</h3><p>If you had asked me a year earlier whether I would go for a Ph.D. afterward, I would have replied, &quot;Nooooo.&quot; What changed in a year that I applied mainly to Ph.D. programs for graduate school?</p><p>Working on <a href="https://github.com/SHI-Labs/OneFormer">OneFormer</a> made me realize that research is more than solving problems. It&#39;s about solving <strong>impactful</strong> <strong>problems. </strong>In other words, looking at the bigger picture before starting a project. This realization led me to ask the following questions:</p><h4><strong>Q1 </strong>How to identify impactful problems?</h4><p>The answer to the above question relates to developing the maturity and foresightedness to reasonably, correctly, and independently imagine the likely impact of solving a problem. Gaining experience through practice is the best way to do it. One of the goals of a Ph.D. is to develop the sort of vision required to lead one&#39;s research and create impact. I also emphasize that if someone is new to a field, it is hard to have an impactful work straightway. Having a few mediocre works in an area to collect the ground knowledge and then break the ground with impactful work feels great.</p><h4><strong>Q2 </strong>What one problem should I choose out of all the impactful options?</h4><p>The answer to this question contributed the most to my decision to apply for Ph.D. programs. I have spent much of my undergrad working on image segmentation (2D vision task). However, do I want to continue researching in the same area or switch fields? Honestly, I do not know 🤷‍♂. A Ph.D. provides me with the perfect opportunity to freely (I am not entirely a paid employee, although I still get some financial support through RAships) explore various directions and then fixate on a single direction at the end of my first two years. I like that promise of freedom 🤗.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F14294399&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fchandler-matthew-perry-i-want-my-freedom-freedom-ive-had-it-gif-14294399&amp;image=https%3A%2F%2Fmedia.tenor.com%2FOgJ-hSS5oJQAAAAC%2Fchandler-matthew-perry.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/692b91e18794ce92eeb4cb7bdbe878ad/href">https://medium.com/media/692b91e18794ce92eeb4cb7bdbe878ad/href</a></iframe><h4><strong>Q3 </strong>My work is identified with me.</h4><p>Working on three first-author papers at SHI Labs taught me that I am the only one responsible for my project. My work is identified with my name. I like that recognition. It happens in any scientist&#39;s job where the work is publically released, to be honest. Everything I do during a Ph.D. is mine.</p><h4><strong>Q4 </strong>What if I do not like a Ph.D. degree?</h4><p>Talking to Ph.D. students in my network, I learned that most programs allow Ph.D. students to leave with a Master&#39;s degree after the starting two years of their program. So, I can always do that if something doesn&#39;t work out. It&#39;s better than going for an M.Sc. first and then for a Ph.D. anyway for me.</p><p>The answers to the above questions helped me decide to apply for Ph.D. programs. Now, I am still waiting to hear back about all my applications. Let&#39;s see how it turns out 🤞. I also recommend reading <a href="http://karpathy.github.io/2016/09/07/phd/">Karpathy&#39;s blog on surviving a Ph.D.</a></p><h3>The Purpose (why?) of my research</h3><p>It&#39;s a good practice to ask &quot;<strong><em>Why?</em></strong>&quot; before doing anything. One only gets a convincing answer sometimes. &quot;<em>Why</em> are professors still teaching us outdated content in most courses?&quot; Who knows, it may be laziness on their part to update the content. &quot;<em>Why </em>do girls have to make an entry every time they leave their hostels at IITR?&quot; Guards following senseless orders 🤷‍♂.</p><p>When researching, one must be convinced about the purpose of investing months, if not years, towards a single goal. I started my first research project (in the exploration mode) with the end goal of releasing a paper. I did not care much about its impact and utility at the time. I was happy with a paper to my name, to be honest. However, after gaining more experience, I realized <strong><em>papers are not everything one needs in A.I. research</em></strong>.</p><p>The core principle behind a research project is to push the corresponding field forward. Releasing a paper is lovely. However, research is not only publishing papers, and only publishing papers is not research. I think a single paper with 100 citations and 500 stars on GitHub is better on most occasions than ten papers with 10–20 stars and a few citations. <strong><em>Quality matters much more than quantity </em></strong>in the longer run. As a beginner, it is to work toward completing a paper. Publications are still important (<a href="https://medium.com/vlgiitr/riding-the-noisy-research-track-4035e64e7ea8#:~:text=accepted%20to%20a-,reputed,-conference%2C%20it%E2%80%99s%20an">reason</a>).</p><p>At the end of the day, the researcher in me wants people to acknowledge my research efforts and contributions. I have experienced that a single impactful work brings more acknowledgment (and a sense of fulfillment) than two or three papers with limited impact. So, <strong><em>why</em></strong> research? To <strong>create impact and drive the field forward. </strong>Also, check out some <a href="https://github.com/jbhuang0604/awesome-tips">awesome tips on research by Dr. Jia Bin Huang</a>.</p><p>Note that as a beginner, it&#39;s a good idea to work on completing a research paper. In the longer run, focus on the impact, though.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F23338350&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Froman-reigns-acknowledge-me-universal-champion-paul-heyman-tribal-chief-gif-23338350&amp;image=https%3A%2F%2Fmedia.tenor.com%2F5JZbvAoifUEAAAAC%2Froman-reigns-acknowledge-me.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/73ff05c145f9a5a3a1fa9e4fe38d8b7a/href">https://medium.com/media/73ff05c145f9a5a3a1fa9e4fe38d8b7a/href</a></iframe><h3>The boon of Open-Source in A.I.</h3><p>With the spread of the open-source culture in the A.I. community, measuring the quality of work has become more accessible. If a stranger on Twitter shares your work, in most cases, it is a fine piece of research. Recently, I worked on integrating <a href="https://huggingface.co/docs/transformers/main/en/model_doc/oneformer">OneFormer</a> into the 🤗 <a href="https://huggingface.co/docs/transformers/index">Hugging Face transformers</a> library. I was highly impressed by their <a href="https://huggingface.co/about">vision to democratize</a> the field of A.I. With their various <a href="https://github.com/huggingface">libraries</a> (transformers, diffusers, accelerate, etc.), it is getting easier for anyone to use ML models.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2FRo2ONWyochZCZwX3E8%2Ftwitter%2Fiframe&amp;display_name=Giphy&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2FRo2ONWyochZCZwX3E8%2Fgiphy.gif&amp;image=https%3A%2F%2Fi.giphy.com%2Fmedia%2FRo2ONWyochZCZwX3E8%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="310" frameborder="0" scrolling="no"><a href="https://medium.com/media/d9a23bb153d3af72d2c8f72fc0342c65/href">https://medium.com/media/d9a23bb153d3af72d2c8f72fc0342c65/href</a></iframe><p>Apart from publishing a paper on arXiv, it is an excellent idea to open-source the codebase on GitHub, release a demo (if applicable) for your model and integrate it into any of Hugging Face&#39;s libraries. I practiced this practice with OneFormer recently, and it is effective in obtaining some extra attention from the community and makes it easier to use. An open-sourced GitHub repo is now a necessity in the age of open-source. Also, pay attention to the organization of the README.md file. It&#39;s important. A good open-sourced project is also more straightforward for others to use, understand and improve upon, pushing the field forward. Unless for commercial reasons, open-source is the way to do research. Although, one also needs to release any warnings for caution attached to the public model (biases, failures, etc.).</p><h3>The Importance of Advisors and Collaborators</h3><p>A good research advisor is arguably the most critical contributing factor to the outlook development of a junior researcher toward research. The advisor&#39;s values set a lab&#39;s culture.<em> Is publishing papers (anywhere) the end goal or producing quality, impactful works? Is paper rejection the worst thing that can happen? Is independent research encouraged? What are the perks of a good presentation of ideas? Are the other lab members collaborative or just thirsty for credit and papers? Do your lab mates respect you as a researcher? </em>These are a few questions one can ask about their research environment.</p><h4>The Dependable Advisor</h4><p>Fortunately, at <a href="https://www.shi-labs.com/">SHI Labs</a>, <a href="https://www.humphreyshi.com/">Prof. Humphrey Shi</a> practices fair values for research where the end goal is to create an impact with our research and not just publish papers at any conference. In other words, the quality of our work should be such that it has a chance at the top conferences (CVPR, ICCV, NeurIPS, etc.). That&#39;s an excellent way to leverage deadlines to produce high-quality work. One of his <a href="https://twitter.com/praeclarumjj/status/1618124486263595009?s=20">tweets</a> expresses that idea perfectly.</p><blockquote>🥇 Impact is Primary, 🥈 Publication is Secondary</blockquote><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2FIfin9TdhN9gtI2w4i8%2Fvideo&amp;display_name=GIPHY&amp;url=https%3A%2F%2Fgiphy.com%2Fclips%2Fthelword-the-l-word-generation-q-Ifin9TdhN9gtI2w4i8&amp;image=https%3A%2F%2Fmedia2.giphy.com%2Fmedia%2FIfin9TdhN9gtI2w4i8%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="480" height="206" frameborder="0" scrolling="no"><a href="https://medium.com/media/1c5a2f787e97cdde1e4b7e125387871f/href">https://medium.com/media/1c5a2f787e97cdde1e4b7e125387871f/href</a></iframe><h4>The Awesome Autonomy</h4><p>Another thing that I value the most when doing research is autonomy. I like to think about what to do first and then take feedback from other people on my ideas instead of just following orders. The ability to think and implement solutions on one&#39;s own helps develop independence which is critical when researching. The vision of the research lab is also an important contributing factor to guiding your research path. You can do all the work yourself, but without a vision, the impact will only be limited.</p><p>Research continues beyond the thinking and implementing stage. Presenting the observations clearly and comprehensively is necessary to create an impact. I haven&#39;t always been the best at delivering my knowledge and ideas in writing. I like others to suggest improvements in my big-stake papers or presentations. I always have one of my friends read my blogs before I publish these. Fortunately, I obtained excellent presentation suggestions while working on all my research projects.</p><h4>The Charming Collaborators</h4><p>Research in A.I. witnesses developments at lightning speed. It&#39;s easy to fall behind by unfollowing the research news, even for a week. Still, one can only be an expert and up-to-date in some fields. Other expert members and collaborators in a research lab play a considerable role when one needs knowledge and guidance about a new area. The advisor can always direct you to the correct person for every field of research. Collaborations are at the core of successful research. It is also necessary for a researcher to respect other researchers. Everyone demands respect, and it is only humane to provide that respect. When arguments and disagreements happen, it&#39;s best to act respectfully and humbly. No one likes a haughty, arrogant researcher.</p><h3>The High Stakes in A.I.</h3><p>Research in A.I. is subject to constant scrutiny by the open-source community. Your research work must be solid, reproducible, fair, and well-grounded at the time of its release. Failing to achieve any single one of these traits could put you in a nervous position. With its fierce competition, any dubious trait in your research could jeopardize your image among the A.I. community.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F26102852&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fricciardo-norris-daniel-ricciardo-lando-norris-daniel-ricciardo-space-hopper-gif-26102852&amp;image=https%3A%2F%2Fmedia.tenor.com%2F6fntiC_iUnEAAAAM%2Fricciardo-norris.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/767b58ff1c0cec052c0a171da78bdcd1/href">https://medium.com/media/767b58ff1c0cec052c0a171da78bdcd1/href</a></iframe><p>Do not copy/use anything (even an English sentence) from any source without proper citations. Don’t be frugal with the citations; cite profusely (it’s free). Always ensure your results are reproducible (run experiments more than once). Use fair settings when comparing to baseline methods. A few things come to my mind.</p><p>Some people will always question your research. Hold your research to the highest standards, and you will always have effective responses for them.</p><h3>Conclusion</h3><p>Alright, so that’s the end of another research experience blog. As I approach the end of my undergraduate degree at IITR, I have tried to capture my growth as an undergrad researcher in a series of blogs (including this one). Although I still have much to learn, I hope my blogs will help and motivate future undergrads to explore research during their undergraduate degrees.</p><p>And my future as a researcher is still being determined. Where (if at all) will I be going for my Ph.D.? Will I be going for academic research or industrial research? There’s still a lot for me to explore, and I will try to capture my research journey and life experiences here in the future. Till then, Adíos!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/639/1*yUJHq0lGYbbaE7i7mt1idA.jpeg" /><figcaption>Don’t worry. You’re learning through my blogs 😉</figcaption></figure><p>You can learn more about me on my<em> </em><a href="https://praeclarumjj3.github.io/"><em>webpage</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=89a8503749ce" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/ascending-the-research-trail-89a8503749ce">Ascending the Research Trail</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Password Cracking]]></title>
            <link>https://medium.com/vlgiitr/password-cracking-1b14e0844404?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/1b14e0844404</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[generative-adversarial]]></category>
            <category><![CDATA[hacking]]></category>
            <category><![CDATA[ml-research-paper-summary]]></category>
            <category><![CDATA[password-cracking]]></category>
            <dc:creator><![CDATA[Rohan Garg]]></dc:creator>
            <pubDate>Tue, 31 May 2022 19:57:50 GMT</pubDate>
            <atom:updated>2022-05-31T19:57:50.029Z</atom:updated>
            <content:encoded><![CDATA[<p>On hearing the term &quot;password-cracking,&quot; many will think this post will be about how to guess someone&#39;s password or somewhat similar, but the reality is not always so satisfying.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/863/0*VzcjBp_R1DAGmPnj.jpg" /></figure><h3><strong>What is Password Cracking</strong></h3><p>In general, whenever anybody types a password on any device or software, passwords don&#39;t get stored in the raw format in the database. Instead, raw passwords are first passed through the hashing algorithm, which converts the raw passwords into some particular sequence of letters, numbers, and special characters which looks entirely random for an ordinary being.</p><p>Now there are several password database leaks and breaches all over the world. One such dataset is Rockyou Dataset, which contains <strong>about 31 million passwords; </strong>this is a widely used dataset because this dataset contains passwords in plain text format without any hashing. Most password cracking algorithms are either trained using this dataset or have used this for dictionary attacks.</p><p>These algorithms decrypt the hashes of the passwords obtained from other password databases leaks. These algorithms generate passwords, hashes them using the encryption algorithm, and then compare the hash with the hashes present in the database; if the hash matches, Bingo! We got the password corresponding to that hash; otherwise, keep generating and comparing passwords. Password hashes generated by the encryption algorithm are such that they can&#39;t be reverted. Passwords, once hashed, can not be converted back into passwords by any algorithm other than brute force attacks over the hash of every possible password.</p><h3>Hashcat</h3><p>Hashcat is one of the most popular and widely used password crackers. It uses various kinds of attacks for cracking the passwords like:</p><ul><li><em>Dictionary attack</em>: Trying all the passwords present in a list or database.</li><li><em>Combinator attack</em>: Trying concatenating words from multiple wordlists.</li><li><em>Mask attack</em>: Trying all the characters given in charsets, per position.</li><li><em>Hybrid attack</em>: Trying combining wordlist and masks.</li><li><em>Association attack</em>: Use a piece of information that could have had an influence on password generation to attack a specific hash.</li></ul><p>In addition to these, Hashcat enables high-parallelized password cracking and the ability to support a distributed hash cracking system via overlays.</p><h3>Probabilistic Context-Free Grammar</h3><p>Context-free grammars have been in the study of natural languages, where they are used to generate strings with a particular structure. Probabilistic context-free grammar is a probabilistic approach to traditional context-free grammar; it incorporates available information about the probability distribution of user passwords. This information is used to generate password patterns in order of decreasing probability. At the same time, these structures can be either password guesses or word-mangling templates that can be filled by dictionary words. Here&#39;s a brief overview of how probabilistic context-free grammar is used in password cracking:</p><p><strong><em>Preprocessing: </em></strong>In this phase, frequencies of specific patterns are measured associated with the password string. In this, the author denotes the alpha string (sequence of alphabet symbols) by <strong>L</strong>, digit string as <strong>D</strong>, and special strings(sequence of non-alpha and non-digit symbols) as <strong>S. </strong>For password &quot;$password123&quot;, structure of the password would be <strong>SLD</strong>, base structure would also be similar to structure except that it would also incorporate the length of strings, so base structure would be <strong>S¹L⁸D³</strong>. The preterminal structure fills in the value of<strong> S</strong> and <strong>D</strong> in the base structure, whereas the terminal structure (guess) would fill the value of <strong>L</strong> in the preterminal structure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/833/1*nx944Acb7VB9jHv_LhHMew.png" /></figure><p><strong><em>Using Probabilistic Grammars: </em></strong>A mathematical form of defining context-free grammar as <strong>G = (V, Σ, S, P), </strong>where:<strong> V</strong> is a finite set of variables (or non-terminals),<strong> Σ </strong>is a finite set of terminals, <strong>S</strong> is the start variable, and <strong>P</strong> is a finite set of productions of the form <strong>α → β </strong>where <strong>α </strong>is a single variable and <strong>β</strong> is a string consisting of variables or terminals. Probabilistic context-free grammars have probabilities associated with each production such that for a specific left-hand-side variable, all the associated productions add up to 1. A string derived from the start symbol is called a sentential form. The probability of sentential form is simply the product of the possibilities of the productions used in its derivation. As the production rules don&#39;t have any data to rewrite alpha variables to alpha strings, thus sentential forms can be maximally derived up to the terminal digits and special characters with alpha <em>variables. </em>These sentential forms are the pre-terminal structures. The main idea is that preterminal structures define mangling rules that can be directly used in a distributed password cracking trial on passing them to the distributed system to fill in the alpha variables with dictionary words and hash the guesses.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/895/1*Dq1EWM1KRI1wPogS8Iwx9Q.png" /><figcaption>Assigning pre-terminal structure with probability</figcaption></figure><p>In order to generate pre-terminal structures in decreasing order of probability, authors used the approach to output all the probable pre-terminal structures, evaluate them on probability, and then sort the results. However, this pre-computation step is not parallelizable with the password cracking step that follows. Now to generate terminal structures from the pre-terminal structure, one approach is to simply fill in all relevant dictionary words for the highest pre-terminal structure and then choose the next highest probable pre-terminal structure. This approach does not further assign probabilities to the dictionary words and does not learn the specific replacement of alpha variables from the training set. This approach is called <em>pre-terminal probability order. </em>Another approach is to assign probabilities to alpha strings in various ways. For instance, it is possible to assign probabilities to words in a dictionary based on how many words of that length appear, observed use of the word, frequency of appearance in language, or knowledge about the target. This approach is called <em>terminal probability order. </em>This approach does assign each terminal structure (password guesses) a well-defined probability.</p><p>For comparing the performance of probabilistic context-free grammars, the authors used a standard open-source password cracking program, John the Ripper. The authors used a total of six publicly available input dictionaries to use in our tests. Four of them, &quot;English_lower&quot;, &quot;Finnish_lower&quot;, &quot;Swedish_lower&quot; and &quot;Common_Passwords&quot; were obtained from John the Ripper&#39;s public website. Additionally &quot;dic-0294&quot; input dictionary was obtained from a password-cracking site, and &quot;English-wiki&quot; input dictionary is based on the English words gathered from <a href="http://www.wiktionary.org/">www.wiktionary.org</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/776/1*iuNdfPckFxT8n4px3zSU5g.png" /><figcaption>Number of passwords cracked against Myspace list</figcaption></figure><p>Passwords Cracked by the <em>Terminal probability order </em>approach of Probabilistic context-free grammar are the highest. It gave an improvement over John the Ripper from 28% to 129% more passwords cracked given the same number of guesses. Additionally, when we used the <em>preterminal order</em>, we also achieved better results than John the Ripper in all cases but one, though less than what we achieved using <em>terminal probability order</em>.</p><h3>PassGAN</h3><p>PassGAN is an example of generative adversarial networks (GANs). GANs are essentially an adversarial framework of multilayer perceptions made up of a generator and discriminator. The generator tries to generate data samples similar to the training data and fool the discriminator. In contrast, the discriminator tries to maximize the probability of assigning the correct label to both the training examples and samples generated by the generator. They both end up playing the minimax game and optimizing the value function V (G, D) for the password distributions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/832/1*6EeJsAbzlObVjsgo2CAHiw.png" /></figure><p>Generative modeling relies on closed-form expressions that generally aren&#39;t capable of noisy real data. PassGAN trains a generative deep neural network that takes as input a multi-dimensional random sample of passwords formed in a Gaussian distribution to generate a sample of the desired target distribution.</p><p>The generator of PassGAN takes input to the reshape node followed by five residual blocks, whereas each block consists of 1D convolutional blocks connected by relu functions, and the final output is the weighted sum of outputs from the conv1D block and the residual identity connection of input. Residual blocks are then followed by a 1D convolutional node which outputs to the softmax node to generate probability distribution in the character set.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/704/1*QOW4BimncBtOlsX8vksO0Q.png" /></figure><p>The discriminator of PassGAN has a very similar architecture to the generator, except that it is in the opposite order as compared to generator. Input after a transpose operation is fed to a 1D convolutional block which is followed by five residual blocks whose architecture is similar to residual blocks used in the case of generator. Output from the final residual block after having a reshape operation is given a linear transformation function which leads to the final output.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*m6vPT4ek3LpOq13aCfdTMg.png" /></figure><p>For the training purpose, 2.5 million passwords were sampled uniformly from the RockYou dataset, length of the passwords was restricted to 10 in order to make training computationally feasible. For testing purposes, additional 2.5 million passwords were sampled exclusive to the training set passwords. To evaluate the trained model, 5 million passwords are generated from the generator network and compared to the test data, about 5.5% (274965) generated passwords were found in the data set, whereas 63110 among them were unique. For calculating the strength of passwords cracked by PassGAN, researchers used <strong>zxcbvn. </strong>zxcbvn is a low-budget password strength estimator. Its algorithm returns an integer strength bar from 0 - 4, estimating a higher strength with a higher score. Passwords, those PassGAN was able to crack scored 1.59 and landed an average guess per password to be 5.32 x 10⁶.</p><h3>GENPass</h3><p>As we have seen, PCFG(Probabilistic context-free grammar), is based on statistical probability. These approaches require a large amount of calculation, which is time-consuming. In PassGAN, neural networks are able to predict more accurate passwords, however, they are not qualified for cross-site attacks as each dataset has its own features.</p><p>GENPass tries to generalize on those leaked passwords and improve the performance in cross-site attacks. GENPass is a multi-source deep learning model that learns from several datasets and ensures the output wordlist can maintain high accuracy for different datasets using adversarial generation. Now before we proceed further, first define what is &quot;general&quot;.</p><blockquote>Definition (what is “general”) : Assume a training set T containing m leaked password datasets D1, D2, D3,…,Dm. Model Gt is obtained by training T. Model Gi is obtained by training Di (i ∈ [1, m]). If Model Gt can guess dataset Dk (Dk∉ D1, D2, D3,…,Dm) better than Gi (i ∈ [1, m]), model Gt is believed to be general.</blockquote><p>For generating passwords, PCFG + LSTM models, also called PL models, comes into the picture. The preprocessing step is performed by PCFG. Passwords are first encoded into a sequence of units. Each unit has a char and a number. A char stands for a sequence of letters (L), digits (D), special chars (S), or an end character (&#39;\n&#39;), and the number stands for the length of the sequence. A table is generated when we preprocess the passwords. LSTM is a widely used RNN variant, which generates the probability of the next element based on the context elements. Each LSTM model unit maintains a state Ct at time t, and three sigmoid gates control the data flow in the unit, namely the input gate, the forget gate, and the output gate. The output is calculated as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/562/1*Y9UV9DirwuIFW6pxlZA7aA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/917/1*RVgJ53cwbb02CRt1s3_O2w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/666/1*VgAK-S3yyTE1ME43HgIRrg.png" /></figure><p>LSTM is used to generate passwords. By feeding the LSTM model the preprocessed wordlist and training it, the model can predict the next unit. When a unit is determined, it is transformed back into an alphabetic sequence according to the table generated during the preprocessing step. The LSTM model will output a list of units with their corresponding probabilities, if units are chosen according to the highest weight, then a large number of duplicates will be created in the output wordlist, so the unit is chosen by sampling from discrete distribution. This ensures that higher-weight candidates are chosen with higher probability, while lower ones can still be chosen after a number of guesses. This procedure is called <em>weight choosing.</em></p><p>PL model is suitable for only one dataset, not for several datasets simultaneously. Different datasets have different underlying principles and lengths, whereas simply mixing datasets would make it difficult for the model to learn the general principles. To solve this multi-source training problem, GENPass comes into the picture.</p><p><em>Prediction of Model n: </em>For all the different datasets, we train a different PL model, thus, the model can output the result with its own principle.</p><p><em>Weight Choosing:</em> It is assumed that all the PL model have the same probability, so the output from each model are combined, the combined list will be the input of the weight choosing process, and the final output will be chosen by sampling from discrete distribution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*2i0W0s9qeUVGHimLyEBiMA.png" /></figure><p><em>Classifier and Discriminator:</em> The classifier is a CNN classifier trained by raw passwords without preprocessing from different datasets. Given a password, the classifier can tell which dataset the password most likely comes from. Through a softmax layer, the output will be a list of numbers with a sum of one. Discriminator takes the classifier&#39;s output and accepts those passwords that have a consistent probability of appearance in different datasets so that the output passwords can be &quot;general&quot;.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OuuNPVcwZWQrZ-EURqni4g.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/478/1*7I6_y4Aq7pTBZA9ZKX3Jzg.png" /></figure><p>If C is too large, the generated unit will be discarded; otherwise, it will be accepted. In the model threshold value of C is set to 0.2.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*BLhKxJ_OSShzM0zxn_lRww.png" /></figure><p>Evaluation: To evaluate the PL model, it is trained with Myspace and phpBB password datasets. After each training session, the model generated a new wordlist. GENPass is also trained on the same Myspace, and phpBB password datasets and wordlist are generated. The authors trained the PL model with a single mixture of two wordlists and compared the result with the GENPass model.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/673/1*asZVhG7r2Pq-8ibaNliKNg.png" /></figure><p>Here it is clear that the GENPass model outperforms all other models. Using raw LSTM without any preprocessing performs the worst. Using PL to learn Myspace alone performs second best, which proves Myspace is a good dataset. Simply mixing two datasets does not improve the matching rate.</p><h3>References</h3><p><a href="https://hashcat.net/wiki/">Hashcat official page</a></p><p><a href="http://courses.csail.mit.edu/6.857/2019/project/9-Nepal-Kontomah-Oguntola-Wang.pdf">Adversarial Password Cracking</a></p><p><a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8832180">GENPass: A Multi-Source Deep Learning Model for Password Guessing</a></p><p><a href="https://www.researchgate.net/publication/220713709_Password_Cracking_Using_Probabilistic_Context-Free_Grammars">Password Cracking Using Probabilistic Context-Free Grammars</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1b14e0844404" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/password-cracking-1b14e0844404">Password Cracking</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Riding the Noisy Research Track]]></title>
            <link>https://medium.com/vlgiitr/riding-the-noisy-research-track-4035e64e7ea8?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/4035e64e7ea8</guid>
            <category><![CDATA[experience]]></category>
            <category><![CDATA[research]]></category>
            <category><![CDATA[student-life]]></category>
            <dc:creator><![CDATA[Jitesh Jain]]></dc:creator>
            <pubDate>Thu, 29 Jul 2021 16:18:44 GMT</pubDate>
            <atom:updated>2021-07-29T16:18:43.979Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fP1elv-raL3PZUDbWHmYSQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@gerandeklerk?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Geran de Klerk</a> on <a href="https://unsplash.com/s/photos/forest?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>Alright, people! This article will share my experience and learnings during the last eight months as an undergrad researcher. For those reading one of my blogs for the first time, I am a CSE undergrad (about to enter 3rd year) and am working as a <em>Research Intern</em> at <a href="https://www.humphreyshi.com/people"><em>SHI Lab @ UO</em></a> and <a href="https://picsart.com/"><em>Picsart</em></a>.</p><p>Now, before we dive in, let me clear it out that I have probably had a more intense research experience for better or worse than some of the other undergrad people at IITR. So, don’t make any judgments about research based on the content in this post 😛. So, we got that sorted out. Let’s begin!</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F5347205&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fnacho-life-good-lifes-funny-gif-5347205&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2Fb7dc0d6c32f396f47d2538dd7fa7f39b%2Fraw&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/f5921ea73521c3eac5071cf3734c7a00/href">https://medium.com/media/f5921ea73521c3eac5071cf3734c7a00/href</a></iframe><blockquote>Disclaimer: If it wasn’t clear by now, this isn’t a post where I will tell you how to get a research intern. You will find a lot of those with a single google search.</blockquote><h3>The Promising Start</h3><p>Now, when you are just starting with research and working with a pro researcher, you can’t wait to take up a research project and get into the mix. That was the case with me, no exceptions, each cell in my body was excited to start <em>“my own”</em> research project(s).</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F4767352&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fdespicable-me-minions-lets-get-started-happy-excited-gif-4767352&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fr3XdvPsAV3kAAAAN%2Fdespicable-me-minions.png&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/f152eb61b96552df2d9bb54017cba731/href">https://medium.com/media/f152eb61b96552df2d9bb54017cba731/href</a></iframe><p>It all begins with a literature survey, reading tons of papers, getting to know the dreaded so-perfect <em>SOTA (state-of-the-art), </em>coming up with the so-called <em>unique innovations,</em> and then finding another paper with the innovations already implemented. That’s right. It isn’t as easy to find a new problem to work on amidst the immense ocean of existing works. It took me almost one month at the start of both my interns to find a project to work on!</p><p>So, don’t get all stressed and messed up if you don’t have anything to work on at the start; paper reading is the most underrated skill without which you can’t excel in research. Feed your mind with ideas from the others and create a new one with a mix-match 😉. That’s what research is: <strong><em>building on existing works and improvising</em></strong>! That brings me to the next section about building.</p><h3>Let’s Build the Concept.</h3><blockquote>Great! You have a concept to work on, but can you build it?</blockquote><p>Here, now you will have two ways to proceed:</p><ol><li><strong>First:</strong><em> Take up an open-source implementation (I am so grateful that these exist 🙈) and build on it</em></li><li><strong>Second: </strong><em>Start the implementation from scratch all by yourself</em>.</li></ol><p>Here, <strong>DON’T</strong> let the craze of learning sway you towards the <em>second</em> option. You learn much more building upon an existing implementation: the code architecture, good practices, and most importantly, how to put modules from different places together in a <strong>bug-free</strong> (more on this later) manner. On the other hand, doing all the implementation yourself will be a waste of time, effort, and, well, inherent smartness 😛. (To be clear, I <strong><em>didn’t </em></strong>make this mistake, but the thought did cross my mind once ¯\_(ツ)_/¯)</p><p>Why is this important? Well, as the research community expands, more and more people are open-sourcing their code, and most of the time, you will use existing works as your baseline, and it is essential to <strong><em>get used to their setting and working</em></strong>, which brings me to the next section.</p><h3><strong>This paper looks good.</strong></h3><p>I often used to ask myself: <strong><em>What’s the significance of the many research conferences held around the globe? </em></strong>The papers are probably months old, outdated, and already read by the targeted audience by the time the conference is organized. Sure, you get to talk to the authors, participate in challenges &amp; workshops, and what else?</p><p>It turns out conferences are like a <strong><em>quality-assurance mark</em></strong> (well, most of the time). If a work has been accepted to a reputed conference, it’s an excellent decision to take that as your baseline. If not, then well, you better do an autopsy on the claimed results.</p><p>As a fun fact, there was a work about 3–4 months back unpublished, just <em>floating out on the arxiv. </em>I took that as a baseline like any good kid would do. So, the work was fluked, the implementation and most probably the idea as well. And even more interesting, the primary author knew about the issues. That’s when I invented the rule:</p><blockquote>Never trust a paper blindly, ever!</blockquote><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F5707976&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fneil-patrick-harris-himym-how-imet-your-mother-barney-stinson-barney-gif-5707976&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2Fab90828f5ed255fbf5f9e898ab99e3b8%2Fraw&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/4c2a0249fe4e94c3d13560b3da1e1683/href">https://medium.com/media/4c2a0249fe4e94c3d13560b3da1e1683/href</a></iframe><h3>Understand the DATA!</h3><blockquote>DL models are data-hungry!</blockquote><p>It’s a common saying in the DL community, and for a good reason. Before diving into the network structure code, starting the experiments, and all that goes on during the sprint, it’s nice to prioritize understanding the dataset and checking its correctness. You might think most papers used this dataset, so let’s load the contents and start! That’s right, and at this point, we need to verify if the pre-processing steps work as expected and we didn’t tweak the input in the wrong way unknowingly.</p><p>It happened with me once, where I took the data processing script from one of the works and used it straight away only to find a week later that the inputs were wrong and not synced to my task 😕. So, <em>respect the data inputs. Without a correct input, you get senseless outputs!</em></p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F12341428&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fobama-what-seriously-wtf-gif-12341428&amp;image=https%3A%2F%2Fc.tenor.com%2FnLWeHUhYIXIAAAAd%2Fobama-what.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/8399d616ca27cbfd9d1daf26633c6907/href">https://medium.com/media/8399d616ca27cbfd9d1daf26633c6907/href</a></iframe><h3>DO it YOUR Way!</h3><p>As an undergrad researcher, you generally have an advisor who is either a grad student or the prof himself might be the advisor. Either way, don’t expect your advisor to help you in the implementation process. During the meetings, often, they may advise you to change the pipeline in a certain way. Here, understand the logic and implement it in your way. Don’t just follow orders from the advisor. They have probably never looked at the codebase and so have no idea about its state. You created the codebase, so make changes to the code in your way.</p><p>Don’t worry if you make big fat bug blunders. That’s how you learn the art of debugging, and with time, the efficiency increases. So,</p><blockquote>Take the what, why, a little how from the advisor and answer the complete how yourself!</blockquote><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F13536614&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fcook-breaking-bad-hoodie-gif-13536614&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2Faae02fe4de382ed63b23978847b80203%2Ftenor.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/6d9626708ce6bad92ba8268bc4738c15/href">https://medium.com/media/6d9626708ce6bad92ba8268bc4738c15/href</a></iframe><h3>The Crisis.</h3><p>Cool, so you have a concept, a credible baseline, and starting implementation. You are ready to start the experiments and then publish your work with a bang. Life is awesome!</p><p>Prank Alert, you just got research bombed 🙅. If your first set of experiments work well, then you are the luckiest person on the planet! Generally, <strong>The Crisis </strong>encompasses a few phases:</p><h4>Oh, this doesn’t work; let’s try that idea instead!</h4><p>One thing didn’t work. You tried changing a few hyperparameters, a few modules, the code is a total mess, and then you throw the current idea out and try a completely new one. That makes sense, but remember that when you are trying different things, be patient, don’t change more than one setting in any of your experiments. Track the effects of the changes and then make a decision.</p><p>PS: I have switched ideas a few times, so it isn’t a big deal, I suppose 🙈.</p><h4><strong>The Never-Ending Trials.</strong></h4><p>Your new idea doesn’t work either. You are already into 3–4 months of experiments. Here is where most people realize that research isn’t the right choice for them, so they opt out, I suppose.</p><p>At this time, one starts to develop something called the <em>Imposter Syndrome (btw, check </em><a href="https://daleonai.com/my-take-imposter-syndrome-tech"><em>this blog</em></a><em> by </em><a href="https://daleonai.com/about"><em>Dale Markowitz</em></a><em> about Imposter Syndrome in Software Engineering) </em>if they didn’t earlier already. So here’s what I did to fight that:</p><ul><li>Talking to a few senior researchers about their experience helped a lot.</li><li>Focusing on the learning and not on producing a paper. At least saying that to myself helped me keep the stress and anxiety to a low level. 😛</li><li>Experience is the primary thing I am here for. The undergrad years are bonus years for research.</li></ul><p>Btw, I am still in this phase, so yeah, way to go!</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F13636146&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fsame-boat-in-the-same-boat-together-in-it-together-gif-13636146&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2F42578f742f04c5383a4b222c1e6933b6%2Ftenor.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/e0633c697cddf68bac816bc469ae6d34/href">https://medium.com/media/e0633c697cddf68bac816bc469ae6d34/href</a></iframe><p><strong>The Sorted Phase.</strong></p><p>This is the phase where the experiments finally work, the paper rolls out, and it is time to move onto newer projects. I hope to experience it someday 🤞.</p><h3>I’m Bored :(</h3><p>Because I am a relatively young researcher and also a little impatient (at least that’s what I feel), I often have those moments when I want to scrap the ongoing project and take up something I find more interesting at that moment. There is no fixed step for this phase, and you might be better off sticking to the current project or starting a new one. It all depends on the project and scope, to be honest.</p><h3>Research Finally Pays off :)</h3><p>I found many seniors telling me back in my first year that undergrad research generally doesn’t earn as much money as the other development-centric activities in India. This is true to an extent, but eventually, you will get a research intern where a development intern package won’t bug you anymore 😛. If you are wondering about me, SHI Lab is an unpaid one, and Picsart pays me.</p><h3>Deep Learning Research is a lot of Engineering.</h3><p>I knew that implementing things in deep learning research isn’t an easy job. If you are one of those people who think that all that happens in research is thinking, and implementation is the simple part, then you are in for a bumpy ride!</p><p>Indeed, implementations in software development fields and DL research aren’t too different. In the end, all you have to do in both cases is develop/create the most optimal, efficient algorithm and write a script for executing that. We spend most of the time debugging the code, creating diagrams for the pipeline, and running toy experiments crucial to the research process. It’s a good habit to write the code and debug it in your mind as you go along, creating imagining the expected functionalities of the modules. If you are lucky and alert, you may find a big fluke in the pipeline while writing the code itself \O/.</p><p>So, it’s not a bad idea to put your developer/engineer hat on at that time. 😛</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F17585875&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fkittisaurus-momo-who-am-i-cat-stare-gif-17585875&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2F57f76630afa6a0bd8e1919f1ea45b5a9%2Ftenor.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/edb2a03370190a125993b1461b926364/href">https://medium.com/media/edb2a03370190a125993b1461b926364/href</a></iframe><h3>TLDR?</h3><p>Alright, that turned out long. Let me provide you with a TLDR here:</p><ul><li><em>Carry out literature surveys </em>before starting a project.</li><li>Choose the baseline carefully and go with an existing implementation if available.</li><li>Spend some time understanding the dataset.</li><li>Don’t fully listen to advisors about how to implement a pipeline 😛</li><li>Fight the crisis phase gallantly :)</li><li>Your engineering and research shall pay off!</li></ul><h3>Conclusion</h3><p>Right, so that’s it, guys! I tried to share a few learnings from my short research experience so far. In my opinion, what makes research different from other fields is the <strong><em>enormous need for perseverance </em></strong>while working. We have no idea if the problem even has a solution or not. We are wanderers, traversing the planes of experiments to find a positive answer, losing our way in the middle, getting back on track again, which makes it exciting tbh!</p><p>If you have any questions, opinions (appreciation included :P), or want to discuss your experience (non-research included), contact me!</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F4840096&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fself-five-barney-himym-gif-4840096&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2F31031ba78338c142795e6486b5049217%2Fraw&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/7f1d211ad1db2490a9e3619fced31011/href">https://medium.com/media/7f1d211ad1db2490a9e3619fced31011/href</a></iframe><p>You can learn more about me on my<em> </em><a href="https://praeclarumjj3.github.io/"><em>webpage</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4035e64e7ea8" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/riding-the-noisy-research-track-4035e64e7ea8">Riding the Noisy Research Track</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Optimizer: diving deep into Neural Networks]]></title>
            <link>https://medium.com/vlgiitr/optimizer-diving-into-deep-neural-networks-94a6ee28f7c5?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/94a6ee28f7c5</guid>
            <category><![CDATA[gradient-descent]]></category>
            <category><![CDATA[optimization-algorithms]]></category>
            <category><![CDATA[neural-networks]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[newtons-method]]></category>
            <dc:creator><![CDATA[Rohan Garg]]></dc:creator>
            <pubDate>Fri, 02 Jul 2021 08:44:28 GMT</pubDate>
            <atom:updated>2021-07-03T03:54:56.963Z</atom:updated>
            <content:encoded><![CDATA[<p>Waiting for the neural network to train is always the most annoying time and even more annoying when the datasets are large.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*ZsH4Tx2ZBFqUdM4oiQ2Hrg.jpeg" /></figure><p>Indeed, but changing the optimization algorithm may bring a significant change in speed as well as accuracy for the deep learning model training.</p><h3>Types of Optimization Algorithms</h3><p>Several optimizations algorithms exist. Mainly there are two types of optimization algorithms</p><ol><li>First-order optimization algorithms →It uses First-order derivatives for optimization.</li><li>Second-order optimization algorithm →It uses second-order derivatives for optimization.</li></ol><p>Here we are going to discuss some of the First-order optimization algorithms with a glimpse of the second-order optimization algorithm.</p><p>First things first, Let’s break it down into pieces for better understanding.</p><h3><strong>Optimization</strong></h3><p>Mathematically, the process of minimizing or maximizing any expression is called optimization. In machine learning algorithms, we have a loss function, which has to be minimized to predict results with significant model performance.</p><p>The objective of optimizers is to reach the point of minima of the loss function, If the loss function can be visualized in 3 dimensions, then some of its possible shapes :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fS1KCDB6iDDSbEkjp5bGIA.jpeg" /><figcaption>Convex and Non-Convex loss functions</figcaption></figure><p>In the Convex loss function (left fig.) on starting at any point randomly we can end only at one global minimum but in the Non-Convex loss function, our right figure at some local minima instead of global minima, due to its initial position and the optimization algorithm used.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oqPKBG4iqP92eTveTUyDNQ.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pUH0_5ZvlC2Pya9EQ-b7Tg.gif" /></figure><p>In this blog, we are going to cover the following optimization algorithms:</p><ol><li>Gradient descent</li><li>Stochastic gradient descent</li><li>Hessian optimization</li><li>Stochastic gradient descent with momentum</li><li>RMSprop</li><li>ADAM</li></ol><h3>Gradient Descent &amp; Stochastic Gradient Descent</h3><p>In Optimizing a curve, with the help of calculus we can find the exact point of minimum, but, in modern neural networks, there can be millions or billions of parameters. At such a high number of parameters, calculating that exact point is computationally infeasible, as a result, we have to follow an iterative approach to descent to the optimal minima.</p><p>In both Gradient descent and stochastic gradient descent, we calculate derivatives of loss functions with respect to each model parameter and then iteratively update them using the gradients.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*YKG9fJaZpiIApO8f.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/566/1*ODEORYYueDWVVUYcYE7wWQ.png" /></figure><p>But the main difference arises in the number of examples considered in one complete iteration. While in Gradient descent, you have to run through ALL the samples in your training set to do a single update for a parameter in a particular iteration, in Stochastic Gradient descent, on the other hand, you use ONLY ONE training sample from your training set to do the update for a parameter in a particular iteration. The update rule for Stochastic gradient descent follows as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/812/1*F2daka7glMvLKZIleB0ZHA.png" /></figure><p>If you use SUBSET instead of a single training sample, then it is called Minibatch Stochastic gradient Descent. The update rule for Minibatch Stochastic gradient Descent follows as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/803/1*lShKRdInXd-cH-mYKWcvmA.png" /></figure><p>Usually, Stochastic gradient descent refers to Minibatch Stochastic gradient descent only. Stochastic gradient descent is much faster than gradient descent especially in the case of larger datasets as we don’t have to go through all the training samples but in comparison to Gradient descent, Stochastic gradient descent is noisy. The noise here refers to the addition of unwanted gradients in the data of original gradients. In Gradient descent, loss function usually decreases at each iteration but in Stochastic gradient descent loss function might go up in some or come down.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/602/0*z05TGdqHRuGRsVof" /><figcaption>Contour plot of the loss function</figcaption></figure><p>Here we can see that in the case of the Stochastic gradient descent path to the minima of the contour plot is more zig-zag but in the case of Gradient descent, there is a smooth contour plot.</p><h3>Pathological Curvature</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CGtyE3kzl5pnwpTYJatGEA.png" /><figcaption>Pathological curvature</figcaption></figure><p>First things First, Gradient Descent and Stochastic gradient descent both work particularly badly when they reach pathological curvature. In such type of curvature, there is a direction where the gradient is very high but minima are not in that direction and another direction where the gradient is pretty less but moving in that direction will get to our minima or optimum position.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/890/1*Glp-ciypHYQdQvcSpJhhIQ.png" /></figure><p>The left image shows that how a normal Gradient descent will be going through the pathological curvature, while the right image shows the ideal direction to be followed. Gradient descent continuously fluctuates between the high sloped curvatures with very little progress in the ideal direction.</p><h3>Hessian Optimization</h3><p>Hessian optimization uses the Hessian matrix which encompasses all the double derivatives of the curve. As we have seen in the pathological curvature, the gradient itself is a very incompetent source of information about the curvature, all it can tell is the rate at which the value of the function is changing with respect to the particular parameter.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9_3j3Xp0nblQpIkai2hXEw.jpeg" /></figure><p>Here all the 3 curves have different double derivatives but have identical gradients, it is cases like these where the need of the Hessian matrix becomes evident. Mathematically Hessian matrix is defined as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/470/1*H5CWKQULbHyXPDI-TO65-A.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jOx33IbvbTZFRwHrFJoTQQ.png" /></figure><p>Now, let us see the Procedure of the Hessian Optimization for which we have to understand Newton’s method.</p><p><strong>Newton’s Method </strong>in multivariate functions are approached by approximating the function by Taylor Series to a simple quadratic function in the neighbor of the point. Then we minimize the approximated function to obtain a new point on the original curve. This process is iterated over the whole function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/683/1*mVOtWsjyt9GRO3QSG38ruA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/717/1*RH4EGvzdLyAnjwbwjgj8oA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C1vcAmHr-gQInL3jLwtozA.png" /></figure><p>In practice, the update step can be written as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hVNEKo2Q16I03afiCCMXxg.png" /></figure><p>Here in Hessian optimization, we can see that second-order derivatives play a role in deciding the optimal direction in contrast to the gradient descent where only first-order derivatives are considered.</p><p>Although Hessian (H) has to be positive definite for the descent to take place in the optimal direction, in fact, recent studies (Dauphin et al., 2014; Choromanska et al., 2014) has shown that saddle points are dominating the optimization landscape of deep neural networks, implying that the Hessian is most likely indefinite.</p><p><strong>Levenberg-Marquardt Modification </strong>is used as a modification to newton’s method when the Hessian matrix does not hold up to positive definite as a result the direction obtained does not correspond to the optimal minimum direction. Here the update rule is modified as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/703/1*jbpRv1ISwi_-0ppDSf-sQA.png" /></figure><p>In the first step, we have added an identity matrix multiplied by a constant mu to the original Hessian matrix thus G becomes the modified Hessian matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M1hIrk1EDWr6a52mQTISNQ.png" /></figure><p>Hessian matrix will be positive definite when all the eigenvalues of Hessian matrix are positive. A fairly large value of the constant mu will make sure that all of the eigenvalues of modified Hessian are positive thus modified Hessian will remain positive definite as a result, direction of descent will be in optimal descent direction.</p><p>In the second step, G, the modified Hessian’s inverse is used in the update step, with a step size alpha which prevents divergence.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/915/1*ccTBE7IB6W3v75098_Ejbw.png" /></figure><p>The step for the approximation of a curve to a quadratic approximation is the preconditioning step. Preconditioning can be thought of as a geometric solution to the problem of pathological curvature. It aims to locally transform the optimization landscape so that its curvature is equal in all directions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/913/1*UrZQS9h-ess2NJ0hlDnq4A.png" /></figure><p>On a two-dimensional curve, Preconditioners approximates the curve locally to a quadratic curve, transforming the optimization landscape for equal curvature in all directions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/772/1*SC6bU9S1KBZg4JDc3W44Bg.png" /></figure><p>Practically, there are several computational drawbacks for using Hessian inverse as a preconditioner. Neural networks typically have millions of parameters.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*XJW7vpWqXEDiQa13wCsk6A.png" /></figure><p>Rendering Hessian optimization to be practically infeasible.</p><h3>SGD with Momentum</h3><p>SGD adds noise to the gradients</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/245/1*FoLPjUZyPIaBWdHZOM45kA.png" /></figure><p>Our optimizer oscillates in the direction perpendicular to the optimal direction, which leads to slow convergence. SGD with Momentum helps to reduce the oscillations in perpendicular direction while moving in the optimal direction.</p><p>Now SGD with momentum doesn&#39;t rely solely on current gradients to calculate the direction of descent but it carries a memory of all the past gradients to find the direction of descent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/366/1*Ue7Zh2naByKiHNUY_SQbNQ.png" /></figure><p>The memory is carried by the function V, and each gradient is multiplied to its particular weight corresponding to its contribution towards the direction of descent. This function is similar to the exponentially weighted average function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/942/1*Brp4yZwaPDtfY0C4uIG9AA.png" /></figure><p>As beta lies between [0,1], therefore, the contribution of initial components of function S is decreased, but each component contributes to the function V thus acting as a memory of function V. SGD with momentum exploits this property of exponentially weighted averages.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/892/1*sbzG7KA0NjhDfuhMxVrrkQ.png" /></figure><p>Therefore instead of using a direct gradient in the update step of the parameters, we use its exponential average modified form to take into consideration the previous gradients. This approach also solves the problem of pathological curvature up to some extent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/816/1*Ra5ZawjBy1Lvmsz59f4ZtA.png" /><figcaption>Pathological curvature(front)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d09LRMeoTIieHFg22tBBgQ.png" /><figcaption>pathological curvature (top)</figcaption></figure><p>These are the steps taken by the Gradient descent which is broken down into two components, one which points in the direction of the ideal path of descent (t1, t2, t3) and one perpendicular to it (n1, n2, n3). On applying the Momentum update step, gradients of previous steps start summing up. The components (n1, n2,n3) point opposite to each other, as a result, during summing up of gradients, they tend to cancel out each other thus reducing the component of descent perpendicular to the ideal path of descent, while at the same time (t1,t2,t3) points in the same direction, therefore, they add up to give higher component to the ideal path of descent. This reduces the noise of the gradient and leads to a smoother path towards 0the optima.</p><p>Here, to just form an analogy with standard momentum in physics, beta acts as friction for the original path of gradient descent, as, larger the beta, larger will be the contribution from the previous gradients, thus larger will be deviation from the original path. Function v act as velocity and gradient act as acceleration, as, more will be the gradient, quick changes occur in direction and if more will be the function v, large steps will be taken.</p><p>Usually, the coefficient of momentum(beta) is taken to be equal to 0.9.</p><p><strong><em>Result</em></strong></p><p>→ It solves the problem of pathological curvature, which can’t be solved by the SGD alone.</p><h3>RMSprop algorithm</h3><p>In SGD with momentum, the steps develop a speed in direction of decreasing gradients but when it reaches optimal minima, generally overshoots it and starts fluctuating around that optimal minima.</p><p>RMSprop dampens the gradients in the non-ideal descent direction and accelerates in the ideal descent, but, it does by calculating for each parameter separately.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/490/1*KwURRjOWeqziJJpnxVd_Pg.png" /></figure><p>There’s a lot of things happening in this formula, let’s take it down to pieces.</p><p>The first equation looks pretty much similar to our exponential weighted average equation used in SGD with momentum, but the key difference is that the gradient is squared instead of a single power.</p><p>The second equation is a parameter updating step, but, the gradient is modified by dividing with the exponentially weighted average function. Moreover, both of these equations work on every parameter separately.</p><p>In the first equation, squaring gradients will squish the smaller gradients to be smaller values and throw the larger gradients to larger values, it also affects that now the opposite gradients won’t cancel out and each other and keep adding just like the gradient in the ideal direction of descent. Just like the momentum equation, here also function v will act as memory and store the information about the previously squared gradients with their respective weights multiplied by them.</p><p>In the second equation, the gradient of the loss function is divided by the square root of exponential weighted average function v. If we assume that for a particular parameter w, the corresponding gradient has a high value, thus, the corresponding exponential weighted average will also be high, therefore, in second equation the gradient term would be less. Similarly, if the gradient has a small value, will also have a small exponential weighted average thus in the second equation the gradient term would large. Therefore gradient term will amplify for small gradients and nullify for large gradients.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*_WB9ZsOeG6chBlHAAouZBw.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*8SEPfBIKfmG3uYJRQDPT-w.jpeg" /></figure><p>Here we can see that for the small gradients, the gradient term of the second equation automatically amplifies it to a larger value while for a larger gradient, it gets nullify to a smaller value, this will help us avoid bouncing between the ridges, and move towards the minima.</p><p>Now consider the pathological curvature,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gIsSAt-s4L-9GDIQVxT0_A.png" /><figcaption>Pathological curvature(top)</figcaption></figure><p>Here we can see that gradients along the ideal direction of descent are small and perpendicular to it is large, with RMSprop gradients get reduced in the perpendicular direction and get enlarged along the ideal direction. Also, it doesn’t let gradients along the ideal direction go too large to overshoot the optimum point.</p><p>The steps of RMSprop are done individually to all different parameters, therefore, it has much better control over every dimension of the loss function and can easily modify any individual gradient without affecting any other gradients.</p><p>The Hyperparameter gamma is generally chosen between 0.9 &amp; 1 while it requires tuning accordingly. Hyperparameter epsilon in equation 2 is normally taken around 1e-8, as it is used to avoid the denominator going to zero.</p><p><strong><em>Result</em></strong></p><p>→ It solves the problem of overshooting the optimal minimal position, created in the SGD with momentum optimization algorithm and also solves the problem of pathological curvature.</p><h3>ADAM Optimizer</h3><p>As we have seen, in both SGD with momentum and RMSprop both algorithms were able to address the problem of the pathological curve with different approaches.</p><p>The Adaptive Movement Estimation algorithm or Adam optimizer combines both algorithms in a single algorithm.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*iRVS01R0ykMcStaY2rdSdw.png" /></figure><p>Here we can see that, functions m and v store the information about both the gradient and gradient squared in the exponentially weighted average function. In the third equation, we combine both algorithms by multiplying the gradient with function m and dividing by the square root of function v.</p><p>When we apply both algorithms altogether, the momentum part of the algorithm tries to build speed and take larger steps toward the optimum while the RMSprop part of the algorithm tries to impede the motion by reducing gradients in direction of optimum minimum both of these algorithms together give an interesting result. The effective magnitude of the steps taken in parameter space at each timestep is approximately bounded by the stepsize setting α, whereas there’s no bound on how small the gradient can go which is favorable in case of curvature near-optimal minima.</p><p><strong><em>Result</em></strong></p><p>→ This solves the problem of overshooting optimal minimal position, created in the SGD with momentum optimization algorithm, and also provides an upper bound to the effective magnitude of the steps taken in parameter space at each timestep.</p><h3>Conclusion</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/0*PU8SX0sv1JrYdMVw" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/0*pRH_TYyUhInScq1Z.gif" /></figure><p>We got to learn many optimization techniques throughout, but RMSprop and ADAM usually dominate the most deep learning models. In the visualizations, you can easily see that momentum initially performs poorly on the pathological curvature but with time it builds up momentum in the desired direction and goes with very high speed, and then overshoots the optimal minima. whereas you can see that RMSprop has complete control over their speed.</p><h3>References</h3><p><strong>Visualizations </strong>— <a href="https://imgur.com/a/Hqolp#NKsFHJb">https://imgur.com/a/Hqolp#NKsFHJb</a> , <a href="https://www.math3d.org/">https://www.math3d.org/</a> , <a href="https://youtu.be/IHZwWFHWa-w">https://youtu.be/IHZwWFHWa-w</a>, <a href="https://www.desmos.com/calculator">https://www.desmos.com/calculator</a>, <a href="https://rstudio-conf-2020.github.io/dl-keras-tf/08-LSTMs.html#19">https://rstudio-conf-2020.github.io/dl-keras-tf/08-LSTMs.html#19</a></p><p><strong>Research Papers</strong> — <a href="https://arxiv.org/pdf/1502.04390v2.pdf">https://arxiv.org/pdf/1502.04390v2.pdf</a> , <a href="https://arxiv.org/pdf/1412.6980.pdf">https://arxiv.org/pdf/1412.6980.pdf</a> , <a href="https://arxiv.org/pdf/1502.04390v1.pdf">https://arxiv.org/pdf/1502.04390v1.pdf</a>, <a href="https://arxiv.org/pdf/1611.07476.pdf">https://arxiv.org/pdf/1611.07476.pdf</a> ,<a href="https://arxiv.org/pdf/1609.04747.pdf">https://arxiv.org/pdf/1609.04747.pdf</a>, <a href="http://www.cs.toronto.edu/~jmartens/docs/Deep_HessianFree.pdf">http://www.cs.toronto.edu/~jmartens/docs/Deep_HessianFree.pdf</a></p><p><strong>blogs</strong> — <a href="https://blog.paperspace.com/intro-to-optimization-in-deep-learning-gradient-descent/">https://blog.paperspace.com/intro-to-optimization-in-deep-learning-gradient-descent/</a> ,<a href="https://towardsdatascience.com/understanding-rmsprop-faster-neural-network-learning-62e116fcf29a">https://towardsdatascience.com/understanding-rmsprop-faster-neural-network-learning-62e116fcf29a</a>,<strong> </strong><a href="https://www.cs.ccu.edu.tw/~wtchu/courses/2014s_OPT/Lectures/Chapter%209%20Newton%27s%20Method.pdf">https://www.cs.ccu.edu.tw/~wtchu/courses/2014s_OPT/Lectures/Chapter%209%20Newton%27s%20Method.pdf</a>, <a href="http://people.duke.edu/~kh269/teaching/b553/newtons_method.pdf">http://people.duke.edu/~kh269/teaching/b553/newtons_method.pdf</a></p><p><strong>book </strong>— <a href="https://www.deeplearningbook.org/">https://www.deeplearningbook.org/</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=94a6ee28f7c5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/optimizer-diving-into-deep-neural-networks-94a6ee28f7c5">Optimizer: diving deep into Neural Networks</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What doing research as an undergrad can teach you]]></title>
            <link>https://medium.com/vlgiitr/what-doing-research-as-an-undergrad-can-teach-you-fa6ea1836b97?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/fa6ea1836b97</guid>
            <category><![CDATA[research]]></category>
            <category><![CDATA[academic]]></category>
            <dc:creator><![CDATA[Ayush Mangal]]></dc:creator>
            <pubDate>Fri, 25 Jun 2021 07:11:14 GMT</pubDate>
            <atom:updated>2022-04-09T17:30:13.782Z</atom:updated>
            <content:encoded><![CDATA[<h3>What doing research as an undergrad can teach you.</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/702/1*eC6wJGj5b4K6ACB9_pw4dA.png" /><figcaption>Source — <a href="https://www.nature.com/articles/d41586-020-02847-8">https://www.nature.com/articles/d41586-020-02847-8</a> ( yeah I thought I should mention the source of the images from now on, its a good practice )</figcaption></figure><p>Although my coaching teachers used to say now and then ki</p><blockquote>“itna deep me jaake kya karega topic me, research karni he kya tereko isme?”</blockquote><p>If someone told me in my first few months at college, that I’ll be spending most of my time pursuing research as an undergrad, I would have probably laughed it off. And honestly, it was accidental for most of the part, a random conversation with a senior and some fateful string of events made me consider research as a direction that I would like to explore and then it was just one thing after the other, and it’s not as if I am considering research as a life-career, it’s more of a just for fun kind of activity.</p><p>Also, I am not a full-fledged researcher, I am just an undergrad lol, with only a few small research experiences ( you can find more about it <a href="https://ayushtues.github.io/">here</a>). Most of them happened under the supervision of highly experienced people, and it was more of me doing stuff for their research and not a research of my own per se, and so I shouldn’t be writing this blog, but there are two reasons I am doing so :</p><ul><li>I probably won’t continue to pursue research as a career in future, so I thought I should write down the feeling, the lessons learnt while they are still fresh, just to come back to them after some years and maybe get inspired or stuff.</li><li>It’s been way too long since my last blog post, and I wanted to write about something ( the real reason lol)</li></ul><p>So, I strongly believe, that everyone should try to get some research experience in their undergrad, even if you don’t want to pursue academic research, <strong>especially </strong>if you don’t want to pursue it as a career. But you might find this statement contradictory and ask, what would research teach me? If I don’t want to pursue it as a career, why is this for me?</p><p>Well, that’s what I will talk about in this blog —</p><h3>Bringing Order to Chaos</h3><blockquote>What is research but a blind date with knowledge?</blockquote><blockquote>— Will Harvey</blockquote><p>The most obvious reason for getting research experience that comes to my mind is that it teaches you how to approach an abstract, unstructured problem and gradually bring order to all the chaos, structure stuff up, and devise a solution to a seemingly unsolvable problem.</p><p>Usually, research problem statements are poorly specified, and there is no right or wrong answer to them, no one knows how to solve them accurately, and you get to work on the frontiers of human knowledge, and although it’s doubtful that you’ll be able to make the next great discovery that will lead humankind to salvation, you might be able to take a small small part in the conversation of experts of the world and maybe help shift the conversation from one point to another ( or you can get effectively remain unknown and practically dead for the community, and well, there’s a graveyard for all such dead ideas — <a href="https://arxiv.org/">arxiv.org</a> 😛)</p><p>This ability is precious in whatever career you want to pursue, problems in the real world are like research problems too, they don’t have one correct answer ( maybe they don’t have any answer at all ), but you still need to make hypotheses, test it, and then repeat, and that’s precisely what doing research teaches you. I personally feel more confident about tackling any problem in any field after doing some research work, because it has taught me how to approach a problem statement scientifically and break it down into smaller manageable subproblems.</p><h3>Standing on the Shoulder of Giants</h3><p>A researcher who believes that he can figure it out all by himself is probably not a very good one. Good researchers respect the opinions of people who came before them, dive deep into their work, what they did, what problems they discovered and how they tackled them. A lot of good research work has been done by taking inspiration from something done by someone lots of years back, which was forgotten over time, and redesigning it into the present. In fact, Issac Newton famously quoted —</p><blockquote>If I have seen further it is by standing on the shoulders of Giants</blockquote><blockquote>— Issac Newton</blockquote><p>And well, I don’t think anyone is vain enough to believe they are smarter than this guy, so if the biggest daddy out there in research says that respect those who came before, you bet we do precisely that.</p><p>Also, research is a highly collaborative environment. People openly discuss ideas ( albeit, there are some constraints due to the ideas being an intellectual property ), they welcome criticism of their works since they believe that the problem statement they are working on is yet unsolved, they are probably not lucky enough to have it all figured out correctly. And I think this is a bit more prevalent in the US and a bit less in India as of now, but hopefully, that would change in the future.</p><p>Working in such an environment would pay off in alternate careers, because well, developing a collaborative spirit is quintessential to success. You get comfortable with putting your “ego” aside and look for ideas from everywhere. You become intellectually humble, and begin to realise that one cannot possibly know everything about anything and also begin to respect other people’s work. You stop discarding things as inherently easy because you know that there is probably some really complex research going on even for something seemingly simple. Personally doing research has made me more open to asking for help from others ( sometimes I think I ask for help a little too much lol, but that’s okay ) and also appreciate the inherent complexity of stuff around us.</p><h3>The art of storytelling</h3><blockquote>The human species thinks in metaphors and learns through stories</blockquote><blockquote>— Mary Catherine Bateson</blockquote><p>A critical part of life as a researcher is making other people believe that your work is actually worth considering in the larger conversation going about that problem. And what better than storytelling to make a large group of people believe in something ( take religion, for example, it’s mostly storytelling used to unite a people under a common idealogy ).</p><p>Even while writing a research paper, a lot of effort goes into making stuff sound coherent and in line with the overall “story” you are putting forward. You conduct experiments that further strengthen your story’s validity. You review other people’s version of the story and try to add some quirks of your storytelling into it. A PhD thesis is basically a story of your beliefs, and a PhD defence puts that story to the test, hoping that you can make others believe it.</p><p>Again this art of storytelling is a vital skill in any career. Say you want to be an entrepreneur, I can’t imagine someone being successful as an entrepreneur without storytelling. You need to make people believe in your story for making them work with you, and you need customers to believe in your story to buy services/products from you. Political parties need people to believe in their story if they want to come to power. The human population has grown to such a level, that to unite these many people, what works the best is making them believe in a common story.</p><p>Also, as an added bonus, as a researcher, you have to give a lot of presentations ( since you need to present your research work to multiple peoples, at various conferences, guest lectures, reading groups etc. etc. ). So you also get to learn the crucial skill of making great presentations quickly and also a lot of time you have to present complex research work to people who don’t necessarily have the same level of expertise in that area, so you also learn how to simplify complicated stuff and explain it in a simple manner, and that my dear reader, is genius.</p><h3>Do or Do not. There is no try.</h3><blockquote>Research teaches a man to admit he is wrong and to be proud of the fact that he does so</blockquote><blockquote>— H.E. Stocher</blockquote><p>This one is probably the most critical thing research has perhaps taught me personally. Rejection becomes a daily thing for people doing research and failure your only true companion. You work your ass off on a research paper, spending countless hours, doing tedious experiments, and submit it for peer review, and then get it rejected by the whims of a moody reviewer. Also, especially as an undergraduate, research opportunities are sparsely available. You get rejected a lot while applying for research positions, hell most of the people don&#39;t even bother replying to undergrads lol.</p><p>Also doing research requires you to be quite persistent and intrinsically motivated. It’s quite common to feel lost in the process of finding the answer to your question, and help is not readily available, cause well, its a research problem, nobody really knows/cares about it other than you and probably a few more people. You need to stay motivated and keep trying and trying until you finally overcome it or decide to pivot around the issue ( knowing when to pivot and change your hypothesis when stuff isn’t working is also a crucial skill in itself).</p><p>When failure becomes a daily thing for you, you start getting used to it; you become used to give it your all, knowing that you might fail. This ability is vital in any career, and it makes you fearless and bold, and more willing to take risks. I personally feel that after getting rejected so many times in my early applications in finding research, I have become quite shameless about failing and have become used to doing whatever it takes to get shit done.</p><h3>Some other stuff…</h3><p>Here are some other points that come to my mind, but I don’t want to drag the post too long, so I’ll cover them quickly.</p><ul><li>It makes you a faster reader and makes you able to gather knowledge pretty quickly, which is a bit obvious since you spend most of the time reading research papers and seeing other people’s work.</li><li>It makes you more creative since you have to figure out novel solutions to problems day in and out. You can’t just repeat a previous idea, you’ve got to think something new, hell, you might be trying to solve something that no one else did before, you obviously have to be highly creative.</li><li>It teaches you to respect the small details and how to follow rigorously meticulous experimental procedures. I think doing research has made me better at organising stuff and following the proper procedure of things even if it’s boring.</li><li>You become better at expressing your ideas, concisely and clearly. Research papers usually have an upper bound on the length of pages, and thus you get used to explaining stuff in as little words as possible ( although you do tend to start using more jargons, but ah well there is no free lunch )</li><li>You get used to breaking down a problem to its core and doing things from first principles ( like a physicist ), an approach used by highly successful people like Elon Musk to reimagine the world.</li></ul><p>While I might not continue pursuing research as a career, I am grateful for whatever research experience I got in the last year. It fundamentally changed the way I approach problems. I hope this article might motivate more people to give it a shot even if they don’t want to become a scientist and remove the stigma surrounding research from their mind ( cause well, even I thought research was for weirdos with a grey beard when I started xD ).</p><p>As usual, feel free to hit me up if you have any feedback for my writing, I would highly appreciate that! Also hey, let’s talk anyway! Its been a long year, and I am sure you have a lot of interesting stuff to share :P</p><p>Until then….Stay safe!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fa6ea1836b97" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/what-doing-research-as-an-undergrad-can-teach-you-fa6ea1836b97">What doing research as an undergrad can teach you</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[METRIC LEARNING: It’s all about the Distance]]></title>
            <link>https://medium.com/vlgiitr/metric-learning-its-all-about-the-distance-143a199ab7a5?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/143a199ab7a5</guid>
            <category><![CDATA[eli5]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[metric-learning]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Keerat Kaur Guliani]]></dc:creator>
            <pubDate>Wed, 30 Sep 2020 13:21:38 GMT</pubDate>
            <atom:updated>2020-09-30T14:07:07.223Z</atom:updated>
            <content:encoded><![CDATA[<h3>Metric Learning: It’s all about the Distance</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/688/1*CkMj7c_ybj_ly95lgp-WpQ.jpeg" /></figure><blockquote><em>Metric Learning = Metric + Learning</em></blockquote><p>We’re sufficiently familiar with both these words. Metric stands for a measure of quantitative assessment, such as a meter for length, and learning refers to the process of acquiring knowledge through study or experience. Interpreting the combination of both these words in the context of Machine Learning, we can define metric learning as the process of learning to define the most appropriate measure of similarity(or differences) over objects under consideration.</p><p>Mathematically, we can define a metric as follows:</p><p><em>A metric on a set</em> <em>X</em> <em>is a function (called the distance function or simply distance).</em></p><p><em>d </em>: <em>X </em>× <em>X </em>→ <em>R,</em></p><p><em>where</em> <em>R</em> <em>is a set of real numbers, and for all x,y,z in</em> <em>X</em> <em>following condition are satisfied:</em></p><ol><li><em>d(x, y) </em>≥ <em>0</em> <em>(non-negativity)</em></li></ol><p><em>2. d(x, y) = 0 if and only if x = y</em> <em>(coincidence axiom)</em></p><p><em>3. d(x, y) = d(y, x) (symmetry)</em></p><p><em>4. d(x, z) </em>≤ <em>d(x, y) + d(y, z)</em> <em>(triangle inequality).</em></p><p>Here’s how the pipeline for metric learning is different from the one we use for regular ML tasks:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O3GT5yKPzFoGZpXKjNNCvA.gif" /></figure><h3><strong>In a Nutshell-Convex Optimisation Problems</strong></h3><p>Take a deep breath. Especially if you don’t know what Convex Optimisation Problems are. Or just take one anyway.</p><p>Let’s deal with convex functions first. A real-valued function is called a convex function if the line segment joining any two points on the graph always lies on/above the graph.</p><p>Here’s to visualize this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*u4i3HDWGnw7l0s2HZ5Q5qA.gif" /></figure><p>Clearly, convex functions can have only one local minima, which also happens to be the global minima. It’s derivative is forever non-decreasing, and definitely no flat regions in the function’s graph.</p><blockquote>Convex Optimisation Problems = Optimisation problems on Convex functions</blockquote><p>Naturally, the only optimization you can perform in this case will be minimization.</p><p>But why did we jump from metric learning to Convex problems in a flash? Because in a nutshell, metric learning problems are also convex optimization problems. They can be formulated as</p><pre><em>                    min M ℓ(M, S, D, R) + λR(M)</em></pre><p>where <em>ℓ(M, S, D, R)</em> is the loss function, R(M) is some regularizer on the parameters M of the learned metric, and λ ≥ 0 is the regularization parameter.</p><h3><strong>Why talk about Metric Learning? That’s not really the end goal, right?</strong></h3><p>Sure it isn’t. Depending upon the case, the end goal could be coming up with the correct prediction in a classification or regression problem. So why waste time and resources on learning the metric before the trend of the data?</p><p>It is imperative that the metric used captures the behavior of the data correctly, which directly impacts the performance of the learning algorithm, and generally proposed distance metrics like Euclidean distance, Manhattan distance, etc often fail to do so. Thus, in the absence of any prior knowledge about the data, we must tune the metric to the data and the problem, deriving the most appropriate measure from the high dimensional data itself. This leads us to invest our efforts into metric learning.</p><blockquote><em>The goal of metric learning is to propose a metric that assigns small distances between similar points and larger distances between dissimilar points.</em></blockquote><p><strong>Fun Fact: </strong>Similarity Learning represents a concept similar to that of metric learning, but with much lesser restrictions.</p><p>The goal appears to be similar: to learn a similarity function that measures how similar or related two objects are. However, <em>Similarity learning deploys a similarity function, which may or may not qualify as a distance metric</em>.</p><p>For instance, often in ranking systems, functions of a specific type known as bilinear functions are used as similarity functions, which may or may not be symmetric. Note that symmetry is one of the 4 criteria required for any similarity function to qualify as a metric, as mentioned above. So bilinear functions that are skew-symmetric can be used for similarity learning but not for metric learning.</p><h3><strong>The idea of a Pseudometric</strong></h3><p>Often, certain distances called pseudo-(meaning ‘false’) metrics make an appearance in metric learning problems, rather than a metric. A pseudometric is a distance that does not follow the coincidence axiom (<em>d(x, y) = 0 if and only if x = y</em> ) but has all other features belonging to a regular metric function. So, a pseudometric allows the distance between two different points to be zero.</p><p>Confused how? Let’s take an example.</p><p>Consider a function</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/56/0*GQnvqNtNcjUBMG4L" /></figure><p>and a pseudometric</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/135/0*MfrjT7CKAtOlpJIO" /></figure><p>defined on the set of all functions. Clearly, g is</p><ul><li>Non-negative</li><li>Symmetric</li><li>Fulfills the triangle inequality</li></ul><p>However, in the case of the coincidence axiom, we find that while</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/67/0*USabm7pST13aFzUo" /></figure><p>is true, we also have</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/89/0*0KQLoAk3JD-lCJuL" /></figure><p>where clearly g(x,y) is zero despite x and y being distinct.</p><p>Pseudometrics had to be defined owing to their natural existence in scenarios such as those of functional analysis and complex manifolds, which are beyond the scope of this article.</p><h3><strong>Metric Learning Methods</strong></h3><ol><li>Supervised Metric Learning: Supervised metric learning algorithms take as input points <strong>X</strong> and target labels <a href="https://scikit-learn.org/stable/glossary.html#term-175"><strong>y</strong></a>, and learn a distance matrix that makes points from the same class (for classification) or with close target value (for regression) close to each other, and points from different classes or with distant target values far away from each other.</li></ol><p>Common supervised metric learning algorithms include:</p><ul><li>Large Margin Nearest Neighbor Metric Learning (<a href="http://contrib.scikit-learn.org/metric-learn/generated/metric_learn.LMNN.html#metric_learn.LMNN"><strong>LMNN</strong></a>)</li><li>Neighborhood Components Analysis (<a href="http://contrib.scikit-learn.org/metric-learn/generated/metric_learn.NCA.html#metric_learn.NCA"><strong>NCA</strong></a>)</li><li>Local Fisher Discriminant Analysis (<a href="http://contrib.scikit-learn.org/metric-learn/generated/metric_learn.LFDA.html#metric_learn.LFDA"><strong>LFDA</strong></a>)</li><li>Metric Learning for Kernel Regression (<a href="http://contrib.scikit-learn.org/metric-learn/generated/metric_learn.MLKR.html#metric_learn.MLKR"><strong>MLKR</strong></a>)</li></ul><p>You can read more about each of these <a href="http://contrib.scikit-learn.org/metric-learn/supervised.html">here</a>.</p><p>2. Unsupervised Metric Learning: Unsupervised metric learning algorithms only take as input an (unlabeled) dataset <strong>X </strong>and aim to learn a metric without supervision. A simple baseline algorithm for this task is ‘Covariance’- as the name suggests, it works by calculating the Covariance of the input data.</p><p>3. Semi-Supervised Metric Learning: These techniques take as input a small amount of labeled dataset (x,y) combined with a large amount of unlabelled dataset (x) as input for training, making them fall somewhere between supervised and unsupervised methods, as rightly suggested by their name.</p><p>4. Weakly Supervised Metric Learning: Weakly supervised algorithms work on weaker information about the data points than supervised algorithms. Rather than labeled points, they take as input similarity judgments on tuples of data points, for instance, pairs of similar and dissimilar points. Note the difference between Semi- and Weakly- Supervised Metric Learning.</p><p>Commonly featured algorithms include:</p><ul><li>Information-Theoretic Metric Learning (<a href="http://contrib.scikit-learn.org/metric-learn/generated/metric_learn.ITML.html#metric_learn.ITML"><strong>ITML</strong></a>)</li><li>Sparse High-Dimensional Metric Learning (<a href="http://contrib.scikit-learn.org/metric-learn/generated/metric_learn.SDML.html#metric_learn.SDML"><strong>SDML</strong></a><strong>)</strong></li><li>Relative Components Analysis (<a href="http://contrib.scikit-learn.org/metric-learn/generated/metric_learn.RCA.html#metric_learn.RCA"><strong>RCA</strong></a>)</li><li>Metric Learning with Application for Clustering with Side Information (<a href="http://contrib.scikit-learn.org/metric-learn/generated/metric_learn.MMC.html#metric_learn.MMC"><strong>MMC</strong></a>)</li></ul><p>More information on each of these algorithms can be found <a href="http://contrib.scikit-learn.org/metric-learn/weakly_supervised.html">here</a>.</p><h3><strong>Applications of metric learning</strong></h3><p>Technically, any problem that makes use of machine learning algorithms like k-nearest neighbors, k-means, SVMs, etc can deploy metric learning to boost their performance. However, metric and similarity learning most commonly find their use in the following:</p><ol><li>Recommendation systems (like those used in Netflix, Youtube, etc)</li></ol><p>2. Ranking based problems</p><p>3. Face identification/verification systems.</p><p>4. Patient similarity ( Identification of historical records of patients who are similar to the new patient to help predict clinical outcomes for the new patient).</p><p>5. Semantic textual similarity( To determine how similar 2 pieces of texts are), and other such image, video, text, and audio tasks.</p><p><strong>Tip for extra reading: </strong>Survey/Review papers usually serve as excellent reading material for any topic. They’re essentially research papers that compile the gist of all existing research on a topic in an organized fashion, with some added inputs from the authors. Naturally, they’re long reads but provide a perspective of the development in any field.</p><p>For metric learning, I came across the following survey papers and found them useful- <a href="https://www.mdpi.com/2073-8994/11/9/1066/htm">Deep Metric Learning: A Survey</a> and <a href="https://arxiv.org/pdf/1306.6709.pdf">A Survey on Metric Learning for Feature Vectors and Structured Data</a></p><p><strong>References:</strong></p><ol><li><a href="https://www.math.wustl.edu/~freiwald/ch2.pdf">Metric and pseudometric spaces</a></li><li><a href="https://www.mdpi.com/2073-8994/11/9/1066/htm">Deep Metric Learning: A Survey</a></li><li><a href="https://pdfs.semanticscholar.org/b23e/1b99ae1c3d231f2502959aaee143997456ce.pdf">Metric Learning Tutorial</a></li></ol><p>4. <a href="https://en.wikipedia.org/wiki/Pseudometric_space">Pseudometric Space</a></p><p>5. <a href="https://en.wikipedia.org/wiki/Similarity_learning#Metric_learning">Metric Learning</a></p><p>6. <a href="https://www.researchgate.net/publication/224215792_Machine_learning_of_patient_similarity_A_case_study_on_predicting_survival_in_cancer_patient_after_locoregional_chemotherapy">Machine Learning in Patient Similarity</a></p><p>7. <a href="http://contrib.scikit-learn.org/metric-learn/user_guide.html">Metric Learning Scikit Guide</a></p><p>8. <a href="https://en.wikipedia.org/wiki/Semi-supervised_learning">Semi-Supervised Learning</a></p><p>9. <a href="https://arxiv.org/pdf/1306.6709.pdf">A Survey on Metric Learning for Feature Vectors and Structured Data</a></p><p>10. <a href="https://en.wikipedia.org/wiki/Convex_function#Properties">Convex functions</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=143a199ab7a5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/metric-learning-its-all-about-the-distance-143a199ab7a5">METRIC LEARNING: It’s all about the Distance</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Curse of Dimensionality]]></title>
            <link>https://medium.com/vlgiitr/the-curse-of-dimensionality-15f950e519d2?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/15f950e519d2</guid>
            <category><![CDATA[eli5]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[dimensionality-reduction]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Jitesh Jain]]></dc:creator>
            <pubDate>Wed, 10 Jun 2020 18:36:37 GMT</pubDate>
            <atom:updated>2020-06-10T18:36:36.710Z</atom:updated>
            <content:encoded><![CDATA[<p>Have you ever found yourself stuck in the middle of a problem having a large number of dimensions? You keep on trying harder and harder to come up with a solution that would satisfy all the dimensions of the problem. Still, every time one or another dimension makes ur efforts look futile! It turns out that you can solve a problem very efficiently when presented with not more than 2 or 3 dimensions. Nevertheless, this world is not kind to us every time! You might find yourself struggling amidst a problem, thinking about as many as hundreds or thousands of dimensions simultaneously!</p><p><em>Now, you may ask: “Wait! Does that happen in real life, or are you just making stuff up to sound cool?”</em></p><p>Well, it does happen! Fortunately, in our day to day lives, we do not observe these complications unless faced with an exceptionally complex (mathematical) task. Take some time to appreciate the ability of your mind to effortlessly solve complex tasks for you!</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F5472197&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fsmart-wise-good-brain-gif-5472197&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2Fad072c9dad430ed1631efa8fb631ce2d%2Fraw&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/69397e71f7993214bb8ef7b00b1e1bdb/href">https://medium.com/media/69397e71f7993214bb8ef7b00b1e1bdb/href</a></iframe><p>Again, you may ask: “Why should I care about this?”</p><p>With the rise of <em>Artificial intelligence</em><strong><em>, </em></strong>the large number of dimensions present a problem that, if not taken care of, might render all your efforts developing an algorithm just futile! You might end up all confused and lost around your developed model. You might feel as if been cursed by some evil power :P</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F16335101&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Fralph-crazy-cursed-this-place-is-cursed-friday-the13th-gif-16335101&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2Fde9859308980f522179c8fd9a61c0747%2Ftenor.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/80e226f4ac1db0530ec57e1897520b46/href">https://medium.com/media/80e226f4ac1db0530ec57e1897520b46/href</a></iframe><p>All right! Now you understand the importance of confronting <strong>The Curse of Dimensionality</strong>. Let’s dive in to understand the concept behind the curse and how to nullify its effect!</p><h3>What is the “curse”?</h3><p>The <strong>curse of dimensionality</strong>, first introduced by mathematician Richard Bellman, indicates that the<strong><em> number of samples needed to estimate an arbitrary function with a given level of accuracy grows exponentially with respect to the number of input variables (i.e., dimensionality) of the function.</em></strong></p><p>Let us understand with an example: We have six balls, three of which belong to category BLUE, and the other three belong to the category RED. Now, let’s say our pet dog wants to play only with <strong><em>bluish</em></strong> balls. We want to develop an ML algorithm to cluster out the balls so that we do not have to separate them.</p><p>We have two options for choosing our training set. Let us see what happens, selecting either one of them:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/881/1*gMTN34Y4q36ub_R_zKmXBQ.png" /><figcaption>Training set with <strong>two</strong> features.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FQJRA5LXmJGT3cddWEm_bg.gif" /><figcaption>Our pet would be happy!</figcaption></figure><blockquote>There are six balls, each one is either bluish or reddish in color.</blockquote><blockquote>Two perfect clusters are formed by the learning algorithm.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ssmmckkYvSHmBydLfD3UjA.png" /><figcaption>Training set with <strong>six</strong> features.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IvUzxk2XhLnpodzc21-obA.gif" /><figcaption>Our algorithm botched!</figcaption></figure><blockquote>There are six balls, each one having a unique color.</blockquote><blockquote>Six clusters are formed by the learning algorithm.</blockquote><blockquote>The algorithm is stuck inside the vortex of dimensionality.</blockquote><p>So, which one should we choose? 1st one, right? Yes indeed! The 2nd training set suffers from <strong><em>The Curse of Dimensionality.</em></strong></p><p>Now, we understand what the curse is. Let’s see what might be leading to it and its implications.</p><h3>Why might this be happening?</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*BQU6tPltWewFGq0Ss_GrQQ.gif" /><figcaption>Reaction after seeing results cursed by DIMENSIONALITY.</figcaption></figure><blockquote>(Number of Features) &gt; (Number of Observations)</blockquote><ul><li>The Curse of Dimensionality refers to the situation when our data has too many features, i.e., the algorithm is not learning the required target function but instead gets caught in the vortex of dimensions.</li><li>It is similar to when someone tries to explain something to you in a complicated way, talking about things that do not relate to the concerned topic. The person is completely off the subject with so many unimportant features.</li><li>In our example with six balls, the <em>training set 2</em> had values too, which made the number of dimensions (or features) six against only two observations (bluish or reddish).</li><li>The added features act as <strong>noise</strong> in the data, which decreases the accuracy of our model.</li></ul><h3>What are the implications?</h3><p>In today’s big data world, when your data has a massive number of dimensions, <em>the curse of dimensionality </em>can create issues in your learning algorithm:</p><h4>1. Overfitting</h4><ul><li>Overfitting occurs when estimating relatively few parameters in higher dimensional space or estimating many parameters in lower-dimensional space. Additionally, the variance of a parameter estimate increases if the number of parameters to be estimated increases.</li><li>In contrast, the bias of the estimate and the size of the training set are constant, which suggests that the quality of the parameter estimates decreases as the dimensionality rises due to increasing variance.</li><li>If we have more features than observations than we run the risk of massively overfitting our model — this would generally result in terrible out of sample performance.</li></ul><h4>2. Sparsity</h4><ul><li>The exponential growth in data causes high sparsity in the data set, i.e., the volume of the space represented proliferates that the data cannot keep up and thus becomes sparse.</li></ul><blockquote>Let’s play a game: we have lost 5 coins and need to find them in three different situations:</blockquote><blockquote>First: Just one feature: on a 10 m line (1 dimension) — Easy to find the coins!</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cPra4DHsE8kWbOK8fMmZsg.gif" /></figure><blockquote>Second: Add a feature: on a 100 m² square — Need to put more effort now.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NvaA5LgInOxKm5r51SuGCg.gif" /></figure><blockquote>Third: Add another feature: inside a 1000 m³ cube — No more interested in playing!</blockquote><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F15650143&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Ffriends-stop-youre-killing-me-chandler-bing-stop-gif-15650143&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2F430091f4c89d946dcb803d13a34fdc19%2Ftenor.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/74b7bfb2c4c5fa58a89d6ade630d179b/href">https://medium.com/media/74b7bfb2c4c5fa58a89d6ade630d179b/href</a></iframe><ul><li>The difficulty in finding the coins in a high-dimensional space implies a vital fact: the points tend to distribute more sparsely (i.e., they are more dissimilar to each other) in high-dimensional space because the Euclidean distance between two points is significant as long as they are far apart in the direction of at least one dimension, even though they may be quite close in the direction of all the other dimensions.</li></ul><h4>3. Euclidean Distance</h4><ul><li>When we have too many features, observations become harder to cluster.</li><li>Too many dimensions cause every observation in your dataset to appear equidistant from all the others. And because clustering uses a distance (eg., Euclidean distance) to quantify the similarity between observations, this is a big problem.</li><li>If the distances are all approximately equal, then all the observations appear equally alike (as well as equally different). No meaningful clusters can form as in our six balls example with <em>training set 2.</em></li></ul><p>Let’s understand intuitively! Read the formula below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*t775iIko8I7n6xlCPxM3MA.png" /><figcaption>The percentage of overall space filled by a hypersphere inside a hypercube.</figcaption></figure><p>The above formula generalizes the percentage of space filled by a hypersphere inside a hypercube for all dimensions <em>n, where Γ(n/2 +1 ) is the </em><a href="http://mathworld.wolfram.com/GammaFunction.html">Gamma function</a>. It can be easily observed that the above quantity tends to approach <strong><em>zero</em></strong> for higher values of n, which suggests that more and more data starts to concentrate at the corners(i.e., towards a single dimension) of the hypercube, which not only increases sparsity but also renders the distance function obsolete.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*rX_fK7MkNloWx-zs4y-qNg.png" /><figcaption>The generalized formula for the volume of a hyper-sphere with radius <em>r </em>in <em>n</em> dimensions.</figcaption></figure><h4>4. Computational Power</h4><ul><li>Working with data becomes more demanding as the number of dimensions increases. Like many challenges in data science, this boils down to combinatorics.</li><li>With high-dimensional data, we simply cannot comprehensively sample all the possible combinations, leaving vast regions of feature space in the dark.</li></ul><h4>5. Dimensional Redundancy</h4><ul><li>We may not even need to subject our machines to such demanding work. Having many dimensions is no guarantee that every dimension is especially useful. A lot of the time, we may be measuring the same underlying pattern in several different ways.</li><li>Generally, values added by many dimensions in high-dimensional data is redundant for our algorithms.</li></ul><p>Now, one question that might be going in your mind might be:</p><blockquote>“How to decide the best number of features for our training?”</blockquote><p>Unfortunately, no fixed rule defines how many features we should use in a regression/classification problem. <strong>The magic number depends on the amount of training data available, the complexity of the decision boundaries, and the type of classifier used.</strong></p><p>For example, if a theoretical number of training examples were available, we would not have to deal with this curse. We could simply use an infinite number of features to obtain the perfect classification. However, an infinite number of features requires an infinite number of training examples, eliminating the real-world usefulness of our network!</p><h3>Hughes Phenomenon</h3><p>Hughes phenomenon shows that as the number of features increases, the classifier’s performance increases as well until we reach the optimal number of features. Adding more features based on the same size as the training set will degrade the classifier’s performance.</p><p>Most disconcerting, the number of training data needed increases exponentially with each added feature.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/510/1*ZuFOzQawXnw_CUnVpRDLgA.png" /><figcaption>As the dimensionality increases, the classifier’s performance increases until we reach the optimal number of features. We notice that further increasing the dimensionality without increasing the number of training samples results in a decrease in classifier performance.</figcaption></figure><h3>Breaking free of the CURSE</h3><p>All right! So far, we have seen what the curse is and how it affects our models, and you might be waiting for the solution to the <strong><em>curse of dimensionality. </em></strong>Fortunately, some techniques help us to combat this problem, let’s learn about them.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/130/0*VIdG77rqLzIQl8Nb" /><figcaption>The saviors are here!</figcaption></figure><p>As you might have guessed, the best way to train our model on the limited training data is to reduce the number of features (or dimensions). One algorithm capable of doing it is known as <strong>Dimensionality Reduction.</strong></p><ul><li>The algorithm starts by locating the underlying trends in our features, i.e., extracting the features out of the data.</li><li>In data science, these underlying trends hidden in our features are often called latent features.</li><li>Next, the algorithm estimates and rewrites every other feature in terms of their exposures to these latent features.</li><li>We can then classify data points using distance measures.</li></ul><p>Some of the techniques for <em>Dimensionality Reduction are:</em></p><h4>1. Principal Component Analysis (PCA)</h4><ul><li>PCA seeks to explain the correlation structure of a set of predictor variables, using a smaller set of linear combinations of these variables. These linear combinations are called <em>components</em>.</li><li>It means that the total variability of a data set produced by the complete set of <strong>m variables </strong>can be accounted for by a smaller set of <strong>k linear combinations.</strong> There is almost as much information in the k components as there is in the original m variables.</li><li>Check out <a href="https://medium.com/vlgiitr/principal-components-analysis-82a7682323e6">this</a> link for more information on PCA.</li></ul><h4>2. Linear Discriminant Analysis (LDA)</h4><p>PCA seeks axes that best describe the variation within the data. Linear Discriminant Analysis (LDA) finds axes that best discriminate between two or more classes within the data.</p><p>We can achieve the task by calculating two measures:</p><ul><li><strong>within-class variance</strong></li><li><strong>between-class variance</strong>.</li></ul><p>The objective is to optimize the ratio between them. There is minimal variance <strong>within</strong> each class and maximal variance <strong>between</strong> the classes.</p><p>For more methods on how to combat the curse of dimensionality, check out <a href="https://www.freecodecamp.org/news/the-curse-of-dimensionality-how-we-can-save-big-data-from-itself-d9fa0f872335/">this</a> link.</p><h3>Conclusion</h3><p>Today, we confronted the <strong><em>Curse of Dimensionality. </em></strong>We saw the reasons leading to the curse, how it affects our algorithms and at the end, ways to break free of the curse.</p><p>A careful choice of the number of dimensions (features) to be used is the prerogative of the data scientist training the network. In general the smaller the size of the training set, the fewer features one must use. One must keep in mind that each added feature increases the data set requirement exponentially.</p><p>Now, we understand the importance of selecting the right number of dimensions for our training data!</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Ftenor.com%2Fembed%2F7569635&amp;display_name=Tenor&amp;url=https%3A%2F%2Ftenor.com%2Fview%2Felmer-thumbs-up-gif-7569635&amp;image=https%3A%2F%2Fmedia.tenor.com%2Fimages%2Fe63c3a9190f521ea84adbea685728342%2Ftenor.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=tenor" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/0b34418d82cac298ec57ee55cd5dd0c8/href">https://medium.com/media/0b34418d82cac298ec57ee55cd5dd0c8/href</a></iframe><p>Congratulations on making it through the article!</p><p><em>NOTE: The animations were created using the </em><a href="https://github.com/3b1b/manim"><em>manim</em></a><em> engine. The code for the animations can be found on </em><a href="https://github.com/praeclarumjj3/manim_anim"><em>GitHub</em></a><em>.</em></p><h3>References</h3><ul><li><a href="https://www.freecodecamp.org/news/the-curse-of-dimensionality-how-we-can-save-big-data-from-itself-d9fa0f872335/">Blog by Peter Gleeson</a></li><li><a href="https://towardsdatascience.com/the-curse-of-dimensionality-50dc6e49aa1e">https://towardsdatascience.com/the-curse-of-dimensionality-50dc6e49aa1e</a></li><li><a href="https://medium.com/diogo-menezes-borges/give-me-the-antidote-for-the-curse-of-dimensionality-b14bce4bf4d2">https://medium.com/diogo-menezes-borges/give-me-the-antidote-for-the-curse-of-dimensionality-b14bce4bf4d2</a></li><li><a href="https://blog.datasciencedojo.com/curse-of-dimensionality-python/">https://blog.datasciencedojo.com/curse-of-dimensionality-python/</a></li><li><a href="https://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/">https://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=15f950e519d2" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/the-curse-of-dimensionality-15f950e519d2">The Curse of Dimensionality</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Principal Component Analysis]]></title>
            <link>https://medium.com/vlgiitr/principal-components-analysis-82a7682323e6?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/82a7682323e6</guid>
            <category><![CDATA[dimensionality-reduction]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[eli5]]></category>
            <category><![CDATA[apc]]></category>
            <category><![CDATA[statistics]]></category>
            <dc:creator><![CDATA[Ankit Biswas]]></dc:creator>
            <pubDate>Tue, 02 Jun 2020 19:24:18 GMT</pubDate>
            <atom:updated>2020-06-03T03:19:43.578Z</atom:updated>
            <content:encoded><![CDATA[<p>Principal component analysis (PCA) is one of a family of techniques for taking high-dimensional data and using the dependencies between the variables to represent it in a more tractable, lower-dimensional form, without losing too much information. It is one of the simplest and most robust ways of achieving <strong>dimensionality reduction</strong>.</p><p>What we do is that we start with p-dimensional vectors, and want to summarize them by projecting down into a q-dimensional subspace. There are several equivalent ways of deriving the principal components mathematically. The simplest one is by finding the projections which maximize the variance because the higher the variation, the easier it is to distinguish individual entities even after reducing feature dimensions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*dh72Kx1U7FPjxkCiqnrQMg.gif" /><figcaption>Reducing Dimensions</figcaption></figure><p>The first principal component is the direction in space along which projections have the highest variance. The second principal component is the direction that maximizes variance among all directions orthogonal to the first. The kth component is the variance-maximizing direction orthogonal to the previous k − 1 component. There are p principal components in all.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*2OGtkHgofDhIoF-YBJeWYw.gif" /><figcaption>Principal Components are orthogonal.</figcaption></figure><p><strong>Important</strong></p><p>Geometrically, PCA corresponds to “centering the dataset” and then rotating it to align the axis of highest variance with the principle axis.</p><h3>Assumptions</h3><ol><li><strong>Sample size</strong>: Minimum of 150 observations and ideally a 5:1 ratio of observation to features.</li><li><strong>Correlations</strong>: The feature set is correlated, so the reduced feature set effectively represents the original data space.</li><li><strong>Linearity</strong>: All variables exhibit a constant multivariate normal relationship, and principal components are a linear combination of the original features.</li><li><strong>Outliers</strong>: No significant outliers in the data as these can have a disproportionate influence on the results.</li><li><strong>Large variance implies more structure</strong>: high variance axes are treated as principal components, while low variance axes are treated as noise and discarded.</li></ol><h3>Limitations</h3><ol><li><strong>Model performance</strong>: PCA can lead to a reduction in model performance on datasets with no or low feature correlation or does not meet the assumptions of linearity.</li><li><strong>Classification accuracy</strong>: Variance based PCA framework does not consider the differentiating characteristics of the classes. Also, the information that distinguishes one class from another might be in the low variance components and may be discarded.</li><li><strong>Interpretability</strong>: Each principal component is a combination of original features and does not allow for the individual feature importance to be recognized.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*tNU3w-bE4wXY2N3q8ZklfA.png" /><figcaption>Never question the critic cat !!!</figcaption></figure><h3>Graphical Justification</h3><p>Consider a distribution of data in two dimensions as given below -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*tkxMD0go9Tw9mm08LGDsDQ.gif" /><figcaption>Random distribution of data</figcaption></figure><p>Let’s consider that x and y in this distribution are correlated. Then a new property can be constructed by drawing a line through the center of the distribution.</p><p>This new property will be given by a linear combination 𝓌₁x + 𝓌₂y where each line corresponds to some value of 𝓌₁ and 𝓌₂.</p><p>The reconstruction error is defined as the average mean-squared distance between the original white dots and their projections (yellow dots) onto the principal components.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*-Ri2rnDeXwovwu3tpTzaFw.gif" /><figcaption>See how the reconstruction error varies.</figcaption></figure><p>Observe that the spread (variance) of the yellow projected dots reaches the maximum when the black rotating line lines up parallel to the direction marked by the pc1 vector. Also, at the same instant, the reconstruction error reaches its minimum. Hence we can interpret that “the maximum variance” and “the minimum reconstruction error” are achieved at the same time.</p><h4>Note</h4><p>In Linear Regression, the mean squared error which we reduce comes from the vertical projection of a point onto the line. Meanwhile, in PCA, the mean squared error comes from projecting the point perpendicularly onto the line, as indicated in the above figure.</p><h3>Mathematical Justification</h3><h4>Covariance</h4><p>Covariance is a measure of the extent to which corresponding elements from two sets of ordered data move in the same direction. We use the following formula to compute covariance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/344/1*sgw7qTWjhCUxOUUjtVwFrQ.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/566/1*HlCer9e7gjOX0GJZYK3pDw.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*Wp1i9SOgH88cMPrSd6f46Q.gif" /></figure><h4>Covariance Matrix</h4><p>Variance and covariance are often displayed together in a variance-covariance matrix, (aka, a covariance matrix). The variances appear along the diagonal, and covariances appear in the off-diagonal elements, as shown below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/405/1*hijlThHL3x6SgpNsf3c1OQ.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/523/1*9G28y_K7x0KTcSPGUFMsMQ.jpeg" /></figure><h4>Proof</h4><p>For simplicity purposes, we can assume that the data has been “centered” so that every variable has mean zero. Hence if we write the centered data in a matrix <strong>x</strong>, where rows are objects and columns are variables, and <strong>v </strong>is the covariance matrix, then -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/108/1*ftDPLBJHDvJsAFOVPPGcSQ.jpeg" /></figure><p>Consider we have p-dimensional vectors, and we want to project them on to a line through the origin. The mean of the projections will be zero because the mean of the vectors is zero:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/416/1*zCm8aga4Zfw_4R8focPy5Q.jpeg" /></figure><p>If we try to use our projected or image vectors instead of our original vectors, there will be some error. The difference is the error or residual of the projection given by the following expression -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*gQPXHvzwDT8k_EQ8dIO_4A.jpeg" /></figure><p>Since w is a unit vector, w·w = 1. Adding those residuals up across all the vectors gives -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/385/1*MRlJY3tHyX0ZklhiUUP2Ig.jpeg" /></figure><p>The first summation doesn’t depend on w and hence has no role in minimizing the mean squared residual. To make the MSE small, we can make the second sum big, i.e., we can maximize -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/157/1*6Oc_-Cy-zvgp3E7SMhO75w.jpeg" /></figure><p>which we can see is the sample mean of the square of the dot product of w and x. The mean of a square is always equal to the square of the mean plus the variance -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/442/1*K6vkLx-3klKEkkqRgHf_og.jpeg" /></figure><p>Since we’ve just seen that the mean of the projections is zero, minimizing the residual sum of squares turns out to be equivalent to maximizing the variance of the projections.</p><p>In general, we project onto multiple principal components. If those components are orthogonal and have k unit vectors, then the image of <strong>x</strong> is its projection into space spanned by these vectors. Hence this image of <strong>x</strong> can be represented by-</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/164/1*DmROU1zCsnrlNMlBAjGoZA.jpeg" /></figure><p>The mean of the projection on each component is still zero. If we go through the same algebra for the mean squared error, it turns out that the cross-terms between different components all cancel out, and we are left with trying to maximize the sum of the variances of the projections onto the components.</p><h3>Maximizing Variance</h3><p>To maximize the variance, we can do our algebra in matrix form, so that the calculations are not too tedious. If we stack our n data vectors into an <strong>x (</strong>n × p matrix<strong>) </strong>and the weight matrix is <strong>w (</strong>p x 1 matrix<strong>), </strong>then the projections are given by <strong>xw</strong> (n ×1 matrix). The variance is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/248/1*rI7P0-coZziCte3vAZu6kQ.jpeg" /></figure><p>We need to choose a unit vector w so as to maximize the variance. To do this, we need to make sure that we only look at the unit vector that is we need to constrain the maximization. The constraint is that the square of the modulus of the vector w should be equal to 1. This can be done by introducing a new variable, the Lagrange multiplier λ. Adding λ times the constraint equation to our objective function, and then doing an unconstrained optimization allows us to maximize the variance taking into account the constraint. For our projection problem -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/331/1*UCRg-gnizjSP4xmbsUommQ.jpeg" /></figure><p>Setting the derivatives to zero at the optimum, we get -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/176/1*Jd74N4ytrb1PVh6mVywl3A.jpeg" /></figure><p>Thus, desired vector <strong>w</strong> is an eigenvector of the covariance matrix <strong>v</strong>, and the maximizing vector will be the one associated with the largest eigenvalue <strong>λ</strong></p><p>We know that the covariance matrix <strong>v</strong> is a p × p matrix, so -</p><ul><li>It will have p different eigenvectors.</li><li>It is symmetric, and hence the eigenvectors are orthogonal to one another.</li></ul><h3>Projecting onto a lower dimension</h3><p>The eigenvectors of v are the principal components of the data. Since they are all orthogonal to each other, so together they span the whole p-dimensional space.</p><p>The first principal component, i.e., the eigenvector, which corresponds to the largest value of λ, is the direction along which the data have the most variance. The second principal component, i.e., the second eigenvector, is the direction orthogonal to the first component with the most variance. Because it is orthogonal to the first eigenvector, their projections will be uncorrelated. In fact, projections on to all the principal components are uncorrelated with each other.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*pmxiIJ-KY8DTFYM-9L02SQ.gif" /><figcaption>computing Covariance</figcaption></figure><p>If we need to use q principal components, we sort the eigenvectors by decreasing eigenvalues and choose q eigenvectors with the largest eigenvalues to form a p × q dimensional matrix <strong>w</strong> where each column will be a different eigenvector (p x 1) of the covariance matrix v.</p><p>Using this weight matrix <strong>w </strong>(p x q), we can project our <strong>x</strong> matrix<strong> </strong>(n x p) into lower dimensions <strong>xw </strong>(n x q), essentially reducing the dimensions of data.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*-e0Fl9pEeBZVp1ohr-QGbQ.gif" /><figcaption>Projecting onto lower dimensions</figcaption></figure><h3>Applications of PCA</h3><h4>Image Compression</h4><p>Image compression with principal component analysis is a frequently occurring application of the dimension reduction technique. Thus, principal component analysis can be used to reduce the dimensions of the matrix (image) and project those new dimensions to reform the image that retains its qualities but is smaller in k-weight.</p><p>As the number of principal components used to project the new data increases, the quality and representation compared to the original image improve.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1022/1*MxcKNbnjAotLhhrJowASYg.png" /><figcaption>Recovering compressed images</figcaption></figure><h4>Reducing Redundancies in data</h4><p>Sometimes people gather tons of data with 20, 30, or more variables. They may think that they’re measuring 20 or 30 things, but they may be measuring fewer underlying factors (often called “latent traits”) than the number of measurements. Now, what happens when you have large amounts of features or if you keep on increasing the number of features in your data? A phenomenon known as the Curse Of Dimensionality begins to occur.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*nDIElQ6qtwfkV5NmZzo5UQ.png" /><figcaption>So many dimensions !!</figcaption></figure><p>The gist is that the more features that you have, the more complicated your numerical computations become. This means that the performance of the machine learning algorithms, which are mathematical computations on the data, will be affected. Each added variable results in an exponential decrease in predictive power.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/510/1*vah8IolNqlxNHq9ysVzYkw.png" /><figcaption>performance drops with a rise in features</figcaption></figure><p>Principal components are used to separate these essential underlying factors. When you run a PCA, you’ll see a component that points in the direction that accounts for the most variation in the n-variable space. The second component finds the next direction, perpendicular to the first, that has the second most variation. And so on for as many variables you have. Having n variables means that we have n components, but it’s likely that the first few important ones will account for almost all the variation.</p><h3>References</h3><ul><li><a href="https://faculty.marshall.usc.edu/gareth-james/ISL/ISLR%20Seventh%20Printing.pdf"><em>An Introduction to Statistical Learning with Applications in R</em></a><em> </em>by Gareth M. James, Trevor Hastie, Daniela Witten, Robert Tibshirani</li><li><a href="http://diggerdnepr.ddns.net/wp-content/uploads/2019/02/python-machine-learning-2nd.pdf"><em>Python Machine Learning</em></a> by Sebastian Raschka</li><li><a href="http://www.stat.columbia.edu/~fwood/Teaching/w4315/Fall2009/pca.pdf">Principal Component Analysis</a> by Frank Wood</li><li><a href="https://ocw.mit.edu/courses/mathematics/18-650-statistics-for-applications-fall-2016/lecture-videos/lecture-19-video/">Principal Component Analysis</a> MIT OCW</li></ul><h3>Bonus</h3><p>For interactive visualization of Principal Components Analysis visit <a href="https://setosa.io/ev/principal-component-analysis/">here</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=82a7682323e6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/principal-components-analysis-82a7682323e6">Principal Component Analysis</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Singular Value Decomposition (SVD)]]></title>
            <link>https://medium.com/vlgiitr/eli5-singular-value-decomposition-svd-955c151f9907?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/955c151f9907</guid>
            <category><![CDATA[linear-algebra]]></category>
            <category><![CDATA[svd]]></category>
            <category><![CDATA[eli5]]></category>
            <category><![CDATA[machie-learning]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Kaaira Gupta]]></dc:creator>
            <pubDate>Mon, 25 May 2020 19:07:39 GMT</pubDate>
            <atom:updated>2020-05-25T19:34:38.594Z</atom:updated>
            <content:encoded><![CDATA[<p>In this article, in the quest of understanding SVD, we will first see what it is mathematically. Even if the mathematical portion seems overwhelming, I insist on reading further to understand its intuitive reasoning and see how SVD helps us in Data Science as well. The readers should have a basic understanding of eigenvalues and eigenvectors to understand the mathematical portion of this article thoroughly.</p><p>SVD is a matrix factorization method, i.e. it is a method to represent a matrix as a product of matrices. This representation is used in a wide range of applications, including compressing and data reduction. SVD makes these processes reasonably easy due to some exceptional properties of this decomposition. Let us take a look at them.</p><h3>Mathematics</h3><p>The mathematical representation of a “transformation” (I will get to it later) is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*q4gm6oZItY1wQuKFZ4VfWw@2x.jpeg" /></figure><p>where,</p><ul><li><strong>U</strong> is an m × m unitary matrix (left singular vector)</li><li><strong>S</strong> is an m × n diagonal matrix with non-negative real numbers.</li><li><strong>V</strong> is an n × n unitary matrix ( right singular vector)</li><li><strong><em>Vᵀ </em></strong>is the conjugate transpose of the n × n unitary matrix.</li><li>The diagonal values of <strong>S</strong> are known as “<a href="https://en.wikipedia.org/wiki/Singular_value">singular values</a>” of <strong>A</strong>.</li></ul><p>Let us understand a few terms used here:</p><ul><li><strong><em>Unitary Matrix</em></strong>: We can think of it as a “complex number” version of an orthogonal matrix, which is a square matrix whose columns and rows are orthonormal vectors.</li><li><strong><em>Diagonal Matrix</em></strong>: It is a matrix in which the entries outside the main diagonal are all zero.</li><li><strong><em>Conjugate Transpose</em></strong>: The conjugate transpose of a matrix interchanges the row and column index for each element.</li><li><strong><em>Singular Values</em></strong>: It denotes the square root of the eigenvalues of <strong>XXᵀ </strong>where <strong>X</strong> is a matrix.</li></ul><p>But none of it seems <em>understandable, </em>right?? It is just pure mathematics. We get no information about how we can visualize it and use this <em>mathematical</em> tool. So, let us now take a step towards it.</p><h3>Understanding SVD intuitively</h3><p>We know that a matrix is a <strong><em>transformation</em></strong> which <em>transforms</em> the input vectors. We can understand it by saying that it is a <strong><em>function</em></strong> that takes a vector as an input and gives another vector out. Hence it works as a <em>map</em> between them.</p><p>Now, say we have to transform a vector <strong>V</strong> (think of it as applying <em>function</em> <strong>A</strong> on <strong>V</strong>) in space. We can do it by ‘<em>rotating</em>’ it and ‘<em>scaling</em>’ it. Hence, to put it mathematically:</p><p><strong>AV</strong> = <strong>US </strong>(here, <strong>U</strong> and <strong>V</strong> are orthogonal, i.e., rotatory matrices)</p><p><strong>A</strong>= <strong>US<em>Vᵀ,</em></strong></p><p>This is because of the property of orthogonal matrices which says, ‘<em>An orthogonal matrix multiplied with its transpose is equal to the identity matrix’, i.e.,</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/770/0*wOD6eVfTz0yf-TGh.png" /></figure><p>Hence, we can decompose a transformation (here, <strong>A</strong>) into a scaling sandwiched between two rotations. Let us take a simple example to make it more intuitive.</p><p>Suppose a square has to be <em>transformed</em> (<strong>A</strong>) into a parallelogram. We can rotate clockwise by θ (<strong>U</strong>), scale the axes by different factors (<strong>S</strong>), then rotate counterclockwise again by θ (<strong><em>Vᵀ</em></strong>). And voila! We have a parallelogram!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MGt-3gACMB4bRKhXMRbOBw.gif" /></figure><p><strong>Note</strong>: Since the square had to be transformed into a “parallelogram” the angle θ is the same here, it is not always the case. They can be unique as well.</p><p>This is how we can imagine transformation on a vector:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EdIW9yMd2AzLILPomsevxw.gif" /><figcaption>Applying transformation <strong>A </strong>on a vector.</figcaption></figure><p>Now, if we decompose <strong>A</strong>, we will get something like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ht3wo2h1iYn2LZStI1OWdw.gif" /><figcaption>Decomposing the transformation (<strong>A</strong>) into <strong><em>U, S, and Vᵀ</em></strong></figcaption></figure><p>To sum it, the transformation can be broken down into a transcription from one coordinate system to another, dictated by the orthogonal columns of <strong>V</strong> and <strong>U</strong>, and a scaling dictated by the diagonal <strong>S</strong>.</p><p>Also, we see that if we multiply <strong>A</strong> and <strong>A<em>ᵀ</em></strong>, we get:</p><p><strong>AA<em>ᵀ</em></strong>= (<strong><em>USVᵀ)</em></strong>(<strong><em>VSᵀUᵀ)</em></strong></p><p>From the Orthogonal property of <strong>V</strong> (and <strong>U</strong>) we discussed above:</p><p><strong>AA<em>ᵀ</em></strong>=<em> </em><strong><em>U(SSᵀ)Uᵀ</em></strong></p><p>We ultimately get our usual representation of a matrix (here, <strong>AA<em>ᵀ</em></strong>)<strong><em> </em></strong>as a multiple of its Eigenvalues, <strong><em>SSᵀ </em></strong>(λ), and Eigenvector, <strong>U</strong>!<strong> </strong>Similarly, we can have <strong>A<em>ᵀ</em>A </strong>to represent in terms of <strong>V</strong>.</p><h3>Data science and SVD</h3><p>Whether we want to compress our images or prevent our data from over-fitting, we come across the need for dimensionality reduction many a time. SVD is a widely used method in data science for this very purpose. But so is <a href="https://en.wikipedia.org/wiki/Principal_component_analysis">PCA</a>, so what is the difference, or is there a relationship between both? Let us try to assess that with an example.</p><p>Suppose you have some observation that depends on a lot of variables, of which only certain combinations make a significant contribution to the observation. What PCA does is that it projects everything to those “strong” combinations (these are called the principal components). Now, to do that, we can:</p><ul><li>Use eigenvalue and eigenvector of the covariance matrix to calculate and rank the importance of features.</li><li>Use SVD on the covariance matrix to calculate and rank the importance of the features.</li></ul><p>Let us see the difference mathematically (<em>consider all the data preprocessed to have zero mean</em>) :</p><p>So, while performing PCA, we are required to compute the eigenvalues and eigenvectors of the covariance matrix, which is the product <br><strong>(XX<em>ᵀ)/</em></strong><em>(n-1)</em>, where <strong>X</strong> is the data matrix. Since the covariance matrix is symmetric, the matrix is diagonalizable, and the eigenvectors can be normalized such that they are orthonormal:</p><p><strong>(XX<em>ᵀ)/</em></strong><em>(n-1) =</em><strong><em> </em>(WDWᵀ)</strong>/ (n-1)</p><p>On the other hand, applying SVD to the data matrix <strong>X</strong> as follows:</p><p><strong>X </strong>= <strong>UΣ<em>Vᵀ</em></strong></p><p>and attempting to construct the covariance matrix from this decomposition gives:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/871/1*DWTkX_6RnXxBe2aZGO--qQ.png" /></figure><p>and since <strong>V</strong> is an orthogonal matrix (<strong><em>Vᵀ</em>V</strong>=<strong>I</strong>),</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/854/1*uI0L8w4sIfMzmWuo1dd6eg.png" /></figure><p>and the correspondence is easily seen. For example, the square roots of the eigenvalues of <strong>XX<em>ᵀ</em></strong> are the singular values of<strong> X</strong> (as mentioned earlier in the article).</p><p>But, why do we prefer to use the SVD to perform PCA over calculating it directly? This is because the formation of <strong>XX<em>ᵀ </em></strong>can cause a loss of precision, for example, if <strong>X</strong> is the matrix given below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/185/1*MLs0vdOJhmqvIIDMBLwvXQ.png" /></figure><p>where ϵ is a tiny number.</p><p>Here, some elements of <strong>XX<em>ᵀ </em></strong>will be of the order ϵ² will not be precise. Hence using SVD here would be beneficial.</p><p>Hence, SVD is used to reduce a rank R matrix to a rank K matrix, i.e., we can take a list of R unique vectors, and approximate them as a linear combination of K novel vectors to aid dimensionality reduction and make our lives easier!</p><p>If you want to explore more, you can read about some other matrix decomposition techniques as well such as LU decomposition, LU reduction, Cholesky decomposition, and QR decomposition.</p><p><strong>Bonus</strong>: Here is an interactive <a href="https://www.geogebra.org/m/mrey8VJX"><strong><em>tool</em></strong></a> for you to play around with and understand SVD better.</p><h3>References:</h3><ul><li><a href="https://www.youtube.com/watch?v=mBcLRGuAFUk"><em>Video Lecture</em></a> by Gilbert Strang.</li><li><a href="https://web.mit.edu/be.400/www/SVD/Singular_Value_Decomposition.htm"><em>MIT tutorial</em></a></li></ul><p><em>Thanks to </em><a href="https://medium.com/@aaryang01"><em>Aaryan Garg</em></a><em> for the animations.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=955c151f9907" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/eli5-singular-value-decomposition-svd-955c151f9907">Singular Value Decomposition (SVD)</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Support Vector Machines]]></title>
            <link>https://medium.com/vlgiitr/support-vector-machines-77babd8545bb?source=rss----e4bec4e4cc37---4</link>
            <guid isPermaLink="false">https://medium.com/p/77babd8545bb</guid>
            <category><![CDATA[classifier]]></category>
            <category><![CDATA[eli5]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[support-vector-machine]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Aaryan Garg]]></dc:creator>
            <pubDate>Thu, 14 May 2020 20:12:32 GMT</pubDate>
            <atom:updated>2020-05-15T10:34:56.842Z</atom:updated>
            <content:encoded><![CDATA[<p>You must be knowing a bit about Machine Learning Classifiers, right? The basic aim is to separate training examples belonging to different classes. For example, if we have the height and weight of people in general and we want our algorithm to distinguish children from adults, we would use the right combination of height and weight to map the age of a person, and predict according to that, right? Well, there are different ways to do this as well like, Logistic Regression, Naive-Bayes Classification, Decision Trees, K nearest neighbours, to name a few. What we are going to see in detail in this blog, is another one of these techniques, called a Support Vector Classifier. Fancy the name? Not too much, I guess. But, I promise you, you will, by the end of this blog.</p><p>Suppose a person puts balls of two different colours, pink and green on a table in front of you. He then gives you a stick to separate the two colours. You comply and put the stick in such a fashion:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*-98cGmNr4v53s3WWUuF3xQ.gif" /><figcaption>These balls represent two different classes and the stick represents the decision boundary</figcaption></figure><p>Then why don’t you? Because we want to separate them the best way possible. That is the difference between a binary logistic regressor and a support vector classifier. A logistic regressor just gives you a valid decision boundary, but a support vector classifier gives you the best decision boundary there is..or if you want to get a bit more technical, the <strong>optimal hyperplane</strong>. An optimal hyperplane is generally preferred because it gives low training error as well as low generalisation error.</p><p>However, what we really want to find out is, how can a support vector classifier know what is the optimal hyperplane? The answer is in simple math:</p><p>Let us consider the linearly separable examples mentioned above. What we want is to create the widest possible street between the two types of examples that does not touch or contain any point. So, when we choose our optimal hyperplane we choose the one among the set of hyperplanes which is the farthest from the closest data points.</p><p>Now, let our optimal hyperplane be at a distance of b from our origin, and let <strong>w</strong> be its normal vector, then for any point <strong>x </strong>on the plane, its distance from the origin along the normal <strong>w</strong>, must be equal to b, so the equation of the optimal hyperplane is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/177/1*h5Dt0ky90mZWio72eQpqqQ.png" /><figcaption>vector equation of the optimal hyperplane</figcaption></figure><p>Now, taking some margin ‘m’ and scaling it to 1 for simplicity, we get the equation of the support hyperplanes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/193/1*gGFbrhzeBywuVLEJITfHGA.png" /><figcaption>vector equation of the support hyperplane towards y = -1</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/180/1*qE_pjWzYMHMVCiWK0j3GNQ.png" /><figcaption>vector equation of the support hyperplane towards y = +1</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*hOf9h1u3ZQUHuPYuDLvPig.gif" /><figcaption>Support and the optimal hyperplanes</figcaption></figure><p>Now, let us have n training examples each having D dimensions, having labels of either y <em>= </em>1 or<em> </em>y = -1 class, and our examples are linearly separable. Also, to calculate the margin, we calculate the distance between the two support hyperplanes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/705/1*K1vdNYBDv8RNODwTY1cUIQ.png" /><figcaption>A bit of vector algebra leads to this result</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/450/1*MZgsDtmxqXHHDpLpqC18dg.png" /></figure><p>Now, to merge both our support hyperplane classification conditions, we multiply it by y of respective class. Thus, we want all our training examples to satisfy the unified condition:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/244/1*_gMb-2_ZuuwvT2SisADGZw.png" /><figcaption>The points obeying this constraint will lie in the exterior of the margin, that is outside the street</figcaption></figure><p>Now, we want to maximise the margin under the above constraint because <strong>maximum margin classification </strong>is characteristic of a Support Vector Classifier. Thus, we have reached an optimisation problem. But, we can’t use gradient descent to solve this, because this is a constrained optimisation problem and it is better to use <a href="https://en.wikipedia.org/wiki/Lagrange_multiplier">Lagrange’s multipliers</a> to find the optimal solution. We should transform this maximisation problem to a minimisation problem as maximising the margin is the same as minimising the squared <a href="https://machinelearningmastery.com/vector-norms-machine-learning/">L2 norm</a> of <strong>w</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/134/1*UbuG0voTB2GQFa9RI9-7Nw.png" /><figcaption>Squared L2 Norm was preferred over L1 because it is more stable.</figcaption></figure><p>So, our Lagrangian turns out to be :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/605/1*PWrDkxhTim5VVU2GhEtGnQ.png" /></figure><p>As you may have guessed, this was a <a href="https://en.wikipedia.org/wiki/Duality_(optimization)">primal optimisation problem</a>, and to transform this into a dual optimisation problem, we substitute the value of <strong>w </strong>back into the Lagrangian and then maximise it now, in order to obtain the value of λ. After doing some algebra, we obtain:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/304/1*payfx0dEvhl7G-FaySyiHg.png" /></figure><p>Hence, we calculated our Optimal Hyperplane for linearly separable classes. But, what if the person put a pink ball as such:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*YqtCcd5jN3dn88Hoo8XHMA.gif" /><figcaption>The yellow examples were misclassified due to the presence of an outlier.</figcaption></figure><p>As shown in the above animation, the presence of an outlier can change your decision boundary and result in misclassification of many examples as y = -1 despite them being closer to y = 1 or vice-versa. This is a drawback of Hard margin Classification described above ie. it is highly sensitive to outliers. To solve this, we require soft margin classification. In it, we allow some examples to be misclassified for the bias~variance trade-off.</p><p>Mathematically, we relax the constraint by introducing a new slack variable ξ. So, now the constraint is :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/349/1*ZsGk6F0po1fV9oiw9D4E-g.png" /></figure><p>And our Loss function looks like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/266/1*YphZe9u_Ct1KoSCTxRSYgA.png" /><figcaption>Here, C is a hyper-parameter.</figcaption></figure><p>Here, the role of C is much greater than one assumes at first. C is an approximate measure of how soft margin classifier an SVC is, ie. how many misclassifications are allowed. So, when C is increased, then our classifier is more liberal towards misclassifications. Now, when we merge the loss function and the constraint, we obtain an unconstrained loss function:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*_FTDVfE1M-Sfl8GH7Z8bDg.png" /></figure><p>Which awfully resembles <a href="https://en.wikipedia.org/wiki/Hinge_loss">Hinge Loss</a>. The weights can therefore, be easily calculated using Gradient Descent.</p><p>Now, what if under no circumstance can the classes be linearly separated without misclassifying a lot of examples?</p><p>In such cases, we project the feature space into a higher dimension feature space, such that the examples in that feature space are linearly separable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*tWvmE8FDt--msSIsGZSzXA.gif" /><figcaption>We increase the feature space from 2D to 3D by adding a third dimension Z, such that Z² = X² + Y²</figcaption></figure><p>In the above example, the feature space was projected from 2D to 3D, ie. (x,y) to (x,y,z). So, the green points, having larger Z, rose on the Z axis more than the pink points, as shown and thus a plane was able to separate the two classes. This is the fabled “Kernel Trick”. This trick makes a support vector classifier, a <strong>support vector machine</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5EskDwUVwHHk122zqLi0ZQ.jpeg" /></figure><p>The function that maps the lower dimensional feature space to the higher dimensional feature space is called the <strong>Kernel</strong>. There are many different types of Kernels which can be used depending on the requirement:</p><ol><li><a href="https://en.wikipedia.org/wiki/Radial_basis_function_kernel"><strong>Gaussian RBF Kernel</strong></a>:</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/367/1*yqOzuBJygvt06tCIt_ShXQ.png" /></figure><p>Gaussian Kernels are particularly good at plotting circles, spheres and hyper-spheres as decision boundaries. These are also, the preferred choice for plotting non-linear decision boundaries because most things follow gaussian distribution. See <a href="https://en.wikipedia.org/wiki/Central_limit_theorem">Central Limit Theorem</a> for more information, but they map into infinite dimensions, and that is considered by some as a disadvantage.</p><p>2.<strong> </strong><a href="https://en.wikipedia.org/wiki/Polynomial_kernel"><strong>Polynomial Kernel</strong></a><strong>:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/370/1*uTGha0TWGZ2hmeeUCEIgMw.png" /></figure><p>Polynomial Kernels are used in specific cases, when you know the degree of the decision boundary, because in those cases the polynomial kernel exploits its advantage of being finite-dimensioned over the likes of the Gaussian RBF kernel.</p><p>3.<strong> Laplace Kernel:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/309/1*byQJBc_K0La1tBH-hbzCgQ.png" /></figure><p>The Laplacian Kernels are used in Image Processing tasks in general, because the Laplacian of an image highlights regions of rapid intensity change and is therefore often used for edge detection. However it is very sensitive to noise, hence, the image is often smoothed using a <a href="https://homepages.inf.ed.ac.uk/rbf/HIPR2/gsmooth.htm">Gaussian Smoothing Filter</a>.</p><p>4. <strong>Sigmoid Kernel:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/382/1*_H58OO7NbVmIDBMB3yBjcQ.png" /></figure><p>It is interesting to note that a SVM model using a sigmoid kernel function is equivalent to a two-layer, perceptron neural network. This kernel is quite popular for support vector machines due to its origin from neural network theory.</p><h3>Interesting facts:</h3><ul><li>Since the closest examples help in building the marginal hyperplanes, they act as supports for the optimal hyperplane. If they are shifted, the optimal hyperplane itself will shift. Hence, their position vectors are called Support Vectors. Hence, the name for the algorithm. Fancy it now?</li><li><strong>RBF </strong>in the Gaussian RBF Kernel stands for Radial Basis Function and it allows for a normal Gaussian Kernel to apply on data in more than two dimensions.</li></ul><h3>References:</h3><ul><li><a href="https://faculty.marshall.usc.edu/gareth-james/ISL/ISLR%20Seventh%20Printing.pdf"><em>An Introduction to Statistical Learning with Applications in R</em></a><em> </em>by Gareth M. James, Trevor Hastie, Daniela Witten, Robert Tibshirani</li><li><a href="http://diggerdnepr.ddns.net/wp-content/uploads/2019/02/python-machine-learning-2nd.pdf"><em>Python Machine Learning</em></a> by Sebastian Raschka</li><li><a href="https://www.academia.edu/34757446/Neural_Networks_and_Learning_Machines_3rd_Edition"><em>Neural Networks and Learning Machines</em></a><em> </em>by Simon Haykin</li><li><a href="https://www.youtube.com/watch?v=_PwhiWxHK8o">MIT-OCW</a> by Patrick Winston</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=77babd8545bb" width="1" height="1" alt=""><hr><p><a href="https://medium.com/vlgiitr/support-vector-machines-77babd8545bb">Support Vector Machines</a> was originally published in <a href="https://medium.com/vlgiitr">Vision and Language Group</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>