<?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[Stories by Lorenzobattistela on Medium]]></title>
        <description><![CDATA[Stories by Lorenzobattistela on Medium]]></description>
        <link>https://medium.com/@lorenzowbattistela?source=rss-8c060d0910bf------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*uDgXE0Y6ZSYULJv-k8dVIQ.jpeg</url>
            <title>Stories by Lorenzobattistela on Medium</title>
            <link>https://medium.com/@lorenzowbattistela?source=rss-8c060d0910bf------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 18:28:47 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@lorenzowbattistela/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Type Theory 101]]></title>
            <link>https://medium.com/@lorenzowbattistela/type-theory-101-437df9e418c5?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/437df9e418c5</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sat, 03 Feb 2024 19:02:25 GMT</pubDate>
            <atom:updated>2024-02-03T19:02:25.846Z</atom:updated>
            <content:encoded><![CDATA[<p>A few months ago, I had contact with some really interesting open source projects. Compilers, languages, runtimes, mostly low level stuff I had little contact before. So I decided to dive in, and started studying. I ended up discovering a whole new world of theories, proofs and research.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*6oalImIsF2snUfSU" /><figcaption>Photo by <a href="https://unsplash.com/@swimstaralex?utm_source=medium&amp;utm_medium=referral">Alexander Sinn</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>But I felt I did not know the basics, the fundamentals of it — mainly because when trying to read an article, I even had trouble understanding the notation.</p><p>Have you ever seen something like this?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*BGJP6sjtNQB-t4p6JK-OJw.png" /></figure><p>It really seems complicated, but it is no monster. Let’s learn how to read this and what is type theory.</p><h3>A little bit of history</h3><p>We all know what a paradox is. Sometimes we hear some fun ones that make us think, such as the <a href="https://en.wikipedia.org/wiki/Twin_paradox">Twin Paradox.</a> What happens is that math is physics and math are sources of many paradoxes. One of them is Russell’s paradox, which is a set-theoretic paradox that shows that every set theory that contains an unrestricted comprehension principle leads to contradictions. Basically, for any property, there is a set of all and only the objects that have that property. Then we have a set R that is the set of all sets that are not member of themselves. If R is not a member of itself, then its definition entails that it is a member of itself. Otherwise, if it is a member of itself, then it is not a member of itself since this is the set of all the sets that are not members of themselves.</p><p>Well that is confusing, but read it slowly and understand the problem here.</p><p>Type theory was created with the goal of avoiding paradoxes in a math equation based on set theory and formal logic. After that, we had progress on type theory such as ramified type theory together with an axiom of reducibility.</p><p>We also have Alonzo Church into play with his Lambda Calculus — which is the most popular conjunction of type theory. Church demonstrated it as a foundation of mathematics — a higher-order logic.</p><p>In modern literature, type theory usually refers to a typed system based on lambda calculus. Influential systems worth mentioning is Martin-Lofs intuitionistic type theory and Thierry Coquands calculus of constructions.</p><h3>Introducing Type Theory</h3><p>As the name states, in type theory, the basic object of study is a type. I am sure you are familiar with some types. For example, natural number is a type, usually denoted nat . Integer is also a type. = is a type called the identity type.</p><p>Types can have terms (or terms can have types?). For example, 1 is a term of type nat , and we can declare it as 1 : nat . This is a type declaration. This may sound familiar if you have experience with statically typed programming languages like Rust.</p><p>We also have a special type called Type . As you may imagine, it is used to define the type of a type. So, for example, nat : Type is a valid declaration.</p><p>Type theory is a subject that grows along with more fields, (such as category theory and proof theory) and we can have multiple interpretations for types. Here are some of them:</p><ul><li>A type is a set, and a term is an element of this set</li><li>A type is a space, and a term is a point in this space</li><li>A type is a proposition, and a term is a proof of this proposition</li></ul><p>Let’s introduce judgements, and a new symbol: ⊢</p><p>How do we read the following judgement?</p><p>⊢ A : Type</p><p>We can read this as: A is of type Type. This is a simple judgement.</p><p>Another symbol is used to represent Context: Γ (Gamma).</p><p>Γ is a finite sequence of type declarations, aka context. Intuitively, this mean that the assumptions in the left-hand context imply the right-hand side.</p><p>Γ ⊢ A : Type</p><p>We read this as: Under context gamma, A is of type Type</p><p>What about the following?</p><p>Γ ⊢ A === B : Type</p><p>This triple equal sign stands for judgemental equality. In type theory, we can have multiple types of equality, and note that this is different from the = sign stated as identity. So, Under context Gamma, A is judgementally equal to B which has type Type.</p><h3>Function types</h3><p>Most modern type theories introduce function types. They are introduced with an arrow symbol, and are defined inductively. For example, if a and b are types, then a-&gt;b is the type of a function which takes a parameter of type a and returns a term of type b . Types of this form are also known as simple types.</p><p>Let’s walk through a simple example:</p><pre>// add: a function that takes two natural numbers and return one nat number<br>add : nat -&gt; (nat -&gt; nat)</pre><p>You may find weird the parentheses, since we’re all used with something like add(a : nat, b : nat) -&gt; : nat . What happens is that, strictly speaking, a simple type only allows for one input and one output, and this way, we could not receive two args in the way I wrote. Therefore, a better way to read this is: add is a function which takes a nat and returns another function of the form nat -&gt; nat . Note that the arrow is right associative.</p><p>Ok, but untill now Type theories seem pretty inofensive right? What can we do about it? What this has to do with the image in the beginning of the article?</p><p>Well, the power of type theories is in specifying how terms may be combined through inference rules. For example, for functions we have function application. If a is a term of type c -&gt; d and b is a term of type c , then the application of a to b , often written ( a b) has type d . Example:</p><pre>3 : nat<br>6 : nat<br>10 : nat<br><br>(add 3) : nat -&gt; nat // partial application 3 + x<br>((add 6) 3) : nat // 9<br>((add 10) ((add 3) 6)) : nat // results in (10 + (3 + 6)) = 19</pre><p>Note that function application is left associative.</p><h3>Computation</h3><p>Type theory has a built-in notation of computation. The following terms are different:</p><pre>1 + 5 : nat<br>3 + 3 : nat<br>0 + 6 : nat</pre><p>But as you can see, they all compute to 6 : nat . The concept of reduction / reduce to refer to computation. Example: 3 + 3 : nat reduces to 6 : nat and we can write this as: 3 + 3 : nat -&gt;&gt; 6 : nat . A term without any variables that cannot be reduced further is called a canonical term.</p><p>Terms that compute to the same term are equal. As I said before, equality is quite complex on type theory, and the equality we’re referring here is when two terms can be substituted for each other. For example:</p><pre>x : nat<br>x + (10 + 2) : nat<br>x + (5 + 7) : nat<br><br>x + (10 + 2) : nat -&gt;&gt; x + 12 : nat<br>x + (5 + 7) : nat -&gt;&gt; x + 12 : nat</pre><p>The terms above are judgementally equal.</p><p>OK, now that we discussed a little bit the basics, let’s try to develop a little bit more the function type (coming from lambda calculus). Let’s introduce it with a formal notation and then move forward to other types.</p><h3>Function Types -&gt; Lambda Calculus : A formal formation</h3><p>As discussed before, given two types A and B, there is a type A -&gt; B.</p><p>We can write the formation rule for function types as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/781/1*EqOrWgw_sqVCNgVBxwlC0w.png" /></figure><p>Remember that Γ stands for context. A formation rule, as its name states, gives us a way to form function types.</p><p>We can read this rule as: Under context Gamma, if A is of type Type and B is of type Type, then we have a function from type A to type B.</p><p>But besides that, we cannot do anything more yet. Here it comes the introduction rule:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/613/1*m8LOL5hVfWnPQkXhQF9tLg.png" /></figure><p>We can read this as: Under context gamma, assume x is of type A. If b is of type B, then we have a function of type A that goes to type B receiving b as an argument.</p><p>The introduction rule states that, to specify a term of A -&gt; B, it is sufficient to specify a term b : B for every x : A . To understand this rule, it is important to understand the lambda calculus representation of functions. So, for example: we can say that λx.λy.( x y ) is a lambda term that receives two arguments, x and y, and applies x to y. When we receive an x and y, we substitute them in the term: λx.λy ( x y ) negate 1 =&gt; ( negate 1 ).</p><p>That said, now we have terms of A -&gt; B but we have no rules to use them in a way. Now we need to introduce an <strong>elimination</strong> rule. The elimination rule for function type says that, given a function f : A -&gt; B and a term a : A we can form the term f(a) : B . Formally:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/741/1*Bg_T4x3qeCm4JjC16X-DqA.png" /></figure><p>But well, we have no way to compute that. We do not know how to compute that. So, we have a computation rule that tells us what happens when the elimination rule is applied to a result of the introduction rule (in this case, a new function type).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/852/1*dxjMneTdGp2830Y2VrrVpQ.png" /></figure><p>The notation b[a / x] : B is the term that we obtain from b by substituting a for every x . Therefore, we can read it as:</p><p>Under context gamma, assume x is of type A. if b is of type B and a of type A, we have a function that receives b as an argument and it is judgementally equal to the term where we substitute all occurrences of x in b for a.</p><p>To sum up, our rules state the following:</p><ul><li>For any type A and B, there is a type A -&gt; B called the function type. A term of A -&gt; B is called a function</li><li>Defining a function f : A -&gt; B is equivalent to defining a term f(x) : B for every x : A .</li></ul><p>And, as I said before, type theory has many interpretations. About functions we can say that:</p><ul><li>For sets, it is the set of functions from set A to set B.</li><li>For spaces, it is a space of function from A to B</li><li>For propositions, this represents A implies B since having a proof o A -&gt; B is equivalent to having a proof of B for every proof of A.</li></ul><p>In the next article of this type theory series, we will discuss more this rules and introduce new types. If you find any mistake or typo, feel free to comment, as I’m still pretty new to this subject as well. Thanks for reading!</p><h3>References</h3><ul><li><a href="https://en.wikipedia.org/wiki/Type_theory">Type theory - Wikipedia</a></li><li><a href="https://plato.stanford.edu/entries/type-theory/">Type Theory</a></li><li><a href="https://ncatlab.org/nlab/show/type+theory">nLab type theory</a></li><li><a href="https://en.wikipedia.org/wiki/History_of_type_theory">History of type theory - Wikipedia</a></li></ul><p>And papers in the reference of those :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=437df9e418c5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Compilers Unveiled: A Brief Introduction]]></title>
            <link>https://medium.com/@lorenzowbattistela/compilers-unveiled-a-brief-introduction-fa87ab5f3f3a?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/fa87ab5f3f3a</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sat, 02 Sep 2023 12:25:22 GMT</pubDate>
            <atom:updated>2023-09-02T12:25:22.706Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-ll4oHrnIKnNOgwv" /><figcaption>Photo by <a href="https://unsplash.com/@ffstop?utm_source=medium&amp;utm_medium=referral">Fotis Fotopoulos</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>“A compiler is a computer program that translates computer code written in one programming language into another language”.</p><p>The compiler is one component in a toolchain of programs that are used to create executable files from source code. In general, when a single compile command is called, a whole sequence of programs are invoked in the background. Let’s understand this process and how does a compiler work.</p><h3>Compilation Steps</h3><p>As stated before, the compiler itself is not the only “actor” when we are translating source code to executable code. Typically, we can divide this process in four steps:</p><ul><li>Preprocessing: it prepares the source code for the compiler proper. For example, in C and C++, this is translated to consuming all directives that start with the # symbol. An #include directive causes the preprocessor to open the named file an insert its content into the source code. On the other hand, a #define causes the preprocessor to substitute a value wherever a macro name is encountered. Note that this is very flexible on the language, and not all of them rely on a preprocessor.</li><li>Compiling: it properly consumes the clean output of the preprocessor. We’ll discuss compiler steps itself soon, but basically it scans an parse the source code, performs typechecking and other semantic routines, optimizations and then produces assembly language as output.</li><li>Assembling: the assembler consumes the output of the compiler, an produces object code. Object code can be described as “almost executable”, since it contains raw machine learning instructions in the form needed by the CPU. However, it does not know the final memory addresses in which it will be loaded, so it still contains some gaps.</li><li>Linking: the final step is done by the linker, which consumes one or more object files and library files and combines them into one complete executable program. It selects the final memory locations where each piece of code an data will be loaded and “links” them together by writing in the missing address information. For example, if our object file calls the malloc function, it does not know initially the address of the function. Then, a zero (empty) address will be left where the address must be used. Once the linker defines the memory location of malloc, it must go back and write in the address at every place where malloc is called.</li></ul><p>This the overview of how the compilation process works. For this article, we will see the compiling step deeper, since it can be split up into several stages.</p><p>Let’s think this up a little bit. If the compiler outputs assembly code and receives a preprocessed source code file in some programming language, how would you translate this? Well, the first obvious step is to read up the source file and form tokens. This is know as scanning.</p><h3>Scanning</h3><p>It is the process of identifying tokens from the raw text source code of a program. It has to fit in tokens in many categories, like keywords, identifiers, numbers, comments, etc.</p><p>For example, this could be a simple C function to scan tokens:</p><pre>token_t scan_token( FILE *fp ) {<br> int c = fgetc(fp);<br> if(c==’*’) {<br>  return TOKEN_MULTIPLY;<br> } else if(c==’!’) {<br>  char d = fgetc(fp);<br>   if(d==’=’) {<br>    return TOKEN_NOT_EQUAL;<br>   } else {<br>  ungetc(d,fp);<br>  return TOKEN_NOT;<br>  }<br> } else if(isalpha(c)) {<br> do {<br>   char d = fgetc(fp);<br>  } while(isalnum(d));<br>  ungetc(d,fp);<br>  return TOKEN_IDENTIFIER;<br> } else if ( . . . ) {<br> . . .<br> }<br>}</pre><p>Note that the snippet is not complete since we haven’t defined those TOKEN_ identifiers, but the logic remains. We need to loop and keep identifying tokens, knowing that it can be part of a sequence. For example, if I identify a token “!”, it could be the not logical operator or a part of the “!=” sign, so the character which is not part of the sequence is put back. This process where an unexpected item doesn’t match the current objective and it must be put back for later is known as backtracking. When scanning a large number of tokens, it is common to use such things as <a href="https://en.wikipedia.org/wiki/Regular_expression">Regex</a> and <a href="https://en.wikipedia.org/wiki/Finite-state_machine">Finite Automata</a>. I will not get into detail about these topics here. In general, if you want to build a scanner, you can use something like <a href="https://www.cs.princeton.edu/~appel/modern/c/software/flex/flex.html">C Flex</a>.</p><p>A simple scanner example can be found here: <a href="https://github.com/Lorenzobattistela/compilers/tree/main/scanner">https://github.com/Lorenzobattistela/compilers/tree/main/scanner</a></p><h3>Parser</h3><p>Parsers are widely known in all tech fields. Let’s continue with our logic. We read the source file in plain text and grouped individual characters to form complete tokens. But this does not mean nothing at all yet. If I know I have “!=”, what could I do with it alone? Nothing. So the parser consume the tokens an groups them together into copmlete statements and expressions, much like words are grouped into sentences in a natural language. The parser is guided by a grammar which states the formal rules of composition in a given language. The output of a parser is an Abstract Syntax Tree that captures the grammatical structures of the program.</p><p>But of course, not every sequence of words make a valid sentence. Parsing a computer program involves describing the form of valid sentences in a language. This formal statement is known as Context Free Grammar (CFG). They allow recursion and can express richer set of structures. But a CFG is not easy to parse, because it can contain ambiguities an other problems that make hard to write an automatic parser. Therefore, in general we consider two subsets of CFGs known as LL(1) and LR(1) grammars.</p><p>LL(1) grammars are CFGs that can be evaluate by considering only the current rule and next token in the input stream. Not all language structures can be expressed as LL(1) grammars.</p><p>LR(1) grammars are more general and powerful than LL(1), but more complex to parse.</p><p>For this article, I’ll only briefly describe the parts of a CFG, because the whole process of sentence deriving, resolving ambiguities and converting grammars can be quite complex (but maybe I’ll approach it in another article). In addition, typically a parser generator is used and the only reason for you to build a parser by hand is to study. (IMO).</p><h4><strong>Parts of a CFG</strong></h4><ul><li>Terminal: it is a discrete symbol that can appear in the language, otherwise known as a token (from scanners). Examples of terminals are keyword, operators and identifiers. We use lower-case letters to represent terminal.</li><li>Non-terminal: represents a structure that can occur in a language, but is not a literal symbol. Examples are declarations, statements and expressions. We use upper-case letters to represent them. (e.g P for program, S for statement, etc.)</li><li>Sentence: it is a valid sequence of terminals in a language, while a sentential form is a valid sequence of terminals and non-terminal. Greek symbols represent sentential forms.</li></ul><p>A CFG is a list of rules that formally describe allowable sentences in a language. The left-hand side of each rule is always a single non-terminal. The right-hand side of a rule is a sentential form that describes an allowable form of that terminal. For example, B -&gt; xXy indicates that non-terminal A represents a terminal x followed by a non-terminal X and terminal y.</p><p>The parsing processing returns an AST, which is a representation of abstract synctatic structure of text written in a formal language. Each noe of the tree denotes a construct occurring in the text. Ex:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3LudKdkqA9nvV_EKQflkww.jpeg" /><figcaption>By Dcoetzee — Own work, CC0, <a href="https://commons.wikimedia.org/w/index.php?curid=14676451">https://commons.wikimedia.org/w/index.php?curid=14676451</a></figcaption></figure><p>In the parsing process, we have semantic routines that traverse the AST and derive additional meaning (semantics) about the program from the rules of the language an the relationship between elements of the program. For example, suppose this AST:</p><pre>x = 5<br>y = 10<br>z = x + y * 2</pre><pre>   =<br>  / \<br> x   +<br>    / \<br>   y   *<br>      / \<br>     10  2</pre><p>And that we have the rule:</p><p>1: Variables must be declare before use.</p><p>The semantic routine would ensure that ‘x’, ‘y’ and ‘z’ have been declared before use.</p><h4>Type checking</h4><p>After the parser has successfully grouped tokens into complete statements and expressions and created an Abstract Syntax Tree (AST), the next crucial step in the compilation process is type checking. Type checking ensures that the program adheres to the language’s type system rules, verifying that operations are performed on compatible data types and that variables are used in a manner consistent with their declared types.</p><p>The type checking process traverses the AST, examining expressions and statements to confirm their semantic correctness. Type theory can get quite complex, so I recommen reding some stuff about it. <a href="https://en.wikipedia.org/wiki/Type_theory">https://en.wikipedia.org/wiki/Type_theory</a></p><p>Failure to pass the type checking phase results in compilation errors or warnings, indicating the specific issues that need to be addressed by the programmer. This phase plays a crucial role in ensuring the reliability and correctness of the generated code.</p><p>Once type checking is successfully completed, the compiler proceeds to generate an intermediate representation (IR) of the program, which captures the essential semantics and type information. This IR forms the basis for subsequent optimization and code generation stages.</p><h4>Intermediate Representation Generation</h4><p>The generation of the Intermediate Representation (IR) occurs immediately after parsing. During this stage, the compiler takes the AST and transforms it into a more abstract, language-independent representation that captures the essential semantics of the program. The IR represents the program’s logic and data flow in a way that is easier to optimize and translate into machine code. This transformation simplifies further analysis and optimizations.</p><p>The IR generation stage may involve converting the AST into a series of intermediate code instructions or data structures that can be easily manipulated and analyzed by subsequent compiler stages. The specific form of the IR can vary depending on the design of the compiler.</p><h4>Optimization</h4><p>Once we have the IR generated, one or more optimization stages can be applied to improve the program’s performance efficiency. These optimizations operate on the intermediate representation rather than the original source code because the IR is a more structured and abstract representation of the program, making it easier to analyze and optimize. This is another subject that I won’t get much into detail, since I plan to write some articles just on it. But if you want to look up, some common optimizations include dead code elimination, constant folding and loop unrolling.</p><h4>Code generator</h4><p>Finally, a code generator consumes the optimized IR we got and transforms it into a concrete assembly language program. Typically, a code generator must perform register allocation to effectively manage the limited number of hardware registers, and instruction selection and sequencing to order assembly instructions in the most efficient form.</p><h4>Conclusion</h4><p>Well, understanding how a compiler works is really interesting and the basis is quite cool. Building a compiler is also a nice side-project (and something i’m working on too). I plan to write more articles in this subject and go deeper into some subjects like type checking and finite automata.</p><h4>References</h4><ul><li><a href="https://en.wikipedia.org/wiki/Compiler">Compiler - Wikipedia</a></li><li><a href="https://www.cs.princeton.edu/~appel/modern/c/software/flex/flex.html">Flex - a scanner generator</a></li><li><a href="https://en.wikipedia.org/wiki/Type_theory">Type theory - Wikipedia</a></li><li><a href="https://www3.nd.edu/~dthain/compilerbook/">Introduction to Compilers and Language Design</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fa87ab5f3f3a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Exploring Decision Trees]]></title>
            <link>https://medium.com/@lorenzowbattistela/exploring-decision-trees-9b5863c7ad30?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/9b5863c7ad30</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[decision-tree]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sun, 04 Jun 2023 11:52:26 GMT</pubDate>
            <atom:updated>2023-06-04T11:52:26.048Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0HpCz46hMCipTjK0" /><figcaption>Photo by <a href="https://unsplash.com/fr/@huchenme?utm_source=medium&amp;utm_medium=referral">Hu Chen</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Today we are going to understand and explore the concept of decision trees, an important and versatile algorithm, that can execute tasks such as classification, regression and even multi output tasks. The structure of a decision tree is widely known even outside of the AI world. I bet you’ve already seen this before:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/0*xPMgVQTYThFzSNDi.jpg" /><figcaption>[source]: <a href="https://en.wikipedia.org/wiki/File:Manual_decision_tree.jpg">https://en.wikipedia.org/wiki/File:Manual_decision_tree.jpg</a></figcaption></figure><p>This is a handcrafted decision tree. Let’s think about a decision tree that could be applied daily. Suppose you’re thinking about going to the beach tomorrow. The problem is that you don’t know how the weather will be. So, you may think that if it rains, you will not go to the beach. Otherwise, you’re going. This is a simple example of what a decision tree could be, but in fact, they work with probabilities — as the chance to rain or not.</p><h3>Predicting with Decision Trees</h3><p>Suppose we’re using the Iris dataset, a widely known classification dataset (<a href="https://www.kaggle.com/datasets/vikrishnan/iris-dataset">https://www.kaggle.com/datasets/vikrishnan/iris-dataset</a>). I previously implemented a decision tree classifier using<a href="https://scikit-learn.org/stable/modules/tree.html"> Scikit Learn</a>, and plotted the result of the tree. Let’s analyze it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/795/1*vLQyX-OVyXRWkls-cXJYxA.png" /></figure><p>We have an iris flower and want to classify it. We start with the root node, the first presented in the figure. This node asks the question “Is petal length less than or equal to 2.45 centimeters?”. If the answer is yes, so we go to the left child node of the root. In this case it is a leaf node (it has no child node), and therefore it does not ask any question. Hence, we can simply look at the class predicted in this node and we predicted that this flower is an Iris-setosa.</p><p>Now suppose that we find another flower, but this time the answer for the first question is no (false, petal length &gt; 2.45 centimeters). So, we have to move to the right child of the root node, which is not a leaf node (which means it asks a question). “Is the petal width less then or equal to 1.75 centimeter?”. If yes, then we go to the left child and the predicted class is versicolor. Otherwise, we go to the right child and predict Iris-virginica.</p><p>But what is this “gini” attribute showing there? The gini attribute of a node measures it’s “impurity”. A pure node (gini = 0) is a node where all training instances belong to the same class applied. For example, once the left child of the root applies only to training instances of Iris-setosa, it is pure and it’s score is 0. This is the equation to calculate the Gini coefficient for the <em>ith</em> node:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/224/1*hecCh0XUIDW4U7o24yf4Lw.png" /></figure><p>(Note that the k is squared, formatting got a little messy)</p><p>Where P<em>i,k</em> is the mean of instances of class k between training instances of node i.</p><p>Decision tree learning process can be described as a divide and conquer strategy, where it searches optimal split points within a tree. This splitting process is recursively done in a top-down manner until all (or most) of the records have been classified under specific labels.</p><h3>Pros and Cons</h3><p>As any algorithm, decision trees have advantages and disadvantages.</p><p>Decision trees are simple to interpret, and it’s easy to understand the process of decision after explanation.</p><p>Can be combined with other decision techniques (for example, is the base for Random Forest), it uses a white box model (system where it’s internals can be viewed but usually not altered).</p><p>But it also have disadvantages. For example, they are unstable, where a small change in data can change a lot the structure of the optimal decision tree. They can be relatively inaccurate, and calculations can get very complex, particularly if many values are uncertain.</p><h3>Optimizing a decision tree</h3><p>The process of optimization envolves lots of things, and we’re approaching some options. For example, we can increase the number of levels of the tree. The accuracy of a decision tree can change based on its depth, but this is a trade off, since the runtime can increase considerably and this is not always good, since it can also lead to overfit.</p><p>Choice of node-splitting function: there are some specific properties within different splitting functions. For example, a function named “phi” is the measure of “goodness” of a candidate split at a node in the decision tree, and “information gain” is known as a measure of the reduction in entropy.</p><h3>Evaluating</h3><p>Some of the most used metrics to evaluate a decision tree are:</p><ul><li>Accuracy: how close a given set of measurements is from their true value.</li><li>Sensitivity: how well a test can identify true positives</li><li>Specificity: how well a test can identify true negatives</li><li>Precision: how close measurements are from each other</li></ul><p>And derived measures from true positives, false positives true negatives and false negatives. We can also use a confusion matrix to display results.</p><h3>Conclusion</h3><p>Decision trees are widely known and used, really used for learning and to build other algorithms (such as random forest). It is really simple to understand and we can build it from scratch. I highly recommend reading the following article about induction of decision trees, because it clarifies a lot of the calculations and the history of decision trees. <a href="http://dept.cs.williams.edu/~andrea/cs374/Articles/Quinlan.pdf">[Article]</a></p><h3>References</h3><p><a href="http://dept.cs.williams.edu/~andrea/cs374/Articles/Quinlan.pdf">http://dept.cs.williams.edu/~andrea/cs374/Articles/Quinlan.pdf</a><br><a href="https://www.ibm.com/topics/decision-trees">https://www.ibm.com/topics/decision-trees</a><br><a href="https://en.wikipedia.org/wiki/Decision_tree">https://en.wikipedia.org/wiki/Decision_tree</a><br>Mãos à obra: Aprendizado de Máquina com Scikit-Learn &amp; Tensorflow — Aurélien Géron</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9b5863c7ad30" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Quantified Statements and Proofs: Building a Solid Foundation in Logical Reasoning]]></title>
            <link>https://medium.com/@lorenzowbattistela/quantified-statements-and-proofs-building-a-solid-foundation-in-logical-reasoning-76ed113a31bd?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/76ed113a31bd</guid>
            <category><![CDATA[discrete-mathematics]]></category>
            <category><![CDATA[logic]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sun, 28 May 2023 15:48:29 GMT</pubDate>
            <atom:updated>2023-05-28T15:48:29.295Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Fk3T1q81WVDUyBZm" /><figcaption>Photo by <a href="https://unsplash.com/@reubenteo?utm_source=medium&amp;utm_medium=referral">Reuben Teo</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Today we’re going to dive into Discrete Math by discussing quantified statements and approach mathematical proofs using algebra and discrete math. This article assume some understanding about discrete math notation, sets and logical reasoning, but nothing too complex.</p><h3>Quantified Statements</h3><p>At first, let’s quickly review what are quantified statements in discrete math. Consider the following statements: “all mathematicians wear hats”. How can we express this in math? We can use the ‘for all’ symbol like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/176/1*LF1STVOcSN4LeruBkr09vQ.png" /></figure><p>Where the A inverted represents ‘for all’, D is the set of mathematicians and Q(x) represent wearing hats. So, we can read that for all x in the set of mathematicians, x uses hat. Now, consider the statement: “there exists a mathematician that wear hats”. We can represent it using the exists statement:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/175/1*z2wmC7t8Dgop53N0it3Gow.png" /></figure><p>Where inverted E represents ‘exists’, D is the set of mathematicians and Q(x) represents wearing hats. Therefore, we can say that there exists some x in the set of mathematicians such that x wear hats.</p><p>And how we can negate the statements above? Simply negate the quantifier (exists turn into for all and vice-versa) and the function Q(x). So, negating the statements above would result in:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/237/1*D-Vp4YfinYZO6xXTaG4DMw.png" /></figure><p>So, in the first, there exists on mathematician that do not wear glasses. In the second, for all mathematicians, no mathematician wear hats.</p><p>Now that we reviewed quantifiers, let’s put up some work on arguments with quantified statements.</p><h3>Arguments with Quantified Statements</h3><p>Have you ever heard about the following argument?</p><p>All men are mortal.</p><p>Socrates is a man.</p><p>Therefore, Socrates is mortal.</p><p>The statement above is an example of a fundamental tool of deductive reasoning, called Universal Instantiation. It statest that if a property is true of everything in a set, then it is true of any particular thing in the set.</p><blockquote>Disclaimer: to say that an argument form is valid means that: No matter what particular predicates are substitute for the predicate symbols in its premises, if the resulting premise statements are all true then the conclusion is also true. An argument is called valid if, and only if its form is valid. It is called sound if and only if its form is valid and its premises are true.</blockquote><h4>Universal Modus Ponens</h4><p>Modus Ponens has the following form:</p><p>if P(x), then Q(x)</p><p>P(x)</p><p>Therefore, Q(x)</p><p>When we get this back to universal statements we can simply translate it to:</p><p>For all x, if P(x) then Q(x).</p><p>P(a) for a particular a. Therefore, Q(a).</p><p>We can simplify it for: all things that make P(x) true makes Q(x) true.</p><p>Let’s see the use of universal modus ponens in a proof. Consider the following: The sum of any two even integers is even. By definition of even, we know that an integer is even if and only if it equals twice some integer (or, for all integers x, x is even if and only if, it exists an integer k such that x = 2k).</p><p>So, suppose that <em>r</em> and <em>t</em> are two particular but arbitrarily chosen even integers. So, <em>r = 2m</em> for some integer <em>m</em>, and <em>t = 2s</em> for some integer <em>s. </em>Therefore, <em>r + t = 2m + 2s</em> . Now, we can factor out: = <em>2(m + s).</em> Thus, r + t is even.</p><h4>Universal Modus Tollens</h4><p>Modus Tollens has the following form:</p><p>If P(x), then Q(x)</p><p>Not Q(a) for a particular a</p><p>Therefore, Not P(a).</p><p>To transform this for universal statements, we can simply write this as:</p><p>For all x, if P(x) then Q(x)</p><p>Not Q(a) for a particular a, therefore, not P(a).</p><h4>Converse and Inverse errors on quantified form</h4><p>Consider the following: For all x in the set of people, if x is a mathematician then x is good at math.</p><p>For a particular person a, a is not a mathematician. Therefore a is not good at math.</p><p>This may seem a concise conclusion, but a conditional statement is not logically equivalent to its inverse. Remember that a condicional is only false when the premise is true but conclusion false. Thus, if someone is not a mathematician, it does not mean that this person is not good at math. This is called as the <strong>Inverse Error.</strong></p><p>Keeping the same argument of people being good at math, buit consider the following:</p><p>For a particular person b, b is good at math. Therefore, b is a mathematician.</p><p>Remember that the conditional can be true even if the premise is false, so we cannot assume that the premise is true knowing that the conclusion is true. This is called the <strong>Converse Error</strong>.</p><p>Many people make converse and inverse errors because the forms of the resulting arguments would be valid if the major premise were a biconditional rather than a simple conditional.</p><h3>Getting Proofs Started</h3><p>This is the first article about logical reasoning and Discrete Math, and as I continue my studies, I wanted to start the theme Proofs by saying that mathematical proofs seems to be too complicated, but in reality if we break it up in small steps, we can do it ourselves (unless you’re trying to proof the P vs NP problem). To show that, let’s proof a theorem!</p><p><strong>Theorem: </strong>For all integers <em>t</em> and <em>p</em>, if <em>t</em> is even and <em>p</em> is odd, then <em>3t + 2p</em> is even.</p><p><strong>Proof:</strong></p><p>Suppose <em>t </em>and <em>p</em> are any particular but arbitrarily chosen integers such that <em>t</em> is even and <em>p</em> is odd.</p><p>By definition of even and odd, <em>t = 2m </em>and <em>p = 2n + 1</em> . Then,</p><p><em>3t + 2p = 3(2m) + 2(2n + 1)</em> by substitution</p><p><em>3(2m) + 2(2n + 1) = 6m + 4n + 2 </em>by multiplying out</p><p><em>6m + 4n + 2 = 2(3m +2n + 1) </em>by factoring out 2</p><p>Let <em>s = 3m + 2n + 1</em></p><p>Therefore, <em>s</em> is an integer because <em>3, m, 2, n, 1</em> are integers and products and sums of integers are integers (closed operations).</p><p>Hence, <em>3t + 2p = 2s</em> where <em>s</em> is an integer, and by definition of even, <em>3t + 2p</em> is even as was to be shown.</p><h3>Conclusion</h3><p>Today we started discussing some themes around Discrete Math and Logical Reasoning, a subject that I particularly enjoy studying. Mathematics language can be scary to read, and so mathematical proofs. But in the end of the story, it is all about writing it in a way that other people can understand and contribute with it.</p><p>This article was written following the book “<em>Discrete Mathematics with Applications” by Susanna S.Epp.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=76ed113a31bd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Next steps on Linear Algebra]]></title>
            <link>https://medium.com/@lorenzowbattistela/next-steps-on-linear-algebra-1928878117c6?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/1928878117c6</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[learning]]></category>
            <category><![CDATA[linear-algebra]]></category>
            <category><![CDATA[education]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sun, 21 May 2023 19:13:24 GMT</pubDate>
            <atom:updated>2023-05-21T19:13:24.380Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*DCJYANh1FHREAqoG" /><figcaption>Photo by <a href="https://unsplash.com/@saadahmad_umn?utm_source=medium&amp;utm_medium=referral">Saad Ahmad</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>This article is the sequence of a my previous article<a href="https://medium.com/@lorenzowbattistela/the-beauty-of-linear-algebra-160de36b680a"> “The beauty of Linear Algebra”</a>, and I highly recommend reading it before this one, since we will use some concepts explained there. Today we’re going to reach the following topics: Null space, Non-square matrices as transformations, Dot products, eigenvalues and vectors and cross product.</p><h3>Null space (kernel)</h3><p>In math, the kernel of a linear map, also known as the null space is the linear subspace of the domain of the map which is mapped to the zero vector. Ok, this affirmation looks a little complicated, let’s break it through.</p><p>First, let’s recap what is the column space. The column space of a matrix A is the set of all possible linear combinations of its column vectors. So, imagine a matrix A = [1, 0, 2][0, 3, 0] (each [] is a column). Column vectors are v1 = [1, 0, 2] and v2 = [0, 3, 0]. A linear combination of v1 and v2 is any vector of the form c1 * [1, 0, 2] + c2 * [0, 3, 0] = [c1, 3c2, 2c1]. The set of all vectors with this form is the column space of A.</p><p>The null space of a matrix is the set of all vectors that when multiplied by the matrix, yields 0. This every x1, x2 and x3 that make the following equation true [1, 0, 2][0, 3, 0] * [x1, x2, x3] = [0, 0, 0].</p><h3>Non-square matrices as transformations between dimensions</h3><p>In the past article, we saw linear transformations using square matrices, but what happens if we use non-square matrices? We transform through dimensions. Suppose you have a matrix m <em>x</em> n where m is the number of rows and n the number of columns. This means that our matrix takes a vector of dimension n and transforms it in a vector of dimension m. If we have a matrix 3x3, our matrix will transform a 3 dimension vector in other 3 dimension vector. But if we have a 2x3 matrix, it will transform a 3 dimension vector in a 2 dimension one.</p><p>To understand this transformation, we can view each column of matrix A as a basis vector in the input space, and each row as a basis vector in the output space. When we multiply matrix A by a vector, the resulting vector is a linear combination of the column vectors of A, where the coefficients are determined by the entries of the input vector.</p><p>Let’s see this visually. Imagine a 2d vecto [2, 4] and we want to transform it to 1d plan. For this to happen, we need to use a 1x2 matrix. Consider the matrix A = [1, -2]. To apply the transformation, we multiply the vector by the matrix:</p><p>[1, 2] * [2, 4] = [2, -8] = [-6]</p><p>Our resulting vector is [-6], which represents a point on the 1D plane. Geometrically, our transformation maps from a 2d space to 1d space. The transformation specified by the matrix A stretches the x-coordinate by a factor of 1 and the y-coordinate by a factor of -2. Our matrix squeezes the points along the y-axis, resulting in a single point in a 1d line, it collapses one dimension.</p><h3>Dot Products</h3><p>The dot product concept is widely used on the computer science field, also in Machine Learning and Data Science. It is simply the multiplication of each element with the one whose at the same position and then add it. For example, for the matrices [1, 2] and [2, 4], the dot product is 1*2 + 2*4 = 10. It is widely used on Euclidean Geometry.</p><h3>Cross Product</h3><p>The cross product of two vector v X w is the area of the parallelogram formed by the copy of v and copy of w forming a parallelogram. In this context, signs represent orientation and the determinant gives the area of the parallelogram. You can find visual representations <a href="https://en.wikipedia.org/wiki/Cross_product">here.</a> If one of the vectors is scaled up, also is the area.</p><p>Cross products combine two 3d vectors to get a new 3d vector. First, we calculate the area of the parallelogram, that will be the length of our new vector, while the direction is perpendicualr to the parallelogram. We use the right hand rule to discover what perpendicular to use (conforming with sign). Right hand rule represented <a href="https://en.wikipedia.org/wiki/Cross_product#/media/File:Right_hand_rule_cross_product.svg">here.</a> The cross product formula is defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/177/0*EngxPaAmKi0jIQLl" /></figure><p>Where theta is the angle between a and b in the plane, ||a|| and ||b|| are the magnitudes of vectors a and b and n is a unit vector perpendicular to the plane containing our vectors with direction such the ordered set (a, b, n) is positively-oriented.</p><p>Geometrically, the cross product carries intepretations referring to Orthogonality (the resulting vector is orthogonal to both of the original vectors, and it lies perpendicular to the plane containing them), Magnitude (the magnitude of cross product vector is the area of the parallelogram formed), Direction (determined by the right-hand rule) and Permutation (because cross product is not commutative, changing order of vectors change the direction of the resulting cross product vector). It is only defined in three dimensions.</p><h3>Eigenvectors and Eigenvalues</h3><p>Simply said, the eigenvectors of a transformation are vectors that are not knocked off their span on a linear transformation. They remain in their span and are scaled by some factor. The factor by which they were scaled is called the eigenvalue. The sign also gives the orientation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/81/0*sbHLJ7fryIERcsoC" /></figure><p>The formal definition says that if we have a transformation matrix T and apply it to a vector v, it is the same that multiply v by a scalar and the effect would be the same. 2d transformations do not necessarily have eigenvectors. But why are they useful?</p><p>Eigenvectors and values are widely used in many fields, such as Principal Component Analysis (identifying the most important patterns and structures in high dimensional data by finding eigenvectors and eigenvalues of the covariance matrix), Image Compression and Processing, Markov Chain and Graph Theory, Quantum Mechanics (where quantum states are represented by eigenvectors. The Schrodinger equation is an eigenvalue equation) and much more.</p><h3>Conclusion</h3><p>We can see that Linear Algebra is a widely used field, and we can dive deep in many many contents. In this article, we learned new concepts after the basic ones in Linear Algebra, and found out what are the next steps in this field of study. See you next Sunday,</p><p>Lorenzo</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1928878117c6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Guide on Probability Distributions]]></title>
            <link>https://medium.com/@lorenzowbattistela/a-guide-on-probability-distributions-6546cc8263ef?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/6546cc8263ef</guid>
            <category><![CDATA[study]]></category>
            <category><![CDATA[probability]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[probability-distributions]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sun, 14 May 2023 10:40:38 GMT</pubDate>
            <atom:updated>2023-05-14T10:40:38.381Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*pknP42x6pzr6cw_r" /><figcaption>Photo by <a href="https://unsplash.com/@edge2edgemedia?utm_source=medium&amp;utm_medium=referral">Edge2Edge Media</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Today we’re going to introduce a statistics subject here. I recently started studying statistics and got into distributions, so we’re going to pass through some of them and explain what they are and do.</p><p>Let’s start by understanding what is a distribution. In probability, a distribution is the possible values a variable can take and how frequently they occur. More formally, the mathematical function that gives the probabilities of occurence of different possible outcomes for an experiment.</p><p>We will define Y as the outcome of an event, an <em>y</em> as a possible outcome. And P(<em>y</em>) is the probability function. We can define distributions using some other concepts:</p><ul><li>Mean: the average value (we represent it using the greek letter Mu)</li><li>Variance: how spread out the data is, how far it is from the mean (represented by Sigma)</li><li>Sample mean and sample variance, which refers to this measures on sample data</li><li>Standard deviation</li></ul><h3>Types of Probability Distributions</h3><p>Here we’re going to divide distributions into discrete and continuous. A discrete distribution models a variable that can only take on a finite or countably infinite number of values. On the other hand, a continuous distribution models a variable that can take on any value in a certain range or interval. Here we’re going to talk briefly about this seven distributions (although there are more).</p><h4>Discrete Distributions</h4><ul><li>Uniform</li><li>Bernoulli</li><li>Binomial</li><li>Poisson</li></ul><h4>Continuous Distributions</h4><ul><li>Normal</li><li>Student’s t</li><li>Chi-squared</li></ul><h3>Uniform Distributions</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/278/1*FV92L63CT2VQO_uu8A6rJg.png" /></figure><p>This means that X follows a discrete uniform distribution ranging from 3 to 7. In a uniform distribution, all outcomes have equal probability. One example is rolling a fair dice. This is the most common one, and in general we learn it in high school.</p><h3>Bernoulli Distribution</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/175/1*g1ccTrfEIJhd16WX1YHjQA.png" /></figure><p>X follows a Bernoulli discrete distribution. <em>p</em> represents the probability of success. In a bernoulli distribution, we have 1 trial and two possible outcomes. Usually, the value of <em>p </em>is known, or we have post data indicating some experimental probability. An example is an unfair coin, where we know that 70% of the times it will be heads and 30% tails.</p><p>E(heads) = 0.7</p><p>E(tails) = 0.3</p><p>Conventionally, 0.7 is <em>p</em> (following a rule that p &gt; 1 — p) and E(tails) is simply 1 — p. We can represent each result with 0 or 1. The expected value above represents the likelihood of the favored event. We can simplify the equation for the variance of a Bernoulli distribution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/1*dphtxawmrLz6RG_J_PWPXw.png" /></figure><h3>Binomial Distribution</h3><p>A Binomial distribution can be described as a sequence of identical Bernoulli distributions. An example would be flipping a fair coin 10 times and getting heads exactly 5 times.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/192/1*kc9OfOjjCptHI53IfHOI3w.png" /></figure><p>This means that X follows a binomial distribution where 10 is the number of trials and 0.6 is the probability of success in each one. The expected value of a binomial event is the number of times we expect to get a specific outcome. The probability function describes the likelihood of getting a given outcome a precise number of times.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/353/1*0kFy2m1vVAUao35AFi-Ifg.png" /></figure><p>The expected value (expected val for categorical values) is simply n * p, and then we can describe the variance as E(y²) — E(y)² , which is equal to n*p*(1-p).</p><h3>Poisson Distribution</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/260/1*eyOKyemzcbTG-oarzzNufQ.png" /></figure><p>A poisson dsitribution describes the frequency with which an event occurs. The graph of a poisson distribution plots the number of occurrences in a time interval, and it is described by the following function:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/201/1*rxG-O26myrD2nW8jQt5Lww.png" /></figure><p>A poisson distribution has the property that the mean is equal to the variance which is equal to lambda. The expected value of y is also equal to lambda.</p><h3>Normal Distribution</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/178/1*61VdVyZ0arZGZsKw4m4tKg.png" /></figure><p>A normal distribution is used to describe many natural phenomena. It is a continuous probability distribution that describes a symmetric, bell-shaped curve. The shape of the normal distribution is determined by its two parameters: the mean (μ) and the standard deviation (σ).</p><p>In a normal distribution, we have a law, described as 68%, 95%, 99%:</p><p>68% of all outcomes fall within 1 standard deviation away from the mean. 95% fall within 2 standard deviations away from the mean and 99.7% fall within 3 standard deviations.</p><h3>Student’s T distribution</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/111/1*kRKpfuUfjoQ8AvbXS0b0eA.png" /></figure><p><em>y</em> follows a Student’s T distribution where 3 (k) represents degrees of freedom. It is a small sample size approximation of a normal distribution. It is used for hypothesis testing with limited data.</p><p>If k &gt; 2:</p><p>E(y) = μ</p><p>Var(y) = S² * k / k — 2</p><h3>Chi-Squared Distribution</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/130/1*iy67tWZmPcq3pbUhxUmpOg.png" /></figure><p>Y follows a Chi-squared function where 3 represents K degrees of freedom. It is used also for hypothesis testing and computing confidence intervals. It measures the “goodness of fit”.</p><h3>Conclusion</h3><p>Today we passed quickly through some probability distributions to understand what they are and how to represent and use them. If you have any comments or corrections, feel free to comment below. The sequence of this probability series will cover Hypothesis testing and some other contents.</p><h3>References</h3><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fvideoseries%3Flist%3DPLaFfQroTgZnzbfK-Rie19FdV6diehETQy&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fplaylist%3Flist%3DPLaFfQroTgZnzbfK-Rie19FdV6diehETQy&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FCfZa1daLjwo%2Fhqdefault.jpg%3Fsqp%3D-oaymwEWCKgBEF5IWvKriqkDCQgBFQAAiEIYAQ%3D%3D%26rs%3DAOn4CLDogBO9pcxUFAXlLqPu-ujwEOaTFg%26days_since_epoch%3D19491&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="853" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/cd7216569efeecd33d380c60f36279a6/href">https://medium.com/media/cd7216569efeecd33d380c60f36279a6/href</a></iframe><ul><li><a href="https://en.wikipedia.org/wiki/Probability_distribution">Probability distribution - Wikipedia</a></li><li><a href="https://en.wikipedia.org/wiki/List_of_probability_distributions">List of probability distributions - Wikipedia</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6546cc8263ef" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An Overview on Lifted Structure Loss]]></title>
            <link>https://medium.com/@lorenzowbattistela/an-overview-on-lifted-structure-loss-d4c5db70be36?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/d4c5db70be36</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[tensorflow]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sun, 07 May 2023 15:03:08 GMT</pubDate>
            <atom:updated>2023-05-07T15:03:08.260Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*yrwb7STVDouC4XTe" /><figcaption>Photo by <a href="https://unsplash.com/de/@cdr6934?utm_source=medium&amp;utm_medium=referral">Chris Ried</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Today we’re going to discuss about Lifted Structure Loss, a deep metric used on computer visison and pattern recognition. The paper describing it is provided <a href="https://arxiv.org/abs/1511.06452">here.</a> But let’s start from the beggining.</p><h3>What is a loss function?</h3><p>Loss functions are used to determine the error between the output of an algorithm and the given target value. It expresses how far off the mark our computed output is.</p><p>In summary, a loss function maps an event or values of one or more variables onto a real number that represents some “cost” associated with the event. An optimization problem seeks the minimization of a loss function. In statistics, a loss function is used for parameter estimation. Loss functions are also used while training perceptrons and neural networks, since they influence how their weights are updated. Larger the loss, larger the update. When we minimize the loss, the model’s accuracy is maximized.</p><p>There are many types of losses, but today we’re going to focus on a specific one that I have been studying to contribute to<a href="https://github.com/tensorflow/similarity"> Tensorflow.</a></p><h3>Lifted Structure Loss</h3><p>The paper says that:</p><blockquote>In this paper, we describe an algorithm for taking full advantage of the training batches in the neural network training by lifting the vector of pairwise distances within the batch to the matrix of pairwise distances.</blockquote><p>But before understanding that this means, let’s understand the context of where this loss is used. The article describes the context as using lifted structure loss for embedding learning, where the goal is to learn a low-dimensional representation of the input data in a way that preserves the similarity relationship between the data points.</p><p>For example, we can use it on image analysis, and we should represent images in a way that the similarity between them is maintained. This means that 2 cat images should be embedded in a way that their representation is similar to each other, and a cat and a house should be very dissimilar. The Lifted Structure Loss function is designed to put similar data points closer together in the embedding space and push dissimilar points apart.</p><p>When we compare pairs of examples, it is crucial to measure similarity between pairs, since it reduces classification tasks to nearest neighbors problem after you have the similarity score.</p><blockquote>Tangent: embeddings are relatively low-dimensional space into we can translate high-dimensional vectors. (e.g, we represent the vector [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13] as [15, 4] maintaining its relations through some function). In summary it is a vector, and the distance between two vectors measure their relatedness.</blockquote><p>Lifted structure loss takes a set of input data points and their similarity labels as inputs. Then, it computes the pairwise similarity scores between data points in the embedding space using a similarity function (for example, cosine). After this, it operates on the similarity scores to minimize the distance between the embeddings of similar data points and maximize the distance between dissimilar points. This is done by computing the loss as the sum of the negative similarity scores between similar pairs and positive similarity score between dissimilar ones. Last, the loss is backpropagated through the neural network, and the embeddings are updated to minimize the loss.</p><p>The definition of the loss function per each batch is defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/511/1*UJQXXrIvtLOvzE49Ra_y4w.png" /></figure><p>and the backpropagation mentioned is defined in the article as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/439/1*VJlgMzZCJaaqLBUOvQ3c7w.png" /></figure><p>The backpropagation algorithm computes gradients of loss function with respect to the embeddings of the data points. These gradients are used to update embeddings through gradient descent.</p><h3>When to use Lifted Structure Loss?</h3><p>Let’s compare lifted structure loss with some other function, triplet loss. We don’t need to fully understand triplet loss, just know that it optimizes embeddings to satisfy a local constraint, which requires the distance between and anchor point and its positive example to be smaller than the one between the anchor and negative example.</p><p>Lifted Structure Loss performs better, in general, when there are many similar data points and we want to retrieve relevant data points from a large data set. This happens because it can learn a more meaningful embedding space (optimize embeddings to satisfy a global constraint), capturing better the similarity and relations between data points.</p><p>However, triplet loss wins when the task involves fine-grained classification, with few relevant data points for each class and the goal is to identify accurately those points.</p><p>This means that the choice highly depends on the specific task you want to perform, but Lifted Structure Loss proved to be very effective on large datasets and global choices.</p><h3>Open Source</h3><p>Although this article aims to explain Lifted Structure Loss function, the motivation behind it is Open Source. This week I started to pick up some open source projects and try to contribute. I picked up an Issue related to the implementation of Lifted Structure Loss on tensorflow/similarity repository. It is challenging to understand a codebase, a new algorithm and the math behind it, but after a few hours of reading and testing, it was amazing to understand what was happening in the experimental implementation.</p><p>The Issue I relate to is here: <a href="https://github.com/tensorflow/similarity/issues/102">https://github.com/tensorflow/similarity/issues/102</a></p><p>and it is work in progress, but I highly recommend learners to pick up some projects you like and use and try to contribute with them.</p><p>That was it for today, keep learning! When the implementation is merged, I’ll be back to tell how it was to contribute with tensorflow.</p><p>Lorenzo</p><h3>References:</h3><p><a href="https://arxiv.org/abs/1511.06452">arXiv:1511.06452</a> Deep Metric Learning via Lifted Structured Feature Embedding</p><ul><li><a href="https://en.wikipedia.org/wiki/Loss_function">Loss function - Wikipedia</a></li><li><a href="https://deepai.org/machine-learning-glossary-and-terms/loss-function">Loss Function</a></li><li><a href="https://www.tensorflow.org/addons/api_docs/python/tfa/losses/LiftedStructLoss">tfa.losses.LiftedStructLoss | TensorFlow Addons</a></li></ul><p><a href="https://developers.google.com/machine-learning/crash-course/embeddings/video-lecture">https://developers.google.com/machine-learning/crash-course/embeddings/video-lecture</a></p><p><a href="https://platform.openai.com/docs/guides/embeddings/what-are-embeddings">https://platform.openai.com/docs/guides/embeddings/what-are-embeddings</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d4c5db70be36" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Guide to Understanding Different Types of Regression Algorithms]]></title>
            <link>https://medium.com/@lorenzowbattistela/a-guide-to-understanding-different-types-of-regression-algorithms-19f4442cc233?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/19f4442cc233</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[regression]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sun, 23 Apr 2023 17:51:54 GMT</pubDate>
            <atom:updated>2023-04-23T17:51:54.473Z</atom:updated>
            <content:encoded><![CDATA[<p>Regression algorithms are widely used in the world of Data Science and Machine Learning. In my previous articles, I explained Linear and Multiple Linear regression. But that’s not all. To close the regression topic, today I’ll cover different types of regression algorithms, what they do and how to use them. Let’s dive in!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*1JrahDqQgVQ8lpZA" /><figcaption>Photo by <a href="https://unsplash.com/@lazycreekimages?utm_source=medium&amp;utm_medium=referral">Michael Dziedzic</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>As explained in my previous articles, a simple linear regression model makes a prediction by a ponderated sum of input features plus a constant called polarization term (or linear coefficient). Training a model means configure your parameters to be the best fit on the training set. For this to be done, we have to measure how good or bad the model is adapting to data. To train a linear regression model, we are finding the value that minimizes MSE (medium square error). The function can be described as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/638/1*vHcDfwFcZh5TwwGRrAsAjA.png" /></figure><p>To find the value of theta that minimizes the cost function, we can use the least squares method:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/336/1*xeFaXcbJlWmIkhDNtzkvZw.png" /></figure><p>Where theta is the vector that minimizes the cost function and y is the vector of target values from y1 ym. Let’s look closely to an example in python:</p><pre>import numpy as np<br>import matplotlib.pyplot as plt<br><br>X = 2* np.random.rand(100,1)<br>y = 4 + 3 * X + np.random.randn(100,1)<br><br>plt.scatter(X, y)<br>plt.xlabel(&#39;x&#39;)<br>plt.ylabel(&#39;y&#39;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/563/1*FWFEWDbt1sFwHNHFIZ7KEw.png" /><figcaption>generated data points</figcaption></figure><p>First, we generate our data points and plot them to see what they look like. The function we used to generate our data points is <em>y = 4 + 3x + gaussian noise .</em>Now, we’re going to apply the formula mentioned above to find the best theta value for our data points:</p><pre>X_b = np.c_[np.ones((100,1)), X] # adds x0 = 1 to each instance<br>theta_best = np.linalg.inv(X_b.T.dot(X_b)).dot(X_b.T).dot(y)<br>theta_best<br><br># array([[4.00634639], [2.94157425]])</pre><p>We can see that we did not get 4 and 3, which should be the result, but it was close enough (we didn’t get it exactly because of gaussian noise).</p><p>Let’s plot some prediction points as a line and understsand how our model fit training data:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/551/1*ikLUdCBBADqRLq8_3w4x_w.png" /></figure><p>We can see that our line fits data points pretty well for a simple linear model. The computational complexity for this is heavy (tipically O(n²) to O(n³) for inverting a matrix). The predictions are fast O(n).</p><h3>Polynomial Regression</h3><p>We can see that our data points were really simple in the previous model. But what if our data does not fit a simple straight line? Well, we can use a linear model to fit non-linear data. A simple way to do this is adding powers of each feature as new features, and train a linear model in this extended set of features. This technique is called Polynomial Regression.</p><p>We can do this using PolynomialFeatures from scikit learn library. For example:</p><pre>from sklearn.preprocessing import PolynomialFeatures<br><br>m = 100<br>X = 6 * np.random.rand(m, 1) - 3<br>y = 0.5 * X**2 + X + 2 + np.random.randn(m, 1)<br><br>poly_features = PolynomialFeatures(degree=2, include_bias=false)<br>X_poly = poly_features.fit_transform(X)<br>X_poly[0]<br><br># array([-0.752734872, 0.5666234])</pre><p>Using PolynomialFeatures allow us to add the square of each feature to the training model (in this case we have just one feature). Now, X_poly has the original feature X plus X squared. Note that when we have many features, Polynomial Regression is capable of finding relationships between them (something that a Linear Regression cannot do). This is possible because PolynomialFeatures also adds all combinations of features to the degree provided. This means if we had <em>a </em>and <em>b</em> with degree=3, we would have:</p><p><em>a², a³, b², b³, ab, a²b, ab²</em></p><h3>Ridge Regression</h3><p>Ridge regression is a regularized version of linear regression. In general, for linear models, regularization is done by restricting model weights. In Ridge, a regularization term is added to the cost function. The hyperparameter used controls how much you want to regularize the model. Closer to 1, weights will end up close to 0 and the line close to the average. The polarization term is not regularized. An easy way to execute a ridge regression is:</p><pre>from sklearn.linear_model import Ridge<br><br># assuming you already have X and y <br><br>ridge_reg = Ridge(alpha=1, solver=&quot;cholesky&quot;)<br>ridge_reg.fit(X, y)<br>ridge_reg.predict([[1.5]]) # predicting some value</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/426/1*f48K-08LdbgxB0OoZ7GOnA.png" /><figcaption>ridge regression equation</figcaption></figure><h3>Lasso Regression</h3><p>It is also a regularized version of linear regression, and it adds a regularization term to the cost functions, but it uses the norm <em>l1</em> to the weight instead of the half of the square of the norm <em>l2</em>. Lasso regression tends to eliminate completely the weights of features with less importance (adjust them to 0). It automatically executes feature selection and displays a sparse model (few feature weights != 0).</p><pre>from sklearn.linear_model import Lasso<br>lasso_reg = Lasso(alpha=0.1)<br>lasso_reg.fit(X, y)<br>lasso_reg.predict([[1.5]])<br><br># array([8.28714555])</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/430/1*gW7ZMFSpS2VDggbEnax0PA.png" /></figure><h3>Elastic Net</h3><p>It is a mid term between Ridge and Lasso. The regularization term is simply a mix of the regularization terms of Ridge and Lasso, and you can control the ‘mixing rate’ r. When r=0, Elastic Net is the same thing as Ridge, and r=1 it is equal to Lasso.</p><pre>from sklearn.linear_model import ElasticNet<br><br># l1 ratio l1_ratio is mixing tax<br>elastic_net = ElasticNet(alpha=0.1, l1_ratio=0.5)<br>elastic_net.fit(X,y)<br>elastic_net.predict([[1.5]])<br><br># array([8.18453219])</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/845/0*vHN9VV2qIO9KYfZi" /></figure><p>To choose between regression, we need to take some things in account. Generally speaking, it is not good to use linear regression without any regularization. Ridge is a good pattern, but if you can tell that some features are useless, you can choose between Lasso and Elastic Net, since they tend to reduce useless features to 0. In general, Elastic Net is preferable to Lasso, that can behave wrongly when feature number is higher than training instances number or highly correlated features.</p><h3>Logistic Regression</h3><p>Commonly used to estimate the probability of an instance belong to a determined category. It calculates the ponderated sum of input features and it generates the logistic of this result.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/584/0*XJDM4L7Aogevp-F7" /></figure><p>The cost relation with all training set is simply the average cost related to all training instances, and it is written in an expression called log loss:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/596/1*qJT9IpFUg5-qW7sJUeYkDA.png" /></figure><h3>Softmax Regression</h3><p>Logistic regression can be generalized for multiple classes directly without the need to train and combine many binary classifiers. This is called Softmax Regression, or Multinomial Logistic Regression.</p><p>Given an instance x, softmax model will calculated a punctuation sk(x) to each class k, and then estimate the probability for each class applying the softmax function (normalized exponential) to the punctuations. Once calculated, you can estimate the probability of Phat k of an instance to belong to the class k. It calculates the exponencial of each punctuation and normalizes it by dividing it by the sum of all exponentials.</p><h3>Conclusion</h3><p>Regression algorithms are used very often to study and to predict linear (and even non linear) data. Linear regression is the most common, but it is important to know that different cases require different algorithms. That said, it is important to know how other algorithms work, so you can pick the right one when needed! Thanks for reading it, see you next week!</p><p>— Lorenzo</p><h3>References:</h3><p>Mãos à Obra: Aprendizado de Máquina com Scikit-Learn &amp; TensorFlow — Aurélien Geron</p><ul><li><a href="https://en.wikipedia.org/wiki/Linear_regression">Linear regression - Wikipedia</a></li><li><a href="https://en.wikipedia.org/wiki/Logistic_regression">Logistic regression - Wikipedia</a></li></ul><p><a href="https://towardsdatascience.com/7-of-the-most-commonly-used-regression-algorithms-and-how-to-choose-the-right-one-fc3c8890f9e3">https://towardsdatascience.com/7-of-the-most-commonly-used-regression-algorithms-and-how-to-choose-the-right-one-fc3c8890f9e3</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=19f4442cc233" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Demystifying Taylor Series]]></title>
            <link>https://medium.com/@lorenzowbattistela/demystifying-taylor-series-78adcd59c95d?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/78adcd59c95d</guid>
            <category><![CDATA[calculus]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[education]]></category>
            <category><![CDATA[learning]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sun, 16 Apr 2023 14:49:29 GMT</pubDate>
            <atom:updated>2023-04-16T14:49:29.502Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>In mathematics, the <strong>Taylor series</strong> or <strong>Taylor expansion</strong> of a function is an infinite sum of terms that are expressed in terms of the function’s derivatives at a single point. <a href="https://en.wikipedia.org/wiki/Taylor_series">[Source]</a></blockquote><p>When I first read the definition above, I felt like I was reading greek (I don’t know greek, to be clear). The concept of an infinite sum of terms itself can be confusing, and what does it mean for this sum to be expressed in therm of the derivative of the function at a point? And for what this thing called Taylor Series is used? Let’s find out now!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ovfXGf8D3xWuEMLJ" /><figcaption>Photo by <a href="https://unsplash.com/@sharonmccutcheon?utm_source=medium&amp;utm_medium=referral">Alexander Grey</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Again, our goal here is to be conceptual, but the present article will make much more sense if you are already familiar with some calculus fundamentals. I highly recommend you reading my previous article on calculus [here](<a href="https://medium.com/@lorenzowbattistela/from-derivatives-to-integrals-a-journey-through-the-fundamental-theorem-of-calculus-a67302832407">https://medium.com/@lorenzowbattistela/from-derivatives-to-integrals-a-journey-through-the-fundamental-theorem-of-calculus-a67302832407</a>).</p><h3>Why the name Taylor Series?</h3><p>In math, series is a short name for infinite summation. Imagine that you want to add up all natural numbers. You would start by adding up 0 + 1 + 2 + 3 + 4 + 5… But when does this sum end? The answer is never. Natural numbers are infinite, sou you would continue to sum up numbers infinitely and never reach the end.</p><p>This problem was considered by an ancient Greek called Zeno of Elea. He thought that it was impossible to reach a finite result when summing an infinite series (here the word infinite is just for emphasize the fact that it is infinite), and created a paradox, named [The Achilles](<a href="https://iep.utm.edu/zenos-paradoxes/#SSH3ai">https://iep.utm.edu/zenos-paradoxes/#SSH3ai</a>). Imagine we have a man named Achilles, the fastest runner of antiquity, racing against a tortoise that is crawling away from him. They are running a linear path at constant speeds. To reach the tortoise, our runner needs to reach the place where the tortoise currently is. But when he reaches it, the tortoise crawled to another position, and so on forever. Zeno is assuming that space and time are infinitely divisible (continuous), not discrete or atomistic.</p><p>The mathematic point here is that divide our race into infinitely many sub-races that require a finite amount of time to catch the tortoise, thus it has a finite sum. If you are curious about the philosophy part here, I recommend [this read](<a href="https://gori70.medium.com/the-solution-of-the-paradox-of-achilles-and-the-tortoise-f618b23c25e">https://gori70.medium.com/the-solution-of-the-paradox-of-achilles-and-the-tortoise-f618b23c25e</a>).</p><p>It is the same principle of the following problem:</p><p>What happens when we sum 1/2 + 1/4 + 1/8 + 1/16 + … ? The answer is that the result is 1. We can visualize that thinking about a square of side 1. Then fill it in with the fractions above. You will see that the value converges to one, which means it fills the entire square.</p><p>Now that we understood the “Series” part of the name, it is worth mentioning that the “Taylor” part comes from [Brook Taylor](<a href="https://en.wikipedia.org/wiki/Brook_Taylor">https://en.wikipedia.org/wiki/Brook_Taylor</a>), who published the general method for constructing this type of series in 1715.</p><h3>Definition</h3><p>A basic explanation for Taylor Series is that we can approximate a function by a polinomial that closely matches the function’s behavior around a given point. Generally, given a function <em>f(x)</em>, and a point <em>a</em>, the Taylor Series for <em>f(x) </em>centered at <em>a</em> is given by:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/793/1*wEJdAPcFdgMJUuoCsaUENw.png" /></figure><p>where <em>f(a’)</em> is the derivative of <em>a</em> , <em>f(a’’)</em> is the second derivative of <em>a </em>(the second derivative would be the derivative of the derivative of <em>f(a)</em>, and so on), and the 2! means factorial of 2 (Ex: factorial of 3 is 3 * 2 * 1).</p><p>Let’s put this on a real function, let’s say <em>f(x) = sin(x)</em> . We will also take our first four Taylor polynomials:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/338/1*PZUt-qKZve2uor4swWzM8Q.png" /><figcaption>Built by me here: <a href="https://www.overleaf.com/read/byzqfhwmcvvt">https://www.overleaf.com/read/byzqfhwmcvvt</a></figcaption></figure><p>In the graph above, our center is 0. You can see that all the functions are centered at x = 0. Take a look at the blue line. Near <em>x = 0</em>, our function T1 is a straight line that approximates the behavior of the original function <em>f(x) = sin(x)</em>. The second-order polynomial is a quadratic function (green line), and it captures more of the curvature of our original function. As our N increases (the number of polynomials we take), the Taylor Polynomials get closer and closer to the original function. In fact, the Taylor Series (which is the infinite sum of all taylor polynomials) converges to the original function within a certain radius of convergence.</p><h3>Uses</h3><p>But overall, when are Taylor functions used? There are many applications for them, such as</p><ul><li>The partial sums (Taylor polynomials we discussed above) of the series can be used to approximate the function.</li><li>Approximations using the first few terms of a Taylor series can make problems that seem unsolvable possible for a restricted domain. (used a lot in physics)</li><li>Evaluating definite Integrals</li><li>Understanding asymptotic behavior</li><li>Determination of limits</li><li>A really important equation in complex analysis is defined in terms of Taylor series. See [here](<a href="https://math.stackexchange.com/questions/218421/what-are-the-practical-applications-of-the-taylor-series">https://math.stackexchange.com/questions/218421/what-are-the-practical-applications-of-the-taylor-series</a>)</li></ul><h3>Conclusion</h3><p>Made this article a little shorter, since I won’t cover some more advanced content (I intent to do this in the future, need to study a little bit more). Taylor series are really impressive if you’re used to high school math. The concept of infinite series is really interesting, and it causes discussions on the field of Physics, Mathematics and Philosophy. Taylor series are a powerful math tool, and it is worth learning it. I’ll leave many reference websites and sources that are worth reading. Thank’s for coming over today! See you next week.</p><h3>References</h3><ul><li><a href="https://math.stackexchange.com/questions/218421/what-are-the-practical-applications-of-the-taylor-series">https://math.stackexchange.com/questions/218421/what-are-the-practical-applications-of-the-taylor-series</a></li><li><a href="https://gori70.medium.com/the-solution-of-the-paradox-of-achilles-and-the-tortoise-f618b23c25e">https://gori70.medium.com/the-solution-of-the-paradox-of-achilles-and-the-tortoise-f618b23c25e</a></li><li><a href="https://iep.utm.edu/zenos-paradoxes/#SSH3ai">https://iep.utm.edu/zenos-paradoxes/#SSH3ai</a></li><li><a href="https://www.mathsisfun.com/algebra/infinite-series.html">https://www.mathsisfun.com/algebra/infinite-series.html</a></li><li><a href="https://en.wikipedia.org/wiki/Series_(mathematics)">https://en.wikipedia.org/wiki/Series_(mathematics)</a></li><li><a href="https://mathworld.wolfram.com/TaylorSeries.html">https://mathworld.wolfram.com/TaylorSeries.html</a></li><li><a href="https://en.wikipedia.org/wiki/Taylor_series">https://en.wikipedia.org/wiki/Taylor_series</a></li><li><a href="https://www.mathsisfun.com/algebra/taylor-series.html">https://www.mathsisfun.com/algebra/taylor-series.html</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=78adcd59c95d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[From Derivatives to Integrals: A Journey Through the Fundamental Theorem of Calculus]]></title>
            <link>https://medium.com/@lorenzowbattistela/from-derivatives-to-integrals-a-journey-through-the-fundamental-theorem-of-calculus-a67302832407?source=rss-8c060d0910bf------2</link>
            <guid isPermaLink="false">https://medium.com/p/a67302832407</guid>
            <category><![CDATA[math]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[calculus]]></category>
            <dc:creator><![CDATA[Lorenzobattistela]]></dc:creator>
            <pubDate>Sun, 02 Apr 2023 14:50:40 GMT</pubDate>
            <atom:updated>2023-04-02T14:52:08.002Z</atom:updated>
            <content:encoded><![CDATA[<p>Today we are walking through a subject that many people have fear of. I’m talking about calculus. Although hearing about derivatives and integrals may be a bit shocking at first, the reality is that it is simply amazing when you understand it. If you are not familiar with calculus or math, don’t worry, we will explain it all in a conceptual way.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*66AwKYaxA3hIgNV4" /><figcaption>Photo by <a href="https://unsplash.com/@jeswinthomas?utm_source=medium&amp;utm_medium=referral">Jeswin Thomas</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Let’s start thinking about a circle. We learned that the area of a circle is calculated using the formula <em>2 * PI * r </em>, where <em>r</em> is the radius of the circle. But where does this come from? Let’s divide our circle in many rings, like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*SpkfIrW7mo7KMEF5dRsyQA.png" /></figure><p>For this purpose, we will call the thickness of the ring <em>dr</em> . We can think of a ring as a coiled line. If we uncoil it, we will see that the figure is similar to a rectangle, so we approximate this ring to a rectangle. That said, our thickness would be the rectangle height, and <em>2 * PI * r </em>(the formula to the cirfumfere) is the rectangle width. So the area of our rectangle approximation is <em>2 * PI * r * dr</em>. But as <em>dr</em> becomes smaller (which means as we slice our circle in smaller and smaller rings), the approximation will become less and less wrong.</p><p>Note that we divided our circle in many rings, so it’s logical to conclude that the area of our circle is the sum of the area of all rings. A way to visualize this is to plot a graph from 0 to r, with columns that represent our rings.</p><p>If we choose smaller and smaller values for <em>dr</em>, the area of our rectangles keeps getting closer of the precise area under the graph. The portion under the graph is a triangle, whose base is 1, and height is <em>2 * PI</em> * 1<em> .</em> So the area, which is <em>(base * height) </em>/ 2<em> </em>comes out to be PI *1² . Or, if the radius of our original circle had been other value R, <em>area = 1/2 * R * 2 * PI * R = PI * R²</em></p><h3>Integrals</h3><p>Imagine we have the following graph for the function f(t) = t³:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/357/1*vYtIgaNUeLjeVuKfW7SaPw.png" /><figcaption>Graph of f(t) = t³</figcaption></figure><p>Now, we set the left endpoint at the origin (0), but let’s think that the right endpoint (that we will call x) varies. How can we describe the area under the graph of f(t) when we consider the variation of our endpoint x?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/774/1*azRN6S1q9EjMzRMQqx8TfQ.png" /></figure><p>We do it the following way:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/74/1*ncuGC62EVsGNikQKJOCPfA.png" /></figure><p>In mathematics, integral is a concept used to calculate the area under a curve or the total accumulated value of a function over an interval. Consider a linear function such as <em>f(x) = 2</em>. This function is represented graphically like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/909/1*ZjevfdktJMTtNk0JMs6tRw.png" /><figcaption>f(x) = 2</figcaption></figure><p>To calculate the area under our function, we simply calculate the area of the rectangle formed by the height of the function over that interval and the width of the interval itself.</p><p>However, we may deal with more complex functions, like polynomials. Imagine a function like the one below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/372/1*FoSYm0AKZfMnms8IzbnsBg.png" /><figcaption>Graph for polynomial function</figcaption></figure><p>In that case, it is impossible to calculate the area using simple geometry, like we did before. Instead, we use integration to approximate the area under the curve. Integration involves dividing the area under the curve into an infinite number of small rectangels, with an infinitelly small width and then summing up the area of all rectangles. The result is approximately the total area under the curve, like we represented using our circle rings. This is the foundation of the theory of integration.</p><h3>Derivatives</h3><p>Derivatives are usually defined as “instantaneous rate of change”, but think about this definition for a second. Things only change if we measure different points in time. Think about a moving car: what if I told you that our car is moving 60km per hour, and asked what is the velocity of our car at the instant <em>i?</em></p><p>You cannot measure how fast the car was at a single instant, because there is no room for change since we don’t have separate points in time. Velocity itself is the distance traveld over a given amount of time, so this is a paradox. But we have speedometers right? When you are driving, the car shows your speed at a given moment… or this is what it appears to happen. In reality, the car system is computing speed during <strong>very</strong> small amounts of time.</p><p>This means that if we choose a small amount of time <em>dt,</em> we can compute the rise over the run:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*Mwu1RL5VBtJmNcdu2AyYEQ.png" /></figure><p>The idea presented here is almost what a derivative is. Although a car will choose a small amount like 0.001 seconds to compute speed, in math, the derivative is not this ratio for a specific choice of <em>dt</em>. It’s whatever value this ratio <em>approaches</em> as the choice for <em>dt</em> approaches 0.</p><p>Another way to think about <em>ds/dt</em> is the slope of the line passing through two points on the graph. The derivative is equal to the slope of a line <em>tangent</em> to the graph at a single point.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/363/1*dyZvy2RJllo9Oa9TVqggOw.png" /><figcaption>Tangent line on the point A</figcaption></figure><p>For example, let’s think about a linear function, such as <em>f(x) = 2x + 2 .</em> Knowing the concept of derivatives, we can compute the derivative of our function easily. The graph for this function looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/723/1*LCKwJ4YooM1eW2KvU7ZfbA.png" /><figcaption>graph of f(x) = 2x + 2</figcaption></figure><p>It doesn’t matter the value of <em>x, </em>the slope of the line will always be 2 (because in linear equations of form <em>f(x) = ax + b</em>, a represents the linear coefficient that dictates the slope of the line. In our case, it its one). Derivatives of constant values, such as our <em>b</em> are 0, because there is no change in constant values. That said, the derivative of a linear function is it’s linear coefficient <em>a. </em>In our case, note that every time we increase X by 1 unit, the value of the function increases by 2 units, so the rate of change is always the same.</p><p>There are a lot of techniques to computing derivatives for other types of functions, such as power, exponential, logarithmic and so on. I will not cover those in this article since it is mostly conceptual.</p><blockquote>The formal definition of a derivative is that the derivative of <em>y</em> with respect to <em>x</em> is defined as the change in <em>y</em> over the change in <em>x</em> as the distance between <em>x0</em> and <em>x1</em> becomes smaller and smaller. <a href="https://simple.wikipedia.org/wiki/Derivative_(mathematics)">[source]</a></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/262/1*SP4rjL4bYyZN1WEtMajK0g.png" /></figure><p>This is the math definition of a derivative, which is the slope of the tangent line to the graph of f(x) in that point, it measures how quickly the value of f(x) changes with small changes in x.</p><h3>Fundamental Theorem of Calculus</h3><p>After all we’ve been through in this article, this is the time to stitch it all together and understand the relation between the slope of a curve and the area below it, the Fundamental Theorem of Calculus. It states that integration (integrals) and differentiation (derivatives) are inverse operations of each other.</p><p>It states that for a function <em>f</em> , an <em>antiderivative</em> may be obtained as the integral of <em>f</em> over an interval with a variable upper bound.</p><blockquote>Quick definition: antiderivatives (also known as indefinite integrals) of a function <em>f</em> is a differentiable function <em>F</em> whose derivative is equal to the original function <em>f</em>. (<em>F’ = f).</em></blockquote><p>Basically, if function<em> f(x)</em> is continuous over an interval <em>I</em>, and if <em>F(x)</em> is any antiderivative of <em>f(x)</em> over that interval <em>I</em>, then the indefinite integral of <em>f(x)</em> is <em>F(x)</em> + integration constant. In other words, integration undoes differentiation and restores the original function up to an arbitrary constant. This is what states that they are inverse operations of each other.</p><p>The theorem also states that the integral of <em>f</em> over a fixed interval is equal to the change of any antiderivative <em>F </em>between the ends of the interval. It simplifies the calculation of a definite integral.</p><p>Simply amazing.</p><p>Thanks for reading, see you next week!</p><p>Lorenzo</p><h3>References</h3><p><a href="https://www.geogebra.org/">https://www.geogebra.org/</a></p><p>Howard A, Irl C. B Bivens, Sephen L. Davis; et al. Cálculo.v1, 10th ed. Bookman, 2014.</p><ul><li><a href="https://www.3blue1brown.com/">3Blue1Brown</a></li><li><a href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_calculus">Fundamental theorem of calculus - Wikipedia</a></li><li><a href="https://en.wikipedia.org/wiki/Antiderivative">Antiderivative - Wikipedia</a></li></ul><p><a href="https://en.wikipedia.org/wiki/Derivative">https://en.wikipedia.org/wiki/Derivative</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a67302832407" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>