<?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 Anwar Hermuche on Medium]]></title>
        <description><![CDATA[Stories by Anwar Hermuche on Medium]]></description>
        <link>https://medium.com/@anwarhermuche?source=rss-f78a171df2f2------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*-ORQujSJwV3VZQtJ1lAPRw.png</url>
            <title>Stories by Anwar Hermuche on Medium</title>
            <link>https://medium.com/@anwarhermuche?source=rss-f78a171df2f2------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 01:46:46 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@anwarhermuche/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[O Nascimento em Massa dos Falsos Especialistas em Inteligência Artificial]]></title>
            <link>https://medium.com/@anwarhermuche/o-nascimento-em-massa-dos-falsos-especialistas-em-intelig%C3%AAncia-artificial-14c8a39f7256?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/14c8a39f7256</guid>
            <category><![CDATA[inteligencia-artificial]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Thu, 08 May 2025 00:42:51 GMT</pubDate>
            <atom:updated>2025-05-08T00:42:51.268Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/700/0*JL2__qf6of-lZ_lW" /></figure><p>Eu me lembro do primeiro dia em que escrevi meu próprio código para treinar um modelo. E digo meu próprio código porque nem ChatGPT tinha na época.</p><p>Errei. Errei de novo. Travei em uma linha por horas. Achei que fosse burro. Reli um paper cinco vezes. E, ainda assim, só compreendi de verdade quando tive que explicar o conteúdo para alguém. <strong>A técnica exige tempo, frustração, paciência, silêncio</strong>. É por isso que desconfio, cada vez mais, daqueles que se autodenominam “especialistas” da noite para o dia — e, mais ainda, dos que nunca erraram em público.</p><p>Vivemos uma nova corrida do ouro. A Inteligência Artificial tornou-se o El Dorado do século XXI — promessas de fortuna, status, reconhecimento e, principalmente, de relevância instantânea. <strong>Mas onde há ouro, há garimpeiros oportunistas</strong>. E na pressa por parecerem preparados, muitos escolheram vestir a fantasia de especialista em IA como quem compra um terno para um casamento: basta servir ao evento, não precisa durar além da noite.</p><blockquote>Essa epidemia de especialistas-relâmpago diz mais sobre a nossa cultura do que sobre a tecnologia em si.</blockquote><p>A modernidade passou a confundir aparência com essência.</p><p>Formatação com formação.</p><p>Domínio de ferramenta com domínio de conhecimento.</p><p>E é assim que o sujeito que descobriu o ChatGPT ontem já vende mentoria sobre “como usar a IA para criar um negócio em 7 dias”. Parece piada. Mas é só mais um post viral no LinkedIn.</p><h3>A era da competência encenada</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*w7utzpzwnWp5hhZB.jpg" /></figure><p>Nunca estivemos tão obcecados por saber superficial. Basta que alguém aprenda a dar um prompt que gere uma resposta bonitinha, e já se autoproclama “<strong>especialista em automações com IA</strong>”.</p><p>E o mercado, carente de discernimento técnico, aplaude.</p><p>Mas será que essa pessoa entende o que é um <em>token</em>? O que é <em>overfitting</em>? O que significa <em>fine-tuning</em> em um modelo autoregressivo? Como funciona a janela de atenção em um <em>transformer</em>?O que é LangChain ou LangGraph?</p><blockquote>Na maioria esmagadora das vezes, não.</blockquote><p>E não entender esses conceitos não seria um problema — ninguém é obrigado a saber tudo — <strong>mas é fundamental conhecer o limite da própria ignorância</strong>.</p><h3>A modernidade trocou o silêncio do saber pela pressa do engajamento</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/768/0*ozakEMuhaTOYJtVu" /></figure><p>Estudar exige tempo. Exige insatisfação. Exige paciência diante do próprio fracasso. E, acima de tudo, exige silêncio — <strong>o silêncio necessário para refletir, duvidar, conectar</strong>.</p><p>Mas esse silêncio se tornou insuportável para a alma viciada em likes.</p><p>E é por isso que esses falsos especialistas gritam. Gritam com thumbnails, com ganchos emocionais, com frases de efeito e promessas milagrosas. Gritam porque não têm tempo — ou coragem — para escutar.</p><blockquote>Chesterton dizia que o problema do homem moderno não é que ele perdeu a razão, mas que ele perdeu tudo, <strong>exceto a razão</strong>.</blockquote><p>Eu diria que o novo especialista em IA perdeu tudo — <strong>menos o desejo de ser visto</strong>.</p><blockquote>O problema não está apenas neles. Está em nós.</blockquote><p>O verdadeiro inimigo não é o falso especialista. É o ambiente que o recompensa.</p><p>É o empresário que contrata o mais barulhento, e não o mais preparado.</p><p>É o influenciador que divulga sem checar.</p><p>É o público que consome qualquer conteúdo que venha com estética de autoridade.</p><p>E, acima de tudo, é <strong>a pressa coletiva por resultados rápidos</strong>, mesmo que sejam frágeis, inseguros e insustentáveis.</p><p>Somos cúmplices. Porque, em algum nível, todos nós queremos acreditar que é simples. Que não precisamos estudar. Que não precisamos errar.</p><p>Que podemos vencer o jogo com um curso de 2 horas no YouTube.</p><h3>Mas há um outro caminho. O caminho do construtor.</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/728/0*GkmI3fJbeT0H_-GM.jpg" /></figure><p>O caminho de quem estuda. De quem erra. De quem passa noites refatorando código, soluções no N8N ou mergulhado em papers técnicos que não viralizam no Instagram.</p><p>Esse caminho não tem glamour imediato. Não tem aplausos instantâneos.</p><blockquote>Mas tem raiz. Tem lastro. Tem profundidade. E, sobretudo, <strong>tem verdade</strong>.</blockquote><p>Se você se sente deslocado nesse novo mercado — saturado de mentiras embaladas em carrosséis bonitos — saiba que você não está sozinho.</p><p>A sua inquietação é o sinal de que sua alma ainda reconhece o que é autêntico. Ainda busca sentido. Ainda não foi totalmente anestesiada pelo espetáculo.</p><blockquote>Em defesa do silêncio, da técnica e da integridade</blockquote><p>A Inteligência Artificial não é apenas uma moda. É uma das maiores transformações tecnológicas da história.</p><p>E como toda revolução, ela exige mais do que vendedores. Exige guardiões do conhecimento. Arquitetos e/ou engenheiros de verdade. Professores comprometidos com a formação, não com a performance.</p><p>A moda vai passar. O barulho vai cessar. E, quando tudo isso se acalmar, só restarão dois tipos de profissionais:</p><ul><li>os que realmente sabem…</li><li>e os que fingiram enquanto dava view.</li></ul><p>A pergunta que fica é: <strong>Em qual desses dois grupos você quer estar?</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=14c8a39f7256" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Apenas Três Questões]]></title>
            <link>https://medium.com/@anwarhermuche/apenas-tr%C3%AAs-quest%C3%B5es-eb2cce38a6f6?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/eb2cce38a6f6</guid>
            <category><![CDATA[vida]]></category>
            <category><![CDATA[inteligencia-artificial]]></category>
            <category><![CDATA[historia]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Fri, 13 Sep 2024 19:26:40 GMT</pubDate>
            <atom:updated>2024-09-13T19:26:40.243Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*B2xAmcJtjFoQrln0RXk9_Q.png" /><figcaption>Eu, em 2018, no primeiro ano do ensino médio</figcaption></figure><p>Tudo começou no primeiro ano do ensino médio. A professora de matemática, Mônica, pque costumava trazer algumas questões um pouco desafiadoras, um dia apareceu com uma que ninguém na sala conseguiu resolver.</p><blockquote>Ninguém mesmo. A turma toda, inclusive eu, ficou boiando.</blockquote><p>Só que, diferente dos outros, aquilo mexeu comigo de um jeito diferente. Enquanto a maioria aceitava que era uma questão difícil e seguiria em frente,<strong> eu não consegui largar o osso</strong>. Fiquei com aquela questão na cabeça. Por que ninguém conseguiu resolver? Por que eu também não?</p><p>A resposta não me importava tanto, mas o desafio de entender por que aquilo era tão complicado me consumiu. Fui atrás.</p><h3>Quando descobri o ITA</h3><p>Foi nesse processo que eu descobri o ITA. Você já ouviu falar? O Instituto Tecnológico de Aeronáutica é, para muitos, o topo do topo quando o assunto é engenharia no Brasil.</p><p>E as questões do vestibular deles… meu irmão, elas não são só difíceis, são quase uma obra de arte de tão complexas. <strong>De verdade, o trem é lindo demais</strong>.</p><p>Cada problema parecia um labirinto sem saída. E, honestamente, aquilo me encantou. Muito. Eu queria, de qualquer jeito, ser um dos poucos que conseguiriam passar por aquele vestibular. Não era nem pela carreira de engenheiro em si, era pelo desafio.</p><blockquote>Só o fato de conseguir resolver aquelas questões já seria uma vitória pessoal. E nada além disso.</blockquote><h3>O Ensino Médio</h3><p>E assim foram os três anos seguintes. Enquanto muitos estavam curtindo a adolescência, eu estava enfurnado nos livros, resolvendo questão atrás de questão.</p><p>Livros do Renato Brito, Caio Guimarães, Peruanos, Russos, os livros do Feltre… todos foram 100% consumidos, de cabo a rabo.</p><p>Literalmente, tudo girava em torno de um objetivo: <strong>passar no ITA</strong>. Eu me desafiava a cada dia, acordava com a meta de ser melhor do que ontem, de resolver mais rápido, com mais precisão, de dominar cada canto daquela matemática.</p><p>Esses estudos me renderem ótimos resultados em outros vestibulares. Gabaritei a prova de matemática e física do ENEM, da UNICAMP e gabaritei a própria OMU (Olimpíada de Matemática da UNICAMP), além de três premiações na OBMEP.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RQv9Ok8qk2vQhcJtlQjuzQ.png" /><figcaption>Eu, em 2019, após ter recebido uma premiação da OBMEP</figcaption></figure><p>Aí veio o grande dia. Fiz a prova. Dei tudo de mim. Saí da sala com aquele sentimento misto de alívio e dúvida. Será que deu? E, para ser bem honesto, eu fiz uma boa prova.</p><blockquote>Mas o resultado… bom, não foi o que eu esperava. Três questões abaixo do corte. Três. Dá pra acreditar?</blockquote><p>Não foi uma derrota esmagadora, mas foi o suficiente para me tirar do jogo. <strong>Eu não passei</strong>.</p><p>Na hora, a frustração foi gigantesca. Aqueles três anos de estudo intenso, toda a dedicação, as noites mal dormidas, tudo parecia que tinha sido jogado fora.</p><p>Eu me lembro de pensar: “Será que eu queria mesmo ser engenheiro? Ou será que eu só estava apaixonado pelo desafio do ITA?”. E, depois de muito refletir, a verdade começou a aparecer: <strong>eu não queria ser engenheiro</strong>.</p><p>Não era sobre a profissão. Era sobre provar para mim mesmo que eu era capaz de resolver aqueles problemas. O desafio tinha sido o que me manteve em movimento. Mas, agora que o desafio tinha acabado, restava uma grande questão: <strong>e agora</strong>?</p><h3>A Minha História Com a Computação</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nO2_tYn5pnor6lNS18cpgg.jpeg" /><figcaption>Um story de 2021, quando ainda produzia música eletrônica.</figcaption></figure><p>Durante todo esse processo de preparação para o ITA, eu já mexia com programação. Python era o meu passa tempo. Ficava, no tempo livre dos domingos, maratonando as aulas do Gustavo Guanabara, do Curso em Vídeo.</p><p>Na verdade, não apenas programação. Tudo relacionado a computadores eu já vi um pouco nesse período. Já estudei sobre photoshop, produção musical, edição de vídeos e, claro, a programação.</p><p>Quando eu queria dar uma pausa na matemática, eu ia para o computador, escrevia uns códigos, criava umas ferramentas bobas, como uma função que calcula Bháskara. Sempre foi algo que me trouxe prazer.</p><blockquote>Então, comecei a pensar: o que existe que une essas duas coisas que eu gosto?</blockquote><p>Programação e matemática. Fui pesquisar. Passei algumas semanas imerso em leituras, assistindo vídeos, tentando entender qual poderia ser o meu caminho. Vi vídeos sobre front-end, back-end, cyber segurança, UI/UX Design e outras áreas.</p><p>Foi assim que eu descobri a Ciência de Dados. E, dentro dela, os algoritmos de Machine Learning. Quando comecei a ler sobre isso, foi como se uma luz se acendesse na minha cabeça. <strong>Era exatamente o que eu procurava.</strong></p><p>Toda a complexidade matemática estava lá, mas agora ela tinha um propósito prático. E mais: eu podia usar programação para aplicar esses conceitos. Era o que eu procurava, cacete!</p><p>A partir desse momento, mergulhei de cabeça. Dei meu 100%. Comecei a estudar tudo o que podia sobre machine learning, algoritmos, redes neurais.</p><p>A sensação de treinar modelos e, principalmente, entender tudo o que está rolando por trás, era (e ainda é!) fenomenal. Ver os dados tomando forma e gerando resultados, me trouxe de volta aquele entusiasmo que eu tinha perdido com o ITA. Mas, dessa vez, era diferente. Eu não estava apenas buscando um desafio vazio. Eu estava construindo algo, aprendendo algo que poderia, de fato, ser aplicado em problemas reais.</p><p>E o tempo foi passando. Quanto mais eu estudava, mais me aprofundava na área. Hoje, eu trabalho com Machine Learning. Mas não é só isso. Meus estudos me levaram até o que, atualmente, está em hype: os Large Language Models (LLMs), e mais especificamente, a técnica de RAG (Retrieval-Augmented Generation).</p><blockquote>É incrível pensar como três questões redefinem o rumo da sua vida.</blockquote><h3>Sobre os Caminhos da Vida</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/962/1*9XI9yKCoJYiUIWQWiKEtyQ.jpeg" /><figcaption>Eu e a Luísa, minha namorada.</figcaption></figure><p>Se você tivesse me perguntado no ensino médio o que eu queria ser, eu teria dito: “engenheiro do ITA”. Mas, no fundo, aquilo não era o que eu queria de verdade.</p><blockquote><strong>Eu estava correndo atrás de um desafio</strong>.</blockquote><p>Um desafio que, de certa forma, me trouxe até aqui. Cada fracasso, cada questão que eu não consegui resolver, me empurrou um pouco mais em direção ao que eu realmente gostava.</p><p>Não só em direção ao que eu realmente gostava, mas também do que eu passaria a gostar — ou amar.</p><p>Hoje, eu vejo que o fracasso de não passar no ITA foi, na verdade, uma das melhores coisas que poderia ter acontecido.</p><p>Porque me forçou a parar e refletir sobre o que eu realmente queria. Se eu tivesse passado, talvez eu estivesse agora em uma carreira que não me traria a mesma satisfação que tenho hoje. <strong>E, honestamente, eu não trocaria o que eu faço por nada.</strong></p><p>No final das contas, a vida é assim. A gente passa por um monte de encruzilhadas, acha que sabe o que quer, mas só quando olha para trás percebe o quanto aquelas dificuldades foram importantes.</p><p>Podem, inclusive, fazer você encontrar pessoas incríveis. Pessoas com quem você irá compartilhar sua vida.</p><p>Não sei em que você acredita, mas Deus tinha o plano de eu fracassar para poder ter sucesso. E eu só entendi isso alguns (bons!) anos depois.</p><p>Se eu aprendi algo com tudo isso, é que os desafios que a gente enfrenta são, muitas vezes, o que nos leva para o caminho certo.</p><p><strong>Mesmo que a gente só descubra isso mais tarde</strong>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eb2cce38a6f6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Quantização de LLMs — Teoria e Prática]]></title>
            <link>https://medium.com/@anwarhermuche/quantiza%C3%A7%C3%A3o-de-llms-teoria-e-pr%C3%A1tica-b63401847dfa?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/b63401847dfa</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[quantization]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[large-language-models]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Sat, 27 Apr 2024 16:26:27 GMT</pubDate>
            <atom:updated>2024-04-27T16:26:27.150Z</atom:updated>
            <content:encoded><![CDATA[<h3>Quantização de LLMs — Teoria e Prática</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9E-0PxU8xmSBe5vHydFgCQ.jpeg" /><figcaption>Imagem 1</figcaption></figure><p>Fala, pessoal! Vamos falar hoje um pouco sobre Quantização de LLMs e como você aplicar na prática.</p><p>Vamos começar com uma pergunta que provavelmente vocês estão tendo agora: o que é quantização?</p><h3>O que é Quantização?</h3><p>A técnica de quantização nos permite reduzir o tamanho de um LLM visando manter a sua qualidade.</p><p>Fazendo uma analogia ao mundo das imagens, quando pensamos em compressão logo de cara já pensamos em perda de qualidade. Na Imagem 2 podemos ver um exemplo. A imagem da direita, após ter o seu tamanho reduzido (e por tamanho estou me referindo à quantidade necessária de memória para armazenamento) perde qualidade.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NpxnxXv6S5v776-85Pz7Jw.png" /><figcaption>Imagem 2</figcaption></figure><p>Mas essa técnica de quantização em LLMs nos permite reduzir o tamanho <strong>perdendo muito pouco da performance do modelo</strong>. E é aqui que mora o grande xis da questão. O ouro de realizar a quantização de LLMs.</p><p>Nos últimos anos, os modelos de Deep Learning vêm ficando cada vez maiores. Em 2018, o GPT-1 tinha, aproximadamente, 110 milhões de parâmetros. Atualmente, em 2024, o GPT-4 possui 1 trilhão de parâmetros. Mais de 9000x maior em apenas 6 anos.</p><p>Entretanto, a memória das GPUs ou TPUs, que realizam o treinamento desses modelos, não está crescendo na mesma ordem. Então, torna-se um desafio para poder utilizar esses modelos sem um consumo tão excessivo do hardware.</p><h3>Compressão de Modelos</h3><p>Dessa forma, um dos principais desafios atualmente é tornar os modelos menores, ou seja, realizar uma compressão com o intuito de torná-los mais acessíveis e poderem ser utilizados sem tornar o custo do hardware tão alto.</p><p>Então, vamos começar a falar sobre algumas técnicas state-of-the-art para compressão de modelos: Pruning e Knowledge Distillation.</p><h4>Pruning</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/866/1*8l3dN3jCWpsuHHQ7G0mjXw.png" /><figcaption>Imagem 3</figcaption></figure><p>Note que a técnica de pruning se consiste em retirar do modelo as partes que não tem tanta importância para a tomada de decisão do modelo. Podemos fazer isso de duas maneiras:</p><ul><li>remover os pesos, definindo-os como sendo zero e tornando a matriz mais esparsa, sem alterar a arquitetura do modelo</li><li>remover neurônios da arquitetura, tornando a arquitetura menor</li></ul><p>Como você pode imaginar, há prós e contras em cada uma das técnicas.</p><p>Remover os pesos pode ser benéfico porque não reduz tanto a performance do modelo, mas requer cálculos computacionais em matrizes esparsas, o que pode não ser tão eficiente. Requer uma certa esparsidade.</p><p>Remover neurônios é mais otimizado porque vai permitir uma computação densa, que na maioria das vezes é mais otimizada que a computação esparsa, porém pode reduzir bem a performance do modelo.</p><h4>Knowledge Distillation (Diluição de Conhecimento)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*q0UARGmgNGrw7P1tw4VN2w.png" /><figcaption>Imagem 4</figcaption></figure><p>A diluição de conhecimento funciona treinando um modelo estudante (Student Model), que é justamente o modelo comprimido que queremos ter, usando o Output do modelo professor (Teacher Model) com a função de custo principal.</p><p>O desafio aqui é você garantir que tem recursos o suficiente para treinar o modelo professor e realizar predições com ele. Isso pode ser bem custoso se você estiver trabalhando com modelos muito grandes.</p><p>Isso nos permite fazer com que o modelo estudante aprenda o comportamento do modelo professor para determinados prompts, o tornando capaz e bem parecido com o professor em determinadas tarefas.</p><h3>A Quantização</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*C3lZ4mHC08_zyhYWJ0kbfg.jpeg" /><figcaption>Imagem 5</figcaption></figure><p>Na quantização, o nosso foco será representar os pesos do modelo com uma menor precisão. Na Imagem 5, podemos ver o <strong><em>wi </em></strong>representando os pesos dos inputs, o <strong><em>b</em></strong> representando o viés e temos um output da função de ativação, o <strong><em>a</em></strong>, que também podemos quantizar.</p><p>A maioria dos modelos alocam os números com o tipo <strong><em>float32</em></strong>, ou seja, aloca 32 bits (4 bytes) para cada parâmetro. Ou seja, em um modelo com 100 milhões de parâmetros, com cada um ocupando 4 bytes na memória, ocuparíamos um total de 382 MB. Para um modelo como o GPT-4 que possui 1 trilhão de parâmetros, precisaríamos de 3.64 terabytes (3725 gigabytes). Porém, será que precisamos de toda essa precisão? Será que afetaria muito reduzir de 32 bits para, por exemplo, 16 bits?</p><p>Se não fizer muita diferença, um modelo que antes ocupava 100 GB agora ocupa 50 GB com essa redução! E é justamente esse o papel da quantização, porém nem tudo são flores. E para explicar o porquê, vou mergulhar em uma área um pouco mais teórica da computação de como um número é representado em binário.</p><h3>Representação Binária</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*x8cruLwdRDALyv8NCkJU8g.png" /><figcaption>Imagem 6</figcaption></figure><p>Como vocês podem imaginar, nosso computador armazena os números na memória em código de máquina (números binários, 0 e 1). O número 8, por exemplo, pode ser representado na base binária como sendo 1000. E cada algarismo desse, cada 1 e 0 é um bit. E quando juntamos 8 bits temos um byte!</p><p>Geralmente, vemos que os tipos de dados no Pandas ou alguma outra biblioteca varia de <strong><em>int8</em></strong>, <strong><em>int16</em></strong>, <strong><em>int32</em></strong>, <strong><em>int64</em></strong> etc.. Esse número representa o número de BITS que ele irá utilizar para armazenar um número. E essa informação pode salvar muita memória.</p><p>Com 8 bits conseguimos representar desde o número 0 até o número 2⁸-1, ou seja, de 0 a 255. Com 16 bits, de 0 a 65.535. Como você deve imaginar, esse número aumenta cada vez mais. E se estamos trabalhando com dados onde os valores geralmente são pequenos, como uma variável idade, podemos trabalhar com apenas 8 bits, visto que nenhuma idade será superior a 255, concorda?</p><p>Quando temos um número que pode assumir valores negativos, geralmente adicionamos 1 bit mais à esquerda para representar o sinal. E apenas um bit é necessário, visto que podemos ter números positivos e negativos (0 e 1).</p><p>Quando falamos da representação do float na memória, e imaginando um <strong><em>float32</em></strong>, fazemos essa representação usando 1 bit para o sinal, 8 bits para o expoente e 23 bits para a mantissa (parte fracionária). Não necessariamente é esse número específico de bits para cada uma das partes, o <em>brain float </em>geralmente reduz a precisão e aumenta o expoente.</p><p>Se convertermos de um tipo de dado para outro, por exemplo de <strong><em>float32</em></strong> para <strong><em>float16</em></strong>, temos o risco de perder precisão — e provavelmente perderemos — mas reduzirá pela metade o tamanho total do arquivo.</p><p>E disse tudo isso para você saber que dependendo de como você representa os seus dados o ganho de memória pode ser realmente bem grande. Se você está disposto a sacrificar precisão, perfeito. Siga em frente na quantização!</p><p>Vamos fazer um exemplo prático? Vou criar uma matriz com números aleatórios em <strong><em>float32</em></strong>. Depois disso, vou converter de <strong><em>float32</em></strong> para <strong><em>float16</em></strong>. A partir daí, vou realizar os cálculos de multiplicação de matrizes e notar a diferença. Observe o código abaixo:</p><pre># Importando o torch<br>import torch<br>import numpy as np<br><br># Criando um tensor aleatório com float32 de tipo<br>tensor_float32 = torch.rand(size = (1000,), dtype = torch.float32)<br><br># Convertendo para float16<br>tensor_float16 = tensor_float32.to(dtype = torch.float16)<br><br># Multiplicando os elementos do tensor_float32 e do tensor_float16<br>resultado32 = np.dot(tensor_float32, tensor_float32)<br>resultado16 = np.dot(tensor_float16, tensor_float16)<br><br># Exibindo o resultado<br>print(f&quot;Resultado 32 bits: {resultado32}&quot;)<br>print(f&quot;Resultado 16 bits: {resultado16}&quot;)<br><br># Resultado 32 bits: 340.8283996582031<br># Resultado 16 bits: 340.75</pre><p>Notou que o resultado foi bem parecido, mas com o <strong><em>float32</em></strong> tendo mais precisão? Era o esperado. E se essa pequena perda de precisão não for tão crítico para a nossa aplicação, conseguimos reduzir pela metade a memória ocupada!</p><h3>Aplicação Prática em um Modelo do HuggingFace</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QKJivQ0XWksRgSq0_rMRAg.png" /><figcaption>Imagem 7</figcaption></figure><p>Vamos ver agora em um modelo real com alguns milhões de parâmetros! Como a conversão dos tipos pode alterar? Bom, para isso vou usar um modelo chamado <strong>BlipForConditionalGeneration</strong>.</p><p>Esse modelo é de visão e linguagem baseado na aquitetura do Transformer que gera descrições textuais a partir de imagens, utilizando um encoder para processar características visuais e um decoder autoregressivo para produzir texto.</p><p>Vamos importar esse modelo para o nosso ambiente utilizando a biblioteca transformers do HuggingFace e verificar a quantidade de parâmetros e memória que esse modelo ocupa.</p><pre># Importando a classe do modelo<br>from transformers import BlipForConditionalGeneration<br><br># Definindo o modelo<br>modelo = BlipForConditionalGeneration.from_pretrained(&quot;Salesforce/blip-image-captioning-base&quot;)<br><br># Parâmetros<br>total_params = sum(p.numel() for p in modelo.parameters())<br>print(f&#39;Total de parâmetros: {total_params:,}&#39;)<br><br># Memória<br>memoria_megabytes = modelo.get_memory_footprint()/(2**20)<br>print(f&quot;Memória em megabytes necessária para alocar os parâmetros: {memoria_megabytes:,.2f}&quot;)<br><br># Total de parâmetros: 247,414,076<br># Memória em megabytes necessária para alocar os parâmetros: 943.81</pre><p>Note que esse modelo com 247 milhões de parâmetros ocupa um total de 943 megabytes! Será que podemos reduzir isso? Bom, como você deve imaginar, sim, podemos. E faremos isso utilizando a quantização, mas antes vamos conferir os tipos de dados inicializados para os parâmetros dos modelos com o código abaixo.</p><pre># Vendo os tipos de dados dos parâmetros<br>for nome, parametro in modelo.named_parameters():<br>    print(f&quot;O parâmetro {name} possui o tipo {parametro.dtype}&quot;)<br>    <br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br># O parâmetro text_decoder.cls.predictions.decoder.weight possui o tipo torch.float32<br>.<br>.<br>.</pre><p>Como você pode ver, os parâmetros realmente são inicializados em <strong><em>float32</em></strong>. Além disso, eu coloquei apenas os 9 primeiros parâmetros, mas temos muito mais.</p><p>Agora, vamos reduzir de <strong><em>float32 </em></strong>para <strong><em>brain</em></strong><em> </em><strong><em>float16</em></strong>. Sim, eu não comentei sobre esse tal <strong><em>brain float16</em></strong>, mas vou comentar agora. Esse é um formato de ponto flutuante de 16 bits que é otimizado para redes neurais. Ele permite cálculos mais rápidos e uso bem mais eficiente da memória em comparação com a precisão de ponto flutuante padrão de 32 bits.</p><p>No código abaixo, realizo a conversão de todos os parâmetros do modelo para <strong><em>bfloat16</em></strong> e mostro o consumo de memória.</p><pre># Importando a classe do modelo<br>from transformers import BlipForConditionalGeneration<br><br># Definindo o modelo<br>modelo = BlipForConditionalGeneration.from_pretrained(&quot;Salesforce/blip-image-captioning-base&quot;, torch_dtype = torch.bfloat16)<br><br># Memória<br>memoria_megabytes = modelo.get_memory_footprint()/(2**20)<br>print(f&quot;Memória em megabytes necessária para alocar os parâmetros: {memoria_megabytes:,.2f}&quot;)<br><br># Memória em megabytes necessária para alocar os parâmetros: 471.91</pre><p>Olha só! Saímos de 943 MB para 471MB, ou seja, é praticamente metade do tamanho do modelo original.</p><p>Agora, vamos comparar a performance dos dois modelos? Do modelo com os parâmetros em <strong><em>float32 </em></strong>e com os parâmetros em <strong><em>bfloat16</em></strong>? Como é um modelo que recebe uma imagem e nos retorna um texto descrevendo a imagem, vou utilizar a imagem abaixo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8Q4PM6gok9MX40IyH9gajA.jpeg" /><figcaption>Imagem 8</figcaption></figure><p>Note que retrata uma mulher sentada na areia da praia com o cachorro dela. No código abaixo, crio os dois modelos diferentes e faço as predições para podermos comparar se há alguma diferença:</p><pre># Imports<br>from PIL import Image<br>from urllib.request import urlopen<br>from transformers import BlipProcessor<br><br># Imagem<br>image = Image.open(urlopen(&#39;https://storage.googleapis.com/sfr-vision-language-research/BLIP/demo.jpg&#39;))<br><br># Modelos<br>model_name = &quot;Salesforce/blip-image-captioning-base&quot;<br>modelo_float32 = BlipForConditionalGeneration.from_pretrained(model_name, torch_dtype = torch.float32)<br>modelo_bfloat16 = BlipForConditionalGeneration.from_pretrained(model_name, torch_dtype = torch.bfloat16)<br><br># Processor<br>processor = BlipProcessor.from_pretrained(model_name)<br><br># Função para retornar o output<br>def geraPredicoes(model, processor, image, datatype):<br>    inputs = processor(images = image, return_tensors=&quot;pt&quot;).to(datatype)<br>    outputs = model.generate(**inputs)<br>    prediction = processor.decode(outputs[0], skip_special_tokens = True)<br>    return prediction<br><br># Predições<br>output_float32 = geraPredicoes(modelo_float32, processor, image, torch.float32)<br>output_bfloat16 = geraPredicoes(modelo_bfloat16, processor, image, torch.bfloat16)<br><br># Resultados<br>print(f&quot;Resultado modelo float32: \n{output_float32}&quot;)<br>print(&#39;&#39;)<br>print(f&quot;Resultado modelo bfloat16: \n{output_bfloat16}&quot;)<br><br># Resultado modelo float32: <br># a woman sitting on the beach with her dog<br><br># Resultado modelo bfloat16: <br># a woman sitting on the beach with a dog</pre><p>Note que a diferença dos resultados foi que no modelo de <strong><em>bfloat16 </em></strong>tivemos “with <strong>a</strong> dog”, e no primeiro “with <strong>her</strong> dog”. Essa foi a única diferença no output. E por que isso ocorreu mesmo com as diferenças sendo tão baixas?</p><p>Como esse modelo especificamente é autoregressivo, isso faz com que um erro no começo seja passado adiante em todas as previsões seguintes, fazendo meio que um efeito cascata de erros. Mas em termos práticos a diferença foi mínima para o ganho de memória que tivemos.</p><h3>Quantização Linear</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rCtUNP1qoOL9wxFmXuO5zA.png" /><figcaption>Imagem 9</figcaption></figure><p>Quantização é o processo de mapear um conjunto maior de valores para um conjunto menor de valores. E há diversas técnicas para podermos realizar esse processo, entretanto vamos focar na quantização linear.</p><p>Vamos supor que você tem a matriz abaixo representada pelo tipo <strong><em>float32 </em></strong>e você deseja converter para <strong><em>int8</em></strong>. Como podemos fazer isso sem perder tanta informação? Note que já perderemos a precisão das casas decimais, além de conseguirmos representar, em tese, menos números que antes… mas daremos um jeito nisso.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IIyiBiBNUl1dwlwZXXSDqg.png" /><figcaption>Imagem 10</figcaption></figure><p>Antes de tudo, sabemos que <strong><em>int8</em> </strong>nos permite variar entre -128 até 127. Então, a primeira coisa que faremos é pegar o maior elemento da matriz original (728.6) e atribuir ele como sendo 127 e o menor valor da matriz original (-184) como sendo -128. A partir daí, fazemos um mapeamento linear de cada um dos outros valores. E podemos fazer isso com a equação abaixo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VFQnAVHKUbwqAolzgz_m8A.png" /><figcaption>Imagem 11</figcaption></figure><p>Note que, a partir de um determinado número representado em <strong><em>float32</em></strong>, conseguimos mapear o seu valor utilizando uma equação linear para a representação inteira. Claro, realizando o devido truncamento ou arredondamento em seu valor. Vou seguir com o truncamento aqui.</p><p>Por exemplo, Se x = -13.5 o valor que será representado em <strong><em>int8 </em></strong>será -80. Se x = 684.6 o valor mapeado será 114. Dessa forma, terminamos com a matriz abaixo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hkrePkTTUz09D-a98ic6rw.png" /><figcaption>Imagem 12</figcaption></figure><p>Muito massa, né? Agora, e se quiséssemos voltar aos dados originais em <strong><em>float32</em></strong>? Bom, você pode até pensar que seria pegar a f-1(x) (a função inversa da que temos), mas não chegaremos em um resultado idêntico.</p><p>E não conseguimos devido ao trucamento que realizamos ao converter para inteiro. Entretanto, chegaremos em um resutado bem próximo que pode muito bem ser utilizado.</p><h4>Quantização Linear na Prática</h4><p>A primeira coisa que faremos é instalar a biblioteca <strong><em>quanto </em></strong>(pip install quanto), também do HuggingFace. Ela nos permite utilizar diversos métodos de quantização, inclusive a linear que acabamos de ver.</p><p>No código abaixo, vamos utilizar o <em>pythia-410m</em>, um modelo com 410 milhões de parâmetros que pertence a uma coleção de modelos de diferentes tamanhos desenvolvida para pesquisas de interpretabilidade.</p><pre># Importando o modelo<br>from transformers import AutoModelForCausalLM, AutoTokenizer<br><br># Modelo<br>model_name = &quot;EleutherAI/pythia-410m&quot;<br>modelo = AutoModelForCausalLM.from_pretrained(model_name, low_cpu_mem_usage = True)<br><br># Tokenizador<br>tokenizer = AutoTokenizer.from_pretrained(model_name)<br><br># Função para gerar o output<br>def gerarResposta(texto, modelo, tokenizer):<br>    inputs = tokenizer(texto, return_tensors = &quot;pt&quot;)<br>    outputs = modelo.generate(**inputs, max_new_tokens = 30)<br>    return tokenizer.decode(outputs[0], skip_special_tokens = True)<br><br># Texto teste<br>texto = &quot;Olá! Meu nome é Anwar, sou cientista de dados e eu&quot;<br><br># Resposta gerada<br>resposta = gerarResposta(texto, modelo, tokenizer)<br>print(f&quot;Resposta: {resposta}&quot;)<br><br># Resposta: Olá! Meu nome é Anwar, sou cientista de dados e eu sou um dos meus colegas mais importantes.<br><br># Agora, o que é que vocês estão a fazer?</pre><p>Note que ele completou a minha resposta. Sinceramente, não gostei tanto do resultado. Mas não estamos aqui para avaliar se um modelo X é bom ou ruim, mas comparar a sua performance com a sua versão quantizada.</p><p>Dito isso, vamos fazer uma análise de tamanho antes de fazer a análise de performance. Como o modelo original possui 410 milhões de parâmetros e cada parâmetro contém 32 bits (4 bytes), logo o modelo possui 1.52 gigabytes de tamanho. Se cada parâmetro fosse do tipo <strong><em>int8</em></strong>, logo o modelo teria 0.38 gigabytes de tamanho. Ou seja, houve uma redução de 4x de tamanho.</p><p>No código abaixo, podemos ver a utilização da biblioteca <strong><em>quanto </em></strong>e das funções quantize e freeze. Quando chamamos o quantize, o quanto cria um estado intermediário e então você chama o freeze para realmente quantizar os pesos.</p><pre># Importando as funções do quanto + tipo int8<br>from quanto import quantize, freeze, qint8<br><br># Realizando a quantização (estado intermediário)<br>quantize(modelo, weights = qint8, activations = None)<br><br># Estado final de quantização<br>freeze(modelo)<br><br># Verificando a saída do novo modelo<br>resposta = gerarResposta(texto, modelo, tokenizer)<br>print(f&quot;Resposta: {resposta}&quot;)<br><br># Resposta: Olá! Meu nome é Anwar, sou cientista de dados e eu sou um dos mais importantes.<br><br># — O que é que você quer dizer? — perguntou.<br><br># — Não</pre><p>Podemos notar que a resposta foi bem diferente que a primeira que obtivemos. Para ter uma maior comprovação, você poderia testar o mesmo modelo de Image2Text que usamos anteriormente.</p><p>Sobre aquele estado intermediário que disse, ele basicamente serve para duas coisas:</p><ul><li>Sabemos que a ativação do modelo depende muito do input, logo se você quer quantizar as ativações do modelo o estado intermediário vai ajudar você a saber o mínimo e o máximo range dessa ativação para poder calibrar a sua transformação;</li><li>Além disso, ele é útil para os casos de “quantization aware training”, ou seja, você mantém esse estado intermediário durante o backpropagation, mas durante o feedforward será utilizado os parâmetros quantizados.</li></ul><h3>Conclusão</h3><p>Finalizamos por aqui, pessoal.</p><p>Se você chegou até aqui, parabéns! Você realmente é um(a) guerreiro(a). E tenho certeza de que aprendeu muito sobre quantização de LLMs e não paramos por aqui.</p><p>O próximo artigo será sobre o QLoRA (Quantized Low-Rank Adaption), que usa esse conceito de quantização e é um dos métodos mais utilizados atualmente.</p><p>Não se esqueça de me seguir para mais tutoriais como este. E ah, tomei como um material de referência para esse artigo o <a href="https://learn.deeplearning.ai/accomplishments/4149f2d8-04ab-4118-98ad-575422564cb5?usp=sharing">curso gratuito da DeepLearning.AI</a> sobre Quantização em parceria com o HuggingFace.</p><p>Até mais!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b63401847dfa" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Métodos de Busca em Grafos — BFS & DFS]]></title>
            <link>https://medium.com/@anwarhermuche/m%C3%A9todos-de-busca-em-grafos-bfs-dfs-cf17761a0dd9?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/cf17761a0dd9</guid>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[depth-first-search]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Wed, 17 Apr 2024 00:37:12 GMT</pubDate>
            <atom:updated>2024-04-17T00:38:46.085Z</atom:updated>
            <content:encoded><![CDATA[<h3>Métodos de Busca em Grafos — BFS &amp; DFS</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*6JG9CS9v4G9XC0vl.png" /><figcaption>Imagem 1</figcaption></figure><p>Fala, galera!</p><p>Hoje, vou fazer a parte 2 de uma sequência sobre Grafos. Na <a href="https://medium.com/@anwarhermuche/teoria-dos-grafos-introdu%C3%A7%C3%A3o-defini%C3%A7%C3%B5es-matriz-e-lista-de-adjac%C3%AAncia-2252d4800a44">parte 1</a>, dei uma introdução à Teoria dos Grafos. Hoje, vamos nos aprofundar um pouco mais.</p><p>Falaremos sobre dois métodos de busca muito famosos e que se você busca um maior aprofundamento em algoritmos da computação, é um conhecimento que deve ter.</p><p>Vamos começar!</p><h3>O que são Métodos de Busca?</h3><p>Quando falamos em realizar uma busca em um grafo, basicamente estamos dizendo que iremos percorrer as arestas do grafo de forma sistemática, passando pelos vértices.</p><p>Eu citei dois algoritmos muito famosos de busca: <strong>Breadth-Fist Search</strong> (BFS ou Busca em Largura) e o <strong>Depth-First Search</strong> (DFS ou Busca em Profundidade).</p><h3>Depth-First Search (DFS)</h3><p>Vamos começar com o DFS! Como o próprio nome diz, iremos realizar uma busca em profundidade. Vamos fazer um exemplo para ficar mais claro. Observe o grafo abaixo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*aApu4NMQukGtjySD1lvbsw.gif" /><figcaption>Imagem 2</figcaption></figure><p>Vou escrever qual é a lógica para realizarmos essa busca em profundidade.</p><h4>Lógica de Funcionamento</h4><p>Primeiramente, definimos um nó inicial. Começamos aí com o Nó 1. Enquanto este nó não for num nó final, e por nó final eu quero dizer um nó onde todas as adjacências já tenham sido visitadas, escolhemos um dos adjacentes não visitado e o visitamos.</p><p>No exemplo, ele começa no Nó 1 (marcando-o como visitado) e vê todas as suas adjacências: Nó 2, Nó 5 e Nó 3. Ele vai para o Nó 2 (marcando-o como visitado) e e olha para todas as adjacências dele: Nó 6 e Nó 4. A partir daí, ele vai para o Nó 6 (marcando-o como visitado) e olha para suas adjacências: Nó 2. Como o Nó 2 já foi visitado, ele vai para a outra adjacência de Nó 2 que não foi visitada (Nó 4, marcando-o como visitado).</p><p>Se o nó que estamos observando tiver pai, voltamos ao pai dele. Se não tiver pai, mas se tiver um nó não visitado, escolhemos outro nó não visitado.</p><h4>Aplicação do Algoritmo DFS</h4><p>Vamos supor que estamos lidando com o seguinte problema:</p><blockquote>Conte a quantidade de caminhos únicos do topo superior esquerdo ao topo inferior direito. Um único caminho deve se mover apenas nos 0’s e não pode visitar a mesma posição mais de uma vez.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/0*Almjt9cHjDl6HYBH.png" /><figcaption>Imagem 3</figcaption></figure><p>Primeira coisa é que notamos que eu já descrevi o nosso grafo como sendo essa matriz. Se utilizarmos apenas o grafo, não teria graça, hahaha. Abaixo, você pode ver a representação em um grafo da matriz acima, considerando apenas 0’s como sendo caminhos válidos:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/347/0*0Gr6uv28dsGqr_x5.png" /><figcaption>Imagem 4</figcaption></figure><p>Bom, vamos continuar com a nossa matriz, mesmo. Como podemos aplicar uma busca em profundidade aí? Vamos escolher um nó (o 0 do topo superior esquerdo) e vamos fazer as seguintes verificações:</p><ul><li>Há algum nó adjacente igual a 0?</li><li>Há algum nó adjacente que não foi visitado?</li></ul><p>Considerando a estrutura de um grafo, essas são as perguntas que nos faremos para percorrer toda a estrutura. Mas como estamos trabalhando com uma matriz, devemos fazer mais algumas considerações:</p><ul><li>O índice da linha e da coluna estão dentro do escopo (sempre maiores ou iguais a 0 e menores que o tamanho de linhas e colunas)?</li></ul><p>Faremos essas verificações. Além disso, caso os índices correspondam ao índice que buscamos (do elemento inferior direito), ou seja, N-1 e M-1, sendo N e M a quantidade de linhas e colunas, respectivamente, encontramos um caminho possível!</p><p>Vamos traduzir isso para o código?</p><pre># Quantidade de caminhos<br>def DFS(matriz, linha, coluna, visitado):<br>  LINHAS, COLUNAS = len(matriz), len(matriz[0])<br><br>  if min(linha, coluna) &lt; 0 or linha == LINHAS or coluna == COLUNAS or (linha, coluna) in visitado or matriz[linha][coluna] == 1:<br>    return 0<br><br>  if linha == LINHAS - 1 and coluna == COLUNAS - 1:<br>    return 1<br><br>  visitado.add((linha, coluna))<br><br>  caminhos = 0<br>  caminhos += DFS(matriz, linha + 1, coluna, visitado)<br>  caminhos += DFS(matiz, linha, coluna + 1, visitado)<br>  caminhos += DFS(matriz, linha - 1, coluna, visitado)<br>  caminhos += DFS(matriz, linha, coluna - 1, visitado)<br><br>  visitado.remove((linha, coluna))<br>  return caminhos</pre><p>Vou explicar cada trecho de código aqui. Começando pelo primeiro <em>if</em>, que podemos ver abaixo. Note que fazemos as seguintes verificações:</p><ul><li>Os índices da linha e da coluna são menores que 0?</li><li>Passamos o número máximo para os índices da linha e da coluna?</li><li>Já visitamos o elemento?</li><li>O elemento é igual a 1?</li></ul><p>Note que se dissermos ‘sim’ para uma dessas respostas, não consideramos como sendo um caminho válido. Por isso, retornamos 0 caso isso ocorra.</p><pre>if min(linha, coluna) &lt; 0 or linha == LINHAS or coluna == COLUNAS or (linha, coluna) in visitado or matriz[linha][coluna] == 1:<br>  return 0</pre><p>Depois, verificamos se chegamos no elemento que queríamos! Como o nosso interesse no problema acima era chegar no elemento do canto inferior direito, ou seja, de índices N-1 e M-1, fizemos essa verificação.</p><p>E quando a gente chega no elemento que queremos, adicionamos uma unidade ao contador de possíveis caminhos.</p><pre>if linha == LINHAS - 1 and coluna == COLUNAS - 1:<br>    return 1</pre><p>Se não acontece nem um nem outro, ou seja, estamos ali em posições válidas, adicionamos o par linha-coluna a um set() que diz se já foi visitado ou não. Quando inicializamos o algoritmo, passamos um set() vazio.</p><pre>visitado.add((linha, coluna))</pre><p>Após isso, chamamos a nossa função criando uma recursão para cada posição adjacente. Note que o que muda no argumento da função DFS é apenas o índice da linha e da coluna.</p><p>Perceba também que, como “linha + 1” é a primeira, então nossa busca em profundidade fará com que o algoritmo tente sempre descer nas linhas em profundidade. Mas ele vai testar todos os caminhos adjacentes.</p><p>Olhando para baixo, para a direita, para cima e para a esquerda, respectivamente nas chamadas recursivas.</p><pre>caminhos = 0<br>caminhos += DFS(matriz, linha + 1, coluna, visitado)<br>caminhos += DFS(matiz, linha, coluna + 1, visitado)<br>caminhos += DFS(matriz, linha - 1, coluna, visitado)<br>caminhos += DFS(matriz, linha, coluna - 1, visitado)</pre><p>Talvez o trecho mais “complicado” de entender seja o que está abaixo. Mesmo sendo apenas de duas linhas, o conceito por trás pode ser complexo, mas vou explicar de uma forma que você entenderá.</p><p>Perceba que antes de retornar o contador, estamos excluindo uma tupla do nosso conjunto de visitado. E por que isso? Bom, vamos supor que estamos no elemento 0 acima do nosso alvo. A partir dele, o nosso count para o DFS(matriz, linha + 1, coluna, visitado) irá retornar 1 e todos os outros zero.</p><p>Dessa forma, vamos excluir essa posição do 0 de cima como sendo visitado com o visitado.remove((linha, coluna)) e retornaremos 1.</p><p>Mas lembre-se de que não podemos passar pelo mesmo elemento em UM CAMINHO, não em todos. Logo, quando formos testar outros caminhos, esse cara precisa ser desmarcado como visitado. E aí entra um conceito chamado Backtracking.</p><p>Backtracking é uma técnica de resolução de problemas que tenta todas as possíveis soluções uma a uma e descarta aquelas que não funcionam. Ou seja, se um caminho não funciona, voltamos atrás e tentamos novamente. Só que, ao “voltarmos atrás”, devemos excluir os pares como visitados.</p><pre>visitado.remove((linha, coluna))<br>return count</pre><p>Se formos analisar a complexidade de tempo dessa solução, devemos olhar para o pior cenário. E o pior cenário é onde todos os elementos são iguais a 0, ou seja, não há nenhum impeditivo.</p><p>Como temos 4 possíveis caminhos em cada uma das chamadas, formaremos uma árvore onde cada nó possui 4 filhos e a profundidade dessa árvore será igual à quantidade de elementos da matriz, que é <strong>n*m</strong>, onde <strong>n</strong> é a quantidade de linhas e <strong>m</strong> a quantidade de colunas.</p><p>Dessa forma, no pior caso, teremos uma complexidade de tempo igual a <strong>O(4^(n*m))</strong>. Não é muito eficiente, mas era esperado por ser um algoritmo de força bruta que usa backtracking.</p><h3>Breadth-First Search (BFS)</h3><p>Indo agora para o BFS, como o próprio nome diz ele realiza uma busca em largura! Para ficar mais claro, observe o GIF abaixo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/762/1*PvXMyl7PHuW8GAszMlYKZQ.gif" /><figcaption>Imagem 5</figcaption></figure><p>Para facilitar a compreensão, vou escrever a lógica de funcionamento.</p><h4>Lógica de Funcionamento</h4><p>Em um primeiro momento, iremos definir o nó inicial, marcar como visitado e adicioná-lo à fila. No caso, começamos pelo Nó 1. Lembre-se de que uma fila tem como característica que o primeiro elemento a entrar é o primeiro a sair (FIFO, First In, First Out).</p><p>Depois disso, enquanto a fila não estiver vazia, removemos o primeiro nó da fila (chamaremos esse nó de <strong>u</strong>) e para cada <strong>v</strong> de <strong>u</strong>, se <strong>v</strong> não foi explorado, marcamos <strong>v</strong> como explorado e o adicionamos à fila. Repetimos isso de outro nó inicial se houver.</p><p>No caso da Imagem 5, começamos com o Nó 1 na fila. Depois, vemos quem são os vizinhos do Nó 1 (que são os nós 2, 5 e 3) e os adicionamos na fila. Repetimos o processo até que não haja mais nós a serem explorados.</p><h4>Aplicação do Algoritmo BFS</h4><p>Para fazer uma aplicação desse algoritmo, vamos usar o seguinte problema:</p><blockquote>Encontre o comprimento do menor caminho partindo do canto superior esquerdo da matriz até o canto inferior direito.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*I8Yd4a5Fom-_ICQ-mQnyWw.png" /><figcaption>Imagem 6</figcaption></figure><p>Note que essa matriz é diferente da anterior. Temos mais de um caminho possível para chegar do 0 do canto superior esquerdo até o 0 do canto inferior direito. E a regra continua a mesma: não podemos passar mais de uma vez em uma posição em um caminho e não podemos passar nos 1&#39;s.</p><p>Como podemos aplicar a busca em largura aí? Primeiramente, vamos criar o nosso set() de visitados e uma fila! No Python, criamos uma fila com o deque(), que chamaremos de <em>queue</em>.</p><p>A partir daí, escolhemos o nó inicial (0, 0) e o adicionamos à fila e ao conjunto <em>visitados</em>. Inicializamos a nossa variável para armazenar o comprimento do caminho e, enquanto a fila não estiver vazia:</p><ul><li>Olho para o elemento mais à esquerda da fila</li><li>Se o elemento mais à esquerda for o que eu quero chegar, retorno o comprimento</li><li>Se não for, olho para cada um dos quatro vizinhos (direita, esquerda, baixo e cima).</li><li>Verifico aquelas condições de borda (índices menores que 0, maiores que o comprimento da matriz, elemento igual a 1 ou se já foi visitado)</li><li>E não cair em nenhuma situação anterior, adiciono o elemento ao conjunto <em>visitados</em> e ao final da fila.</li></ul><p>Vamos traduzir isso para o código!</p><pre>def BFS(matriz):<br>  LINHAS, COLUNAS = len(matriz), len(matriz[0])<br>  visitados = set()<br>  fila = deque()<br>  queue.append((0, 0))<br>  visitados.add((0, 0))<br><br>  comprimento = 0<br>  while fila:<br>    for i in range(len(fila)):<br>      linha, coluna = fila.popleft()<br><br>      if linha == LINHAS - 1 and coluna == COLUNAS - 1:<br>        return comprimento<br>    <br>      vizinhos = [[0, 1], [0, -1], [1, 0], [-1, 0]]<br>      for auxLinha, auxColuna in vizinhos:<br>        newLinha, newColuna = auxLinha + linha, auxColuna + coluna<br>        if min(newLinha, newColuna) &lt; 0 or newLinha == LINHAS or newColuna == COLUNAS or (newLinha, newColuna) in visitados or matriz[newLinha][newColuna] == 1:<br>          continue<br>        fila.append((newLinha, newColuna))<br>        visitados.add((newLinha, newColuna))<br>    <br>    comprimento += 1</pre><p>Novamente, vamos explicar trecho por trecho, “começando pelo começo”. Abaixo, você pode ver que inicializamos todas as variáveis que precisaremos: o set() que armazena os elementos visitados, a nossa fila e já adicionamos o par dos índices do elemento que começaremos à fila e ao set().</p><pre>LINHAS, COLUNAS = len(matriz), len(matriz[0])<br>visitados = set()<br>fila = deque()<br>queue.append((0, 0))<br>visitados.add((0, 0))</pre><p>Depois disso, inicializamos a variável do comprimento como sendo 0 e iteramos enquanto a fila não estiver vazia. Se o priemiro elemento inserido tiver o índice igual ao que estamos procurando (e aqui estamos procurando aquele do canto inferior direito, ou seja, de índice N-1 e M-1, onde N é a quantidade de linhas e M a de colunas), retornamos o comprimento.</p><pre>comprimento = 0<br>while fila:<br>  for i in range(len(fila)):<br>    linha, coluna = fila.popleft()<br><br>    if linha == LINHAS - 1 and coluna == COLUNAS - 1:<br>      return comprimento</pre><p>A partir disso, para cada um dos vizinhos, fazemos toda aquela verificação que disse anteriormente e caso esteja tudo ok, adicionamos o nó à fila e ao set() <em>visitados</em>.</p><pre>vizinhos = [[0, 1], [0, -1], [1, 0], [-1, 0]]<br>for auxLinha, auxColuna in vizinhos:<br>  newLinha, newColuna = auxLinha + linha, auxColuna + coluna<br>  if min(newLinha, newColuna) &lt; 0 or newLinha == LINHAS or newColuna == COLUNAS or (newLinha, newColuna) in visitados or matriz[newLinha][newColuna] == 1:<br>    continue<br>  fila.append((newLinha, newColuna))<br>  visitados.add((newLinha, newColuna))</pre><p>Por fim, quando já percorremos os elementos DA LARGURA (que é os que estão na fila naquele momento), adicionamos 1 ao comprimento.</p><pre>comprimento += 1</pre><p>Analisando a complexidade de tempo desse algoritmo, vemos que ele percorre todos os elementos da matriz no pior caso, ou seja, é de <strong>O(n*m)</strong>. Para esse tipo de problema onde queremos saber o caminho mais curto entre 2 posições dadas algumas restrições, ele é bem mais eficiente que o DFS.</p><h3>Comparação entre BFS e DFS</h3><p>Há vantagens e desvantagens de cada um dos métodos para situações específicas.</p><p>Quando estamos trabalhando com grafos densos, ou seja, com a relação E/(V*(V-1)) próxima de 1, o BFS pode ser mais eficiente. Além disso, usamos o BFS comumente em problemas onde queremos saber qual o caminho mínimo de arestas entre um vértice e qualquer um outro.</p><p>Há desvantagens em usar o BFS quando o grafo for esparso, com a relação próxima de 0, que acaba sendo menos eficiente. Além disso, requer mais espaço de armazenamento para fila de vértices.</p><p>Já o DFS é bastante útil quando queremos encontrar o total de caminhos de um ponto X a um ponto Y ou encontrar ciclos, e pode ser mais eficiente em grafos esparsos, onde aquela relação é próxima de zero.</p><h3>Conclusão</h3><p>Chegamos ao final de mais um artigo, pessoal.</p><p>Nos próximos, falarei sobre alguns algoritmos sobre ordem topológica, conexidade forte, o algoritmo de Kruskall e Prim e muito mais.</p><p>Já me siga para não perder todos esses artigos.</p><p>Até já.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cf17761a0dd9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Teoria dos Grafos —Introdução, Definições, Matriz e Lista de Adjacência]]></title>
            <link>https://medium.com/@anwarhermuche/teoria-dos-grafos-introdu%C3%A7%C3%A3o-defini%C3%A7%C3%B5es-matriz-e-lista-de-adjac%C3%AAncia-2252d4800a44?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/2252d4800a44</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Tue, 02 Apr 2024 23:59:28 GMT</pubDate>
            <atom:updated>2024-04-02T23:59:28.051Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*kKGoeR6U4emPSR4w" /><figcaption>Imagem 1</figcaption></figure><p>Fala, pessoal!</p><p>Hoje, quero falar sobre um conceito que não estamos tão acostumados a ver em Ciência de Dados, mas que é extremamente útil — e bonito — em diversas aplicações: GRAFOS!</p><p>Repita comigo: grafos. Não GARFOS.</p><p>Ok, chega de piada ruim e vamos começar a discutir um pouco mais sobre essa estrutura de dados.</p><h3>Definições Iniciais</h3><p>Vamos começar dando nome aos bois, como dizia minha professora de matemática. Precisamos falar o que significa cada coisa antes de já partir para explicações mais complexas.</p><p>Na Imagem 1, podemos notar que temos algumas bolinhas cinza. Chamamos essas bolinhas de <strong>Vértices</strong> ou <strong>Nós </strong>(<strong>Vertices</strong>, em inglês). Além disso, temos também essas linhas ou setas que ligam os vértices. Chamamos essas linhas ou setas de <strong>Arestas </strong>(<strong>Edges</strong>, em inglês).</p><p>Dessa forma, podemos dizer que um grafo é um conjunto de vértices e arestas, onde cada aresta conecta dois vértices. Podemos usar grafos para modelar relacionamentos!</p><p>Se uma pessoa X conhece as pessoas Y e Z e a pessoa Y conhece as pessoas X e W, podemos modelar o grafo da seguinte maneira, mostrado na Imagem 2.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/342/0*RX4kEUEIsh0V5sxo" /><figcaption>Imagem 2</figcaption></figure><p>Agora, voltando na Imagem 1, notou que os grafos (a) e (b) não possuem setas, mas sim linhas sem orientação? Por isso, chamamos de um grafo <strong>não direcionado</strong>. Quando há setas, como no caso dos grafos ( c ) e (d), chamamos de grafo <strong>direcionado </strong>(orientado).</p><p>Em um grafo orientado, devemos obrigatoriamente respeitar a direção indicada. Se há uma seta saindo de V1 para V2 (sendo V1 e V2 dois vértices do grafo) e não há uma seta saindo de V2 e indo para V1, não podemos partir de V2 para chegar em V1.</p><p>Entretanto, em um grafo não direcionado, se há uma aresta conectando V1 e V2, podemos ir tanto de V1 para V2 quanto de V2 para V1.</p><h4>Número máximo de arestas</h4><p>Há uma relação muito bacana em grafos direcionados que limita o número de arestas com base no número de vértices. Uma relação que envolve um pouco de análise combinatória.</p><p>Como eu gosto de explicar o porquê das coisas, vou falar sobre essa relação aqui. Basicamente, temos a relação abaixo, na Imagem 3.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/627/1*r7MlO_HAyjuoVtDeb4Hhiw.png" /><figcaption>Imagem 3</figcaption></figure><p>Aqui, estamos dizendo que o número de arestas (Edges) é menor ou igual ao número de vértices ao quadrado em um grafo direcionado. E isso é fácil de demonstrar com um pingo de combinatória.</p><p>Quantos pares distintos de vértices podemos formar em um grafo de V vértices? Note que, aqui, a ordem importa. Uma tupla (V1, V2) é diferente da tupla (V2, V1). No primeiro caso, temos um caminho que sai de V1 e chega em V2. No segundo caso, temos um caminho que sai de V2 e chega em V1.</p><p>Além disso, note que que um grafo pode “sair” e “entrar” nele mesmo! Na Imagem 4, mostrada abaixo, você vê que o vértice 4 possui um loop (ou laço).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/299/0*eg5zFvNZw3jB-THg.png" /><figcaption>Imagem 4</figcaption></figure><p>Dito tudo isso, podemos calcular o número máximo de arestas vendo as possibilidades de tuplas que temos. Para a primeira posição da tupla, podemos escolher qualquer vértice, logo, temos N possibilidades. Para a segunda posição, também temos N possibilidades, visto que ele pode apontar para ele mesmo (loop).</p><p>Logo, temos N*N = N² arestas no total, chegando na relação da Imagem 3.</p><h3>Conceitos Formais</h3><p>De forma mais formal, um grafo é um par de conjuntos G = (V, A), onde V é um conjunto de vértices e A é um conjunto de arestas. Observe o código abaixo:</p><pre># Vértices (Vertices)<br>V = {v1, v2, v3, v4, v5}<br><br># Arestas (Edges)<br>A = {(v1, v2), (v1, v4), (v1, v5), (v2, v3), (v3, v5), (v4, v5), (v5, v1)}<br><br># Grafo<br>G = (V, A)</pre><p>Abaixo, você vê a representação visual desse grafo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/221/0*155WXvz138qgYNpq" /><figcaption>Imagem 5</figcaption></figure><h4>Vizinhança</h4><p>Com ele, podemos dar algumas definições. A primeira definição é de <strong>relação de vizinhança ou adjacência</strong>. Dois vértices são considerados vizinhos se existe uma aresta que os conecta.</p><h4>Passeio, Caminho e Ciclos</h4><p>Além disso, chamamos de <strong>passeio </strong>(walk) uma trajetória que percorre os vértices e as arestas do grafo, seguindo as conexões entre eles, onde cada aresta na sequência é adjacente à anterior.</p><p>Usando o grafo da Imagem 5, um possível passeio seria (V1, V4, V5, V1, V2).</p><p>Já um <strong>caminho</strong> (path), é um passeio onde nenhum vértice (ou aresta, depende de algumas definições) se repete. O passeio acima não é um caminho, porque V1 é visitado mais de uma vez.</p><p>Se tivermos o passeio (V1, V4, V5, V1), poderíamos denominar de <strong>ciclo</strong>, visto que o vértice de início é o mesmo vértice final. Caso o passeio passasse por todos os vértices do grafo uma única vez (exceto o vértice de início e fim) e fosse um ciclo, chamaríamos de <strong>ciclo hamiltoniano</strong>.</p><h4>Grau e Ordem</h4><p>Alguns conceitos importantes também são o grau e a ordem de um grafo. A ordem é bem tranquila: <strong>é a quantidade de vértices que ele tem</strong>. O grafo da Imagem 5 tem ordem 5, por exemplo, porque possui 5 vértices.</p><p>Agora, quando falamos de grau, estamos olhando para cada vértice específico, isto é, falamos o grau do vértice. O grau é <strong>a quantidade de arestas que tocam o vértice.</strong></p><p>Se for um grafo direcionado, falamos <strong>grau de entrada e grau de saída</strong>. O vértice 1 (V1) da Imagem 5 possui 3 graus de saída e 1 grau de entrada, totalizando grau 4 (3 + 1).</p><p>Quando temos um laço, como o vértice 4 da imagem 4, temos 2 graus de entrada e 1 de saída, totalizando grau 3 (2 + 1). Isso porque o laço conta como saída e entrada ao mesmo tempo (sai e entra no mesmo vértice).</p><h4>Conectividade</h4><p>Um grafo é dito <strong>conexo</strong> se, para cada par distinto no grafo, existe pelo menos um caminho que os conecta. Note que não necessariamente deve haver uma ARESTA, mas sim um caminho. Ou seja, partindo de um vértice, podemos chegar em todos os outros.</p><p>E aí abre margem para duas sub definições: <strong>fortemente e fracamente conexos</strong>.</p><p>O grafo direcionado da Imagem 6 é dito <strong>fortemente conexo</strong> porque, partindo de qualquer vértice do grafo, é possível chegar em qualquer outro vértice.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/163/0*zcr-00bN6OLc7OZw" /><figcaption>Imagem 6</figcaption></figure><p>Já o grafo direcionado da Imagem 7 é dito <strong>fracamente conexo</strong> porque, se ignorarmos a direção das arestas, ele é conexo. Note que não ignorando a direção, não podemos chegar no vértice E partindo do vértice H, por exemplo. Porém, se ignorarmos, ele é conexo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/229/0*rYCSQpPiLkSdFuDO" /><figcaption>Imagem 7</figcaption></figure><h3>Casos Particulares</h3><p>Provavelmente, você notou alguma semelhança dos grafos com um algoritmo bem famoso no mundo da ciência de dados: a árvore de decisão!</p><p>De forma mais geral, uma árvore é um caso particular de um grafo direcionado. Se aplicarmos uma restrição onde um vértice pode ter no máximo um pai, temos o resultado na Imagem 8.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/131/1*mimn82Zjq0J8bt19bZFApA.png" /><figcaption>Imagem 8</figcaption></figure><p>Perceba que é uma árvore (pela definição, uma árvore é uma estrutura hierárquica que consiste de vértices conectados por arestas), mas não a árvore de decisão que estamos acostumados a ver como resultado na scikit-learn, como mostra a Imagem 9.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/0*eubdNjGqh3V8PQr-.png" /><figcaption>Imagem 9</figcaption></figure><p>Note que a árvore de decisão da scikit-learn é um grafo onde cada vértice possui no máximo 1 pai E no exatamente 2 filhos. Isso caracteriza uma árvore binária.</p><p>Além das árvores, temos outras estruturas como linked-lists (listas encadeadas) que podem ser representadas por um grafo, mas isso fica para um próximo papo.</p><h3>Representações de Um Grafo</h3><p>Como vou falar aqui da parte prática também, é importantíssimo sabermos como representar um grafo no computador. E já vou adiantar: há diversas maneiras de fazer isso. Entretanto, vou focar em três principais:</p><ul><li>Matrizes</li><li>Matrizes de Adjacência</li><li>Listas de Adjacência</li></ul><h4>Matrizes</h4><p>Bom, acho que todos nós sabemos o que é uma matriz, certo? Só para recapitular, é uma estrutura bidimensional com linhas e colunas. Vou criar uma matriz de 0’s e 1’s com o código em Python abaixo, depois representar isso em uma imagem, na Imagem 10.</p><pre># Matriz<br>matriz = [<br>    [0, 0, 0, 1],<br>    [1, 1, 0, 0],<br>    [0, 0, 1, 0],<br>    [1, 0, 0, 0]<br>]</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*4yy5bt2DcqdBaZLp.png" /><figcaption>Imagem 10</figcaption></figure><p>Aqui, vamos imaginar que todo elemento que for igual a zero está “livre” e todo elemento que for igual a um está “bloqueado”.</p><p>“Como assim, Anwar? Bloqueado?”</p><p>Sei que pode parecer confuso, então vou dar um exemplo. Note que o caminho verde, seguido pela Imagem 11, é permitido, porque não passa em nenhuma posição bloqueada, ou seja, com algum valor 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/648/1*sZICbJZ67XvahGMZeNZe-A.png" /><figcaption>Imagem 11</figcaption></figure><p>Já na Imagem 12, vemos que esse caminho em vermelho não pode acontecer, visto que estamos passando por um caminho bloqueado!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/714/1*NZUzHmuBxI8DXcetHpWfqw.png" /><figcaption>Imagem 12</figcaption></figure><p>Aqui, podemos entender que cada elemento pode ser representado por matriz[i][j], onde <em>i</em> é o índice da linha e <em>j</em> é o índice da coluna. Ou seja, o elemento matriz[3][0] = 1, visto que o elemento da 4º linha (i + 1 = 3 + 1 = 4) e da 1º coluna (j + 1 = 0 + 1 = 1) é igual a 1.</p><p>E o que isso tem a ver com vértices? Ora, pense que cada zero da nossa matriz é um vértice e podemos nos mover para cima, para baixo, para a direita e para a esquerda. Note na Imagem 13 a representação, em forma de um grado não direcionado, da nossa matriz anterior.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/347/1*zXDxUcLj3co_K5uFfhibww.png" /><figcaption>Imagem 13</figcaption></figure><h4>Matriz de Adjacência</h4><p>A matriz de adjacência é também, como o próprio nome diz, uma matriz, mas aqui os índices representam os próprios vértices!</p><p>Vamos retomar ao exemplo da Imagem 6, mostrada novamente abaixo, com sua matriz de adjacência ao lado direito da Imagem 14. Note que temos 4 vértices, logo nossa matriz terá exatamente 4 linhas e 4 colunas, já que os índices indicam cada um dos vértices.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/807/1*AQFrQf51F4mkl1u_ipXqrg.png" /><figcaption>Imagem 14</figcaption></figure><p>O que cada 1&#39;s e 0&#39;s significam agora? Que está “bloqueado” e “livre”? Não. Esqueça isso. Agora, temos um significado muito maior e mais informativo.</p><p>Como disse, cada linha e coluna representa um dos nós. Nesse caso, a linha e coluna de índice 0 representam o nó A, a linha e coluna de índice 1 representam o nó B, a linha e coluna de índice 2 representam o nó C e por aí vai.</p><p>Quando temos que o elemento da 1º linha (índice 0), que representa o vértice A, e 4º coluna (índice 3), que representa o vértice D, tem o valor igual a 0, significa que não há uma aresta que sai de A e vai para B. Ou seja, o elemento matriz[0][3] = 0.</p><p>Entretanto, vemos que o elemento matriz[1][2] = 1. O que isso significa? Que há uma aresta que sai de B (índice 1 na linha) e chega em C (índice 2 na coluna).</p><p>Ou seja, se matriz[<em>vi</em>][<em>vj</em>] = 1, então existe um caminho que sai do vértice <em>v1 </em>e chega no vértice <em>vj</em>.</p><p>Note que se o grafo for não direcionado, se existe uma aresta saindo de <em>vi </em>para <em>vj, </em>então matriz[<em>vi</em>][<em>vj</em>] = 1 e matriz[<em>vj</em>][<em>vi</em>] = 1. Uma curiosidade: a matriz de adjacência, nesse caso, é simétrica.</p><p>Porém… como tudo na vida há vantagens e desvantagens, um caso particular onde utilizar a matriz de adjacência não é uma boa opção é quando não temos tantas arestas, visto que teríamos uma matriz com muitos 0’s de forma desnecessária.</p><p>De forma mais técnica, temos uma complexidade de espaço O(V²), onde V é o número de vértices. Mas vamos resolver isso.</p><p>Uma vantagem de utilizar a matriz de adjacência seria para casos onde a verificação de arestas entre dois vértices for uma operação comum, pois permite o acesso a um tempo constante.</p><h4>Lista de Adjacência</h4><p>A lista de adjacência é uma das formas mais comuns de representarmos um grafo. Basicamente, podemos criar uma classe com dois atributos: valor e vizinhos. Observe o código abaixo:</p><pre># Classe para representar um vértice na lista de adjacência<br>class Vertice:<br>  def __init__(self, valor):<br>    self.valor = valor<br>    self.vizinhos = list()</pre><p>Usando o mesmo grafo da Imagem 6, vamos representá-lo usando, agora, uma lista de adjacência. Note que, na Imagem 15, temos essa representação.</p><p>Quando temos poucas arestas, representar dessa forma pode ser muito mais eficiente em termos de espaço de memória, visto que estamos olhando apenas para os vértices que possuem uma ligação. Na matriz de adjacência, tínhamos um espaço na memória guardado até para as conexões que não existiam (quando os elementos eram 0).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/953/1*z5Oq31dd8Cw0cek0wNhoGg.png" /><figcaption>Imagem 15</figcaption></figure><p>Utilizar a Lista de Adjacência pode ser muito útil quando queremos explorar os vizinhos de um determinado vértice. E faremos muito isso no próximo artigo.</p><h3>Conclusão</h3><p>Aprendemos bastante coisa até aqui!</p><p>Espero que tenham gostado e fique tranquilo, porque teremos a parte 2 falando sobre métodos de busca DFS e BFS.</p><p>Até já, pessoal.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2252d4800a44" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Derivada is All You Need — Uma aplicação com o algoritmo do gradiente descendente]]></title>
            <link>https://medium.com/@anwarhermuche/derivada-is-all-you-need-uma-aplica%C3%A7%C3%A3o-com-o-algoritmo-do-gradiente-descendente-a29510e63cb4?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/a29510e63cb4</guid>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ciencia-de-dados]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Fri, 01 Mar 2024 00:11:10 GMT</pubDate>
            <atom:updated>2024-03-01T00:14:09.395Z</atom:updated>
            <content:encoded><![CDATA[<h3>Derivada Is All You Need — Uma aplicação com o algoritmo do gradiente descendente</h3><p>Fala, pessoal! Hoje, quero trazer um novo artigo sobre gradiente descendente. Acho que já deu para notar que esse algoritmo é o meu xodó, né?!</p><p>Entretanto, hoje quero trazer uma abordagem bem prática. Teremos muito código aqui e espero que você esteja pronto e com alguma IDE por perto.</p><p>Vamos começar!</p><h3>Introdução às Derivadas</h3><p>Vamos começar explicando o que são derivadas. Para isso, observe o código abaixo, onde eu crio uma parábola.</p><pre># Importando as bibliotecas<br>import numpy as np<br>import matplotlib.pyplot as plt<br><br># Gráfico da função y = x² - 4x + 8<br>x = np.arange(-6, 10.5, 0.5)<br>f = lambda x: x**2 - 4*x + 8<br><br>plt.plot(x, f(x))<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*i4hlxAQZz1LCwhGYl_7CMg.png" /><figcaption>Imagem 1: do autor</figcaption></figure><p>Vamos derivar a função?</p><p>Lembre-se de que encontrar a derivada da função em um determinado ponto R significa encontrar o quanto a função tem o seu valor alterado por uma pequena variação no x, ou seja, <strong>qual a inclinação da reta tangente ao ponto</strong>. E uma reta tangente a um ponto significa que essa reta toca apenas 1 ponto no gráfico, que é o ponto tangente.</p><p>Derivando a função para qualquer ponto dela (podemos fazer isso, porque ela é contínua), chegamos na expressão abaixo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4Vps1EkGLFcANJWLnZ7tzA.png" /><figcaption>Imagem 2: do autor</figcaption></figure><p>Perceba que a inclinação da reta tangente ao ponto x = 6 é igual a 8 (2*6 — 4 = 8). Vamos representar graficamente.</p><pre># Calculando o coeficiente angular e linear da reta tangente<br># f(6) = 8*6 + b<br># 20 = 48 + b<br># b = -28<br>f_linha = lambda x: 8*x - 28<br><br># Reta tangente ao ponto x = 6<br>x = np.arange(-6, 10.5, 0.5)<br>f = lambda x: x**2 - 4*x + 8<br>new_x = np.arange(0, 12, 0.5)<br><br>plt.plot(x, f(x))<br>plt.plot(new_x, f_linha(new_x))<br>plt.plot(6, 20, marker = &#39;o&#39;, color = &#39;red&#39;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/555/1*sVoX5pP4_H8KfFCemvaatQ.png" /><figcaption>Imagem 3: do autor</figcaption></figure><p>Pelo gráfico, parece que a reta toca outros pontos. Mas, acredite em mim, ela toca apenas o ponto onde x = 6. E por que estou dizendo isso?</p><p>Porque se deslizarmos esse ponto vermelho para a esquerda, o coeficiente angular da reta laranja vai se reduzindo cada vez mais. Duvida? Observe os gráficos abaixo.</p><pre>for k in np.arange(4, 0, -1):<br>    a = 2*k - 4 # coeficiente angular<br>    bias = f(k) - a*k # isso é para calcular aquele b da 3º célula de código<br>    f_linha = lambda x: x*a + bias<br>    new_x = np.arange(k - 6, k + 6, 0.5)<br>    <br>    plt.plot(x, f(x))<br>    plt.plot(new_x, f_linha(new_x))<br>    plt.plot(k, f(k), marker = &#39;o&#39;, color = &#39;red&#39;)<br>    plt.title(f&quot;Em x = {k}, a derivada é igual a {a}&quot;)<br>    plt.show();</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/555/1*LAMHqAtkZuT630_zBqv5lA.png" /><figcaption>Imagem 4: do autor</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/555/1*_jDWbMMY3jOygL3w4Uc1jA.png" /><figcaption>Imagem 5: do autor</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*S6p92izMNCtOIRQkB9khww.png" /><figcaption>Imagem 6: do autor</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*8BazxXstYrr0rqcSJd1Q1g.png" /><figcaption>Imagem 7: do autor</figcaption></figure><p>Notou que em x = 2 a derivada é 0? <strong>Isso significa que no ponto x = 2 a inclinação da reta tangente é igual a 0</strong> (e isso é verdade, visto que a reta é paralela ao eixo x).</p><p><strong>Perceba que a derivada ser zero significa que não há variação no ponto</strong> <strong>específico, podendo ser um mínimo, um máximo ou um ponto de inflexão</strong>. Se aumentamos o valor de x, note que o valor da derivada aumenta, indicando que há variação crescente naquele ponto. Se reduzimos o valor de x, note que o valor da derivada reduz, indicando que há uma variação decrescente naquele ponto. Logo, o ponto de derivada zero deve ser algum mínimo, máximo ou um ponto de inflexão.</p><p>E todas essas contas servem para entendermos como um algoritmo de Machine Learning funciona internamente para encontrar os melhores parâmetros que reduzem o seu erro.</p><p>Entretanto, essas funções utilizadas em Machine Learning possuem mais de uma variável. No exemplo acima tinha apenas uma. Cada coluna de um dataset se tornará uma variável, matematicamente falando. Então, o que fazer nesse cenário?</p><h3>Funções de 2 variáveis</h3><pre># Definindo as variáveis<br>x = 1<br>y = 1<br>a = (y - (2*x + 4))**2<br>print(a)<br># a = 25</pre><p>Note que a variável ‘a’ é uma função de x e y. O que isso quer dizer? Que quando alteramos o valor de ‘x’ ou de ‘y’, alteramos também o valor de ‘a’.</p><p>Então, o que acontece se variamos ‘x’ ou ‘y’ bem pouco? Como ‘a’ é afetado? Como estamos interessados na variação em um ponto bem específico da função, temos que derivar ‘a’, mas agora temos duas variáveis e não uma como anteriormente. Então, vamos utilizar um conceito chamado de derivada parcial.</p><p>A derivada parcial é utilizada para derivar funções com mais de uma variável, como é o nosso caso agora. A notação da derivada parcial de ‘a’ em relação a ‘x’ é:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/139/1*XuVYMI9S46_WFtdeDrZePg.png" /><figcaption>Imagem 8: do autor</figcaption></figure><p>Vamos realizar as derivadas.</p><pre># Definindo x e y<br>x, y = 1, 1<br><br># Derivando &#39;a&#39; em relação a &#39;x&#39;<br>a_linha_x = 8*x - 4*y + 16  # No ponto x = 1 e y = 1, a_linha_x = 20<br><br># Derivando &#39;a&#39; em relação a &#39;y&#39;<br>a_linha_y = 2*y - 4*x - 8   # No ponto x = 1 e y = 1, a_linha_y = -10<br><br># Verificando a derivada em relação a x com a definição utilizando limites (f(x + h) - f(x))/h, para h tendendo a 0<br>funcao_a = lambda x, y: (y - (2*x + 4))**2<br>h = 0.001<br>derivada = (funcao_a(x + h, y) - funcao_a(x, y))/h<br>print(f&quot;O valor da derivada de &#39;a&#39; em relação a &#39;x&#39; para h = {h} é {derivada}&quot;)<br><br># Verificando a derivada em relação a y com a definição utilizando limites (f(x + h) - f(x))/h, para h tendendo a 0<br>funcao_a = lambda x, y: (y - (2*x + 4))**2<br>h = 0.001<br>derivada = (funcao_a(x, y + h) - funcao_a(x, y))/h<br>print(f&quot;O valor da derivada de &#39;a&#39; em relação a &#39;y&#39; para h = {h} é {derivada}&quot;)<br><br># O valor da derivada de &#39;a&#39; em relação a &#39;x&#39; para h = 0.001 é 20.00399999999658<br># O valor da derivada de &#39;a&#39; em relação a &#39;y&#39; para h = 0.001 é -9.99899999999343</pre><p>Note que os valores utilizando a definição formal de limites confirma o que fizemos manualmente. O que, claro, era esperado.</p><p>E como encontramos o valor de ‘x’ e ‘y’ que minimizam a função ‘a’?</p><p>Lembre-se de que as derivadas de ‘a’ em relação a ‘x’ e ‘y’ foram, respectivamente, 20 e -10, certo? E a = 25 para x = 1 e y = 1. O que acontece se multiplicarmos os resultados da derivada por um número pequeno, tipo 0.001, e subtrairmos dos valores originais de x e y? Vamos testar.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-r5oGgZYgYJMDnFhjJJx7A.png" /><figcaption>Imagem 9: do autor</figcaption></figure><p>Excelente! Com esses novos valores de x e y, vamos recalcular o valor de ‘a’, que resulta em, aproximadamente, 24.5025. Note que o valor reduziu! Vamos repetir o processo? Lembre-se de calcular o valor da derivada nos novos pontos!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2n9Q4tPZexGH-9J_5t_b-Q.png" /><figcaption>Imagem 10: do autor</figcaption></figure><p>Calculando o novo valor de ‘a’ para esses novos valores de ‘x’ e ‘y’, temos a = 24.014831643049. Reduzimos ainda mais o resultado da nossa função ‘a’.</p><p>Note que se formos fazer dessa forma, passo a passo, um por um, vamos demorar uma eternidade. Então, o que acha de implementarmos um loop em python que execute essa tarefa 10 mil vezes? Vamos ver como os valores de x e y ficam a cada iteração.</p><pre>x, y = 1, 1<br>n_iter = 10000<br>valores_iteracoes = {&#39;x&#39;: list(), &#39;y&#39;: list(), &#39;a&#39;: list()}<br>for iteracao in range(n_iter):<br>    valores_iteracoes[&#39;x&#39;].append(x)<br>    valores_iteracoes[&#39;y&#39;].append(y)<br>    valor_a = funcao_a(x, y)<br>    valores_iteracoes[&#39;a&#39;].append(valor_a)<br>    <br>    x = x - 0.001*(8*x - 4*y + 16)<br>    y = y - 0.001*(2*y - 4*x - 8)</pre><pre># Plotando em um gráfico o valor de &#39;c&#39; ao longo das iterações<br>plt.title(&quot;Valor de &#39;a&#39; ao longo das iterações&quot;)<br>plt.plot(range(n_iter), valores_iteracoes[&#39;a&#39;])<br>plt.xlabel(&#39;Iteração&#39;)<br>plt.ylabel(&#39;a&#39;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/563/1*9zNuNeLV459Q2lQrUlxg9A.png" /><figcaption>Imagem 11: do autor</figcaption></figure><p>Perceba que nas primeiras iterações houve uma queda significativa do valor de ‘a’! Depois, foi se reduzindo lentamente, chegando em um valor mínimo de 0 para x = -1.0032051282051175 e y = 1.9935897435897372.</p><p>Vamos ver como ‘x’ e ‘y’ variaram ao longo das iterações.</p><pre># Criando dois subplots, lado a lado<br>fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4))<br><br># Gráfico de &#39;x&#39;<br>ax1.plot(range(n_iter), valores_iteracoes[&#39;x&#39;])<br>ax1.set_title(&quot;Valor de &#39;x&#39; ao longo das iterações&quot;)<br>ax1.set_xlabel(&#39;Iteração&#39;)<br>ax1.set_ylabel(&#39;x&#39;)<br><br># Gráfico de &#39;y&#39;<br>ax2.plot(range(n_iter), valores_iteracoes[&#39;y&#39;])<br>ax2.set_title(&quot;Valor de &#39;y&#39; ao longo das iterações&quot;)<br>ax2.set_xlabel(&#39;Iteração&#39;)<br>ax2.set_ylabel(&#39;y&#39;)<br><br># Mostrando os gráficos<br>plt.tight_layout()<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pxgiWbch16wDVaeoyDlq3w.png" /><figcaption>Imagem 12: do autor</figcaption></figure><p>O que aconteceu é que ‘x’ reduziu ao longo das iterações e ‘y’ aumentou! Por que isso acontece?</p><p>Para saber onde teremos um mínimo, temos que derivar a nossa função e igualar a zero. Encontramos que a derivada parcial de ‘a’ em relação a ‘x’ é 8x — 4y + 16 e a derivada parcial a ‘a’ em relação ‘y’ é 2y — 4x — 8. Lembra que, no ponto mínimo, a derivada é igual a zero? Então, vamos igualar essas duas expressões a zero e montar um sistema linear:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZGM00Btq-TYjthJVZlEgrA.png" /><figcaption>Imagem 13: do autor</figcaption></figure><p>Resolvendo o sistema linear, chegamos que x = y/2 — 2. Perceba que encontramos os valores mínimos x = -1 e y = 2. Quando substituimos y = 2 na equação, chegamos exatamente em x = -1. Sendo assim, temos infinitos pontos mínimos, todos descritos pela equação da reta x = y/2 — 2</p><p>Vamos visualizar a superfície em três dimensões de ‘a’ para cada valor de ‘x’ e ‘y’, a reta dos mínimos e o ponto mínimo em x = -1 e y = 2.</p><pre># Importando o plotly<br>import plotly.graph_objects as go<br><br># Definindo os intervalos para x e y<br>x_range = np.linspace(-10, 10, 100)<br>y_range = np.linspace(-10, 10, 100)<br><br># Criando uma malha de pontos<br>x, y = np.meshgrid(x_range, y_range)<br><br># Calculando os valores de &#39;a&#39; para cada ponto (x, y)<br>a_values = (y - (2*x + 4))**2<br><br># Coordenadas do ponto mínimo para y = 2 (conforme a fórmula x = y/2 - 2)<br>x_min = 2 / 2 - 2<br>y_min = 2<br>z_min = (y_min - (2*x_min + 4))**2  # Calculando &#39;a&#39; para o ponto mínimo<br><br># Criando o gráfico com Plotly<br>fig = go.Figure(data=[go.Surface(z=a_values, x=x, y=y)])<br><br># Adicionando um marcador no ponto mínimo<br>fig.add_trace(go.Scatter3d(x=[x_min], y=[y_min], z=[z_min],<br>                           mode=&#39;markers&#39;, marker=dict(size=5, color=&#39;red&#39;),<br>                           name=&#39;Ponto Mínimo&#39;))<br><br># Adicionando uma reta com os pontos mínimos (usando a relação x = y/2 - 2)<br>y_line = np.linspace(-10, 10, 100)<br>x_line = y_line / 2 - 2<br>z_line = (y_line - (2*x_line + 4))**2  # &#39;a&#39; para a reta dos mínimos<br><br>fig.add_trace(go.Scatter3d(x=x_line, y=y_line, z=z_line,<br>                           mode=&#39;lines&#39;, line=dict(color=&#39;yellow&#39;, width=2),<br>                           name=&#39;Reta dos Mínimos&#39;))<br><br># Atualizando o layout do gráfico<br>fig.update_layout(title=&#39;Superfície de $a = (y - (2x + 4))^2$ com Ponto Mínimo e Reta dos Mínimos&#39;, autosize=False,<br>                  width=800, height=600,<br>                  margin=dict(l=65, r=50, b=65, t=90))<br><br># Mostrando o gráfico<br>fig.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/655/1*O4XuZ1qeYoKlQ8N7KeIuyw.png" /><figcaption>Imagem 14: do autor</figcaption></figure><p>Notou o que acabamos de fazer? Partimos de uma equação e chegamos no ponto mínimo dela utilizando apenas matemática!</p><h3>Aplicação em Machine Learning</h3><p>E quando estamos falando de Machine Learning, isso é excelente para encontrarmos os parâmetros ideiais (x e y) de uma função que minimizam uma <a href="https://medium.com/@anwarhermuche/fun%C3%A7%C3%B5es-de-custo-uma-breve-introdu%C3%A7%C3%A3o-5a472599ac1e">função de custo</a>. E se você não sabe o que é uma função de custo, basicamente é uma função que mede o quanto estamos errando em um modelo de Machine Learning.</p><p>Para ficar fácil visualmente, vou dar um exemplo utilizando a função de custo MSE e uma Regressão Linear. A função de custo MSE é dada por:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fY4-8G1OkTsk4oJ49JdoyA.png" /><figcaption>Imagem 15: do autor</figcaption></figure><p>Aqui, ‘r’ é o nosso valor real. Se estamos trabalhando em um problema prevendo o preço de uma casa, ‘r’ seria o valor real daquela casa. O termo ‘f’ é o valor da nossa feature. Se estamos utilizando o número de metros quadrados para prever o valor da casa, esse número seria a nossa feature. E, novamente, ‘x’ e ‘y’ são os parâmetros que queremos encontrar para minimizar essa função. Pra finalizar, ‘m’ é o número de instâncias (linhas/exemplos do dataset).</p><p>Como estamos trabalhando com a função de custo, que mede o quão errada nossas previsões estão, faz muito sentido minimizar! Porque, se minimizarmos, significa que estamos minimizando a função de custo.</p><p>Vamos repetir o processo anterior de derivadas partindo de x = 1 e y = 1. Agora, observe abaixo o nosso exemplo da regressão linear prevendo o valor de uma casa a partir do número de metros quadrados.</p><pre># Criando os dados<br>np.random.seed(0)<br>metros_quadrados = np.arange(40, 320, 0.5)<br>valor_casa = 4*metros_quadrados + 8 + np.random.randn(len(metros_quadrados))*100<br><br># Visualizando os dados<br>plt.scatter(metros_quadrados, valor_casa)<br>plt.title(&#39;Relação entre o número de metros quadrados e o valor da casa&#39;)<br>plt.xlabel(&#39;Metros Quadrados&#39;)<br>plt.ylabel(&#39;Valor da Casa&#39;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*EHI2jhBs00QzsvJhvCsp3w.png" /><figcaption>Imagem 16: do autor</figcaption></figure><p>Viu como nossos dados possuem uma correlação positiva? O nosso objetivo aqui é encontrar uma reta que melhor se encaixe nesses dados! Vou começar com uma reta<em> </em><strong><em>valor_casa = 1*metros_quadrados + 1</em></strong>.</p><pre># Visualizando os dados<br>plt.scatter(metros_quadrados, valor_casa)<br>plt.plot(metros_quadrados, metros_quadrados + 1, color = &#39;red&#39;)<br>plt.title(&#39;Relação entre o número de metros quadrados e o valor da casa&#39;)<br>plt.xlabel(&#39;Metros Quadrados&#39;)<br>plt.ylabel(&#39;Valor da Casa&#39;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*9s3AXTafaKUsuoVLwTbA2w.png" /><figcaption>Imagem 17: do autor</figcaption></figure><p>Note que essa reta está muito mal ajustada! Nós podemos calcular o ‘erro de ajuste’ da reta utilizando o MSE. Aplicando nesta reta, temos o valor abaixo.</p><pre># Calculando o MSE<br>funcao_mse = lambda x, y: np.mean((valor_casa - (x*metros_quadrados + y))**2)<br>funcao_mse(1, 1)<br><br># 358764.93074618373</pre><p>O erro foi de 358.764. A unidade desse erro depende da unidade do valor da casa. É em dólares? Reais? Vamos supor que seja em reais. Dessa forma, o erro foi de 358.764 reais². Pois, é: reais ao quadrado. Essa unidade do MSE não permite uma interpretação tão boa, mas nosso foco não é esse agora.</p><p>Para encontrar a melhor reta, ou seja, aquela cujos parâmetros ‘x’ e ‘y’ minimizam o nosso MSE, vamos utilizar derivadas!</p><pre># Definindo x e y<br>x, y = 1, 1<br><br># Função para calcular o MSE<br>funcao_mse = lambda x, y: np.mean((valor_casa - (x * metros_quadrados + y)) ** 2)<br><br># Derivada do &#39;MSE&#39; em relação a &#39;x&#39;<br>mse_linha_x = np.mean(-2 * metros_quadrados * (valor_casa - (x * metros_quadrados + y)))<br><br># Derivada do &#39;MSE&#39; em relação a &#39;y&#39;<br>mse_linha_y = np.mean(-2 * (valor_casa - (x * metros_quadrados + y)))<br><br># Verificando a derivada em relação a x com a definição utilizando limites (f(x + h) - f(x)) / h, para h tendendo a 0<br>h = 0.001<br>derivada_x = (funcao_mse(x + h, y) - funcao_mse(x, y)) / h<br>print(f&quot;O valor da derivada de &#39;mse&#39; em relação a &#39;x&#39; para h = {h} é {derivada_x}&quot;)<br><br># Verificando a derivada em relação a y com a definição utilizando limites (f(y + h) - f(y)) / h, para h tendendo a 0<br>derivada_y = (funcao_mse(x, y + h) - funcao_mse(x, y)) / h<br>print(f&quot;O valor da derivada de &#39;mse&#39; em relação a &#39;y&#39; para h = {h} é {derivada_y}&quot;)<br><br># O valor da derivada de &#39;mse&#39; em relação a &#39;x&#39; para h = 0.001 é -232690.36844617222<br># O valor da derivada de &#39;mse&#39; em relação a &#39;y&#39; para h = 0.001 é -1083.759343076963</pre><p>Vamos, agora, fazer aquelas iterações!</p><pre>x, y = 1, 1  <br>n_iter = 1000  <br>valores_iteracoes = {&#39;x&#39;: list(), &#39;y&#39;: list(), &#39;mse&#39;: list()} <br>for iteracao in range(n_iter):<br>    valores_iteracoes[&#39;x&#39;].append(x)<br>    valores_iteracoes[&#39;y&#39;].append(y)<br>    valor_mse = funcao_mse(x, y) <br>    valores_iteracoes[&#39;mse&#39;].append(valor_mse)<br>    <br>    x = x - 0.00001  * np.mean(-2 * metros_quadrados * (valor_casa - (x * metros_quadrados + y)))<br>    y = y - 0.00001 * np.mean(-2 * (valor_casa - (x * metros_quadrados + y)))</pre><p>Note que eu reduzi a learning rate, pois o algoritmo estava divergindo. Fiz essa redução porque a escala dos dados é maior e, consequentemente, a learning rate que utilizamos no outro exemplo com dados de menor escala não é suficiente.</p><p>Teste o valor anterior de 0.001 e veja o que acontece.</p><pre># Plotando em um gráfico o valor de &#39;c&#39; ao longo das iterações<br>plt.title(&quot;Valor de &#39;MSE&#39; ao longo das iterações&quot;)<br>plt.plot(range(n_iter), valores_iteracoes[&#39;mse&#39;])<br>plt.xlabel(&#39;Iteração&#39;)<br>plt.ylabel(&#39;mse&#39;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*TmL9vBGBfu_U1zSojwYkQA.png" /><figcaption>Imagem 18: do autor</figcaption></figure><p>Note que já nas primeiras iterações o algoritmo foi de um custo altíssimo para um custo muuuito menor. Depois disso, foi reduzindo bem aos poucos. Isso significa que ele convergiu para um mínimo!</p><p>Vamos analisar, novamente, o comportamento dos parâmetros ao longo das iterações.</p><pre># Criando dois subplots, lado a lado<br>fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4))<br><br># Gráfico de &#39;x&#39;<br>ax1.plot(range(n_iter), valores_iteracoes[&#39;x&#39;])<br>ax1.set_title(&quot;Valor de &#39;x&#39; ao longo das iterações&quot;)<br>ax1.set_xlabel(&#39;Iteração&#39;)<br>ax1.set_ylabel(&#39;x&#39;)<br><br># Gráfico de &#39;y&#39;<br>ax2.plot(range(n_iter), valores_iteracoes[&#39;y&#39;])<br>ax2.set_title(&quot;Valor de &#39;y&#39; ao longo das iterações&quot;)<br>ax2.set_xlabel(&#39;Iteração&#39;)<br>ax2.set_ylabel(&#39;y&#39;)<br><br># Mostrando os gráficos<br>plt.tight_layout()<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*joUGHeUdfnEz7BzfGQJadA.png" /><figcaption>Imagem 19: do autor</figcaption></figure><p>Perceba que X se estabilizou muito próximo do 4 e y muito próximo do 1.07.</p><p>Será que tem alguma forma de a gente ver o caminho de forma 3d dos parâmetros, com o resultado do MSE? Tem! Observe o código e o gráfico abaixo:</p><pre># Plotando a evolução de x, y e MSE ao longo das iterações<br>fig = go.Figure()<br><br># Adicionando a trajetória de x e y<br>fig.add_trace(go.Scatter3d(x=valores_iteracoes[&#39;x&#39;], y=valores_iteracoes[&#39;y&#39;], z=valores_iteracoes[&#39;mse&#39;],<br>                           mode=&#39;markers+lines&#39;, marker=dict(size=5, color=&#39;blue&#39;), name=&#39;Trajetória de (x, y)&#39;))<br><br># Marcando o ponto inicial<br>fig.add_trace(go.Scatter3d(x=[valores_iteracoes[&#39;x&#39;][0]], y=[valores_iteracoes[&#39;y&#39;][0]], z=[valores_iteracoes[&#39;mse&#39;][0]],<br>                           mode=&#39;markers&#39;, marker=dict(size=8, color=&#39;green&#39;), name=&#39;Ponto Inicial&#39;))<br><br># Marcando o ponto final<br>fig.add_trace(go.Scatter3d(x=[valores_iteracoes[&#39;x&#39;][-1]], y=[valores_iteracoes[&#39;y&#39;][-1]], z=[valores_iteracoes[&#39;mse&#39;][-1]],<br>                           mode=&#39;markers&#39;, marker=dict(size=8, color=&#39;red&#39;), name=&#39;Ponto Final&#39;))<br><br># Atualizando o layout do gráfico<br>fig.update_layout(title=&#39;Evolução dos Parâmetros x e y com MSE ao longo das Iterações&#39;, autosize=False,<br>                  width=800, height=600,<br>                  scene=dict(<br>                      xaxis_title=&#39;x&#39;,<br>                      yaxis_title=&#39;y&#39;,<br>                      zaxis_title=&#39;MSE&#39;),<br>                  margin=dict(l=65, r=50, b=65, t=90))<br><br># Mostrando o gráfico<br>fig.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/914/1*lnjxhDREbLEmaFeyjmokkA.png" /><figcaption>Imagem 20: do autor</figcaption></figure><p>Note que o valor de X cresceu rapidamente, junto com a redução do MSE. Praticamente nas primeiras 10~20 iterações o algoritmo já havia alcançado um valor bem próximo do valor final para o parâmetro x.</p><p>Além disso, o MSE começou perto de 350 mil e se reduziu para 10 mil na milésima iteração! Reduziu bastante. Os parâmetros também foram corretamente ajustados, sendo que x ficou igual a 3.99 e y igual a 1.07.</p><p>Vamos ver a superfície e o ponto mínimo?</p><pre># Gerando dados hipotéticos para X, Y e MSE<br>x_range = np.linspace(-10, 10, 560)<br>y_range = np.linspace(-10, 10, 560)<br>x, y = np.meshgrid(x_range, y_range)<br><br># Definindo uma função hipotética para o MSE baseada em x e y para visualização<br>mse_values = (valor_casa - (x * metros_quadrados + y)) ** 2<br><br># Coordenadas do ponto mínimo hipotético da função MSE<br>x_min, y_min = 3.9, 1.07  # Assumindo o mínimo no centro para ilustração<br>z_min = np.mean((valor_casa - (x_min * metros_quadrados + y_min)) ** 2)<br><br># Criando o gráfico com Plotly<br>fig = go.Figure(data=[go.Surface(z=mse_values, x=x, y=y, colorscale=&#39;Viridis&#39;)])<br><br># Adicionando um marcador no ponto mínimo<br>fig.add_trace(go.Scatter3d(x=[x_min], y=[y_min], z=[z_min],<br>                           mode=&#39;markers&#39;, marker=dict(size=5, color=&#39;red&#39;),<br>                           name=&#39;Ponto Mínimo&#39;))<br><br># Atualizando o layout do gráfico<br>fig.update_layout(title=&#39;Superfície do MSE com Ponto Mínimo&#39;, autosize=False,<br>                  scene=dict(<br>                      xaxis_title=&#39;X&#39;,<br>                      yaxis_title=&#39;Y&#39;,<br>                      zaxis_title=&#39;MSE&#39;),<br>                  width=800, height=600,<br>                  margin=dict(l=65, r=50, b=65, t=90))<br><br># Mostrando o gráfico<br>fig.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/761/1*eeMenMcDf-RbI3BdBGmOoA.png" /><figcaption>Imagem 21: do autor</figcaption></figure><p>Note que chegamos no ponto mínimo dessa função. E como será que nossa reta fica com x = 3.99 e y = 1.07?</p><pre># Visualizando os dados<br>plt.scatter(metros_quadrados, valor_casa)<br>plt.plot(metros_quadrados, 3.99*metros_quadrados + 1.07, color = &#39;red&#39;)<br>plt.title(&#39;Relação entre o número de metros quadrados e o valor da casa&#39;)<br>plt.xlabel(&#39;Metros Quadrados&#39;)<br>plt.ylabel(&#39;Valor da Casa&#39;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*AIoCehyZBy31DNBeGzFZFw.png" /><figcaption>Imagem 22: do autor</figcaption></figure><p>Viu? Se ajustou muito bem aos nossos dados! Esse é o poder da derivada e sua aplicação em Machine Learning.</p><h3>Conclusão</h3><p>Pronto, vimos uma boa parte sobre as derivadas e como elas são extremamente úteis no contexto de Machine Learning. Acho muito válido ficar por dentro da teoria matemática por trás dos modelos para não ficar trabalhando como uma caixa preta, isto é, sem saber o que realmente se passa durante o processamento dos dados.</p><p>Espero que com esse artigo eu possa ter esclarecido um pouco sobre as derivadas.</p><p>Até já, pessoal</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a29510e63cb4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Tutorial de Clusterização De Dados Categóricos e Mistos com K-Prototypes]]></title>
            <link>https://medium.com/@anwarhermuche/tutorial-de-clusteriza%C3%A7%C3%A3o-de-dados-categ%C3%B3ricos-e-mistos-com-k-prototypes-98a2115a6b9f?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/98a2115a6b9f</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ciencia-de-dados]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[clustering]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Wed, 17 Jan 2024 18:07:09 GMT</pubDate>
            <atom:updated>2024-01-17T18:07:09.969Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*11RPLim4LA7Arf3E42_Yuw.png" /><figcaption>Imagem 1: <a href="https://awari.com.br/wp-content/uploads/2022/12/Qual-a-diferenca-entre-classificacao-e-clusterizacao-1024x310.png">https://awari.com.br/wp-content/uploads/2022/12/Qual-a-diferenca-entre-classificacao-e-clusterizacao-1024x310.png</a></figcaption></figure><p>Se existe uma coisa que eu gosto de fazer, é resolver problemas. Se tem um algoritmo que eu posso usar pra isso, melhor ainda. E é com essa pegada que eu vou abordar um dos algoritmos que mais gosto, que é o algoritmo de clusterização.</p><p>Além de te ensinar o que é e como fazer, vou mostrar uma forma de aplicar em um problema que encontramos em algumas empresas: o agrupamento de dados categóricos.</p><p>Eu vou começar explicando o que é um algoritmo de clusterização, qual é a sua importância e quando utilizá-lo. Depois, vou propor um desafio para que possamos aplicar um algoritmo de clusterização nele. Com tudo isso feito, vou apresentar uma forma de tratarmos dados categóricos para, de fato, resolvermos o problema proposto. Bora lá!</p><h3>Introdução à Clusterização de Dados</h3><h4>O que é Clusterização?</h4><p>O algoritmo que irei abordar hoje é o algoritmo de clusterização. Mas, afinal, o que é isso?</p><p>A clusterização (ou agrupamento) é o processo de particionar um conjunto de dados em subconjuntos, de tal forma que os elementos em um grupo sejam semelhantes uns aos outros e diferentes dos elementos de outros grupos.</p><p>Em outras palavras, a clusterização faz com que os elementos de um mesmo grupo se pareçam entre si, mas se diferenciem dos elementos dos outros grupos.</p><p>Para exemplificar, veja a imagem abaixo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*w4lAcpS9qEGJfoOx6u-edQ.png" /><figcaption>Imagem 2: Imagem do autor</figcaption></figure><p>Na imagem 2, temos um conjunto de dados que representam a renda e a idade de algumas pessoas. Se fôssemos classificá-las de acordo com a idade e a renda, poderíamos fazer a divisão que a imagem mostra: um grupo que contém as pessoas mais novas e com a menor renda, um que contém as pessoas mais novas e com a maior renda, um que contém as pessoas mais velhas e com a menor renda e, por fim, um que contém as pessoas mais velhas e com a maior renda. Note que as pessoas de um mesmo grupo se parecem entre si, mas são diferentes das pessoas dos outros grupos.</p><h4>Quando Utilizar?</h4><p>Agora, uma pergunta que muitos de vocês podem ter: <strong>quando eu devo utilizar um algoritmo de clusterização</strong>?</p><p>A resposta é simples: sempre que você quiser dividir um conjunto de dados em grupos que tenham características semelhantes e, ao mesmo tempo, características diferentes dos outros grupos.</p><p>Seja para tomada de decisão, para análise exploratória dos dados (AED), para segmentação de clientes, para recomendação de produtos, para análise de risco de crédito etc… as possibilidades são inúmeras.</p><p>Mas, em todas essas situações, há uma premissa: <strong>os dados devem ser semelhantes entre si e diferentes dos outros grupos</strong>. Por exemplo, no caso onde temos os dados de idade e renda das pessoas, a idade e a renda são características semelhantes entre si e diferentes dos outros grupos.</p><h4>O Objetivo de um Algoritmo de Clusterização</h4><p>Agora que já sabemos quando utilizar e o que é um algoritmo de clusterização, vamos falar sobre qual é o seu objetivo. Basicamente, podemos resumir o objetivo de um algoritmo de clusterização em 3 pontos:</p><ul><li>Agrupar os dados de acordo com a semelhança</li><li>Manter os grupos o mais diferente possível uns dos outros</li><li>Manter os grupos o mais similares possíveis dentro de si</li></ul><p>E é justamente esse equilíbrio entre a diferenciação entre os grupos e a semelhança dentro dos grupos que torna o problema de clusterização interessante.</p><p>Note que, na imagem que mostrei com a renda e a idade, há uma semelhança muito grande entre as pessoas de um mesmo grupo. E é justamente isso que o algoritmo faz de maneira automática, sem que precisemos especificar qual é a semelhança.</p><h3>Desafio do Uber</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WtSQyE1Xtx_eB72NHkFtpw.jpeg" /><figcaption>Imagem 3: <a href="https://eternisbe.vicoop.com/uploads/127496797_m_d04808a117.jpg">https://eternisbe.vicoop.com/uploads/127496797_m_d04808a117.jpg</a></figcaption></figure><p>Agora que já falamos sobre o conceito de clusterização e qual é o seu objetivo, vou propor um desafio que, acredito, que muitos de vocês já passaram.</p><p>O desafio é o seguinte: imagine que você trabalha para o Uber e a empresa te deu a missão de classificar os usuários do aplicativo de acordo com o tipo de viagem que eles mais costumam fazer, para que a empresa possa lançar um tipo de assinatura específica para esses usuários.</p><p>Porém, a empresa não quer que você faça uma pesquisa ativa com todos os usuários, para não influenciar nas respostas. Sendo assim, você tem que resolver esse problema utilizando os dados que a empresa já te disponibilizou. Abaixo, segue a tabela com os dados que a empresa te forneceu:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wIEz-wdovXS6sW7vGn4hGg.png" /><figcaption>Imagem 4: Imagem do autor</figcaption></figure><p>O desafio é interessante, não é? E, de fato, é um problema real que existem em algumas empresas. Note que não temos a informação do tipo de viagem que o usuário mais costuma fazer. E, para descobrirmos, podemos utilizar o conceito de clusterização.</p><p>Porém, temos um problema: a tabela é composta por dados categóricos e numéricos. E eu sei que muitos de vocês não sabem, mas a maioria dos algoritmos de clusterização só aceitam dados numéricos.</p><p>Então, como podemos resolver esse problema? Simples: com técnicas de pré-processamentos dos dados. E é isso que vou abordar agora.</p><h3>O Algoritmo K-Prototypes</h3><p>Quando falamos sobre algoritmos de clusterização, o primeiro tipo de algoritmo que muitas pessoas pensam é o algoritmo K-means. Realmente, ele é um dos algoritmos de clusterização mais utilizados. Porém, como eu disse, ele só aceita dados numéricos. E, como a nossa base de dados é composta por dados categóricos e numéricos, não podemos utilizá-lo.</p><p>Sendo assim, vou falar sobre um outro tipo de algoritmo de clusterização que é muito bom e que aceita dados categóricos, que é o algoritmo K-prototypes.</p><p>Para fazer a clusterização com o K-prototypes, temos que seguir os seguintes passos:</p><ol><li>Calcular a dissimilaridade entre os dados</li><li>Agrupar os dados</li></ol><h4>Cálculo da Dissimilaridade</h4><p>Como eu disse, o algoritmo K-prototypes aceita tanto dados categóricos quanto dados numéricos. Para fazer isso, ele calcula a dissimilaridade entre os dados categóricos e numéricos de duas formas diferentes e, depois, faz uma média ponderada dessas distâncias. Para exemplificar, vou utilizar a nossa tabela de dados do Uber.</p><p>Então, como podemos ver, existem diferentes tipos de dados em nossa base. E o primeiro passo para a aplicação do algoritmo K-prototypes é calcular a dissimilaridade entre eles.</p><p>Para fazer isso, vamos utilizar uma métrica chamada de Gower. A métrica de Gower, representada pela fórmula d(X, Y), calcula a dissimilaridade entre dois pontos de dados, X e Y, através da média ponderada das diferenças entre suas variáveis.</p><p>Para variáveis numéricas, a distância euclidiana normalizada entre os valores de X e Y é utilizada, garantindo que todas as variáveis numéricas tenham o mesmo peso, independentemente da sua escala.</p><p>Para variáveis categóricas, a contribuição é binária, indicando simplesmente se os valores são iguais ou não. Os indicadores delta_{i}^{(num)} e delta_{i}^{(cat)} determinam a natureza da variável (numérica ou categórica), garantindo a aplicação correta da parte correspondente da fórmula para cada tipo de variável.</p><p>A soma dessas contribuições, dividida pelo número total de variáveis n, resulta na dissimilaridade geral entre X e Y.</p><p>A fórmula para o cálculo da métrica de Gower é:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ISxbOd_91DfYYrY6-gn3_Q.png" /><figcaption>Imagem 5: Imagem do autor</figcaption></figure><p>Suponhamos que estamos comparando as informações de dois usuários: Maria e João. Os dados deles são fictícios, apenas para fins exemplares.</p><p>Passo 1: Normalização da Idade da Maria<br>Primeiramente, normalizamos a idade da Maria. Vamos assumir que a faixa etária ‘18–25’ corresponde a uma idade média de 21 anos. Utilizamos a fórmula de normalização min-max, considerando a idade mínima de 18 anos e a máxima de 80 anos. A idade normalizada da Maria é calculada como (21–18)/(80–18), resultando aproximadamente em 0.0484.</p><p>Passo 2: Distância Euclidiana entre as Categorias de Dados<br>Em seguida, calculamos a distância euclidiana entre as categorias de dados. No nosso caso, a idade é uma variável numérica e o tipo de viagem é uma variável categórica. Como estamos comparando variáveis de naturezas diferentes, a distância euclidiana é definida como 1.</p><p>Passo 3: Matriz de Correspondência entre os Dados Categóricos<br>Agora, observamos a matriz de correspondência entre os dados categóricos, que indica se as categorias de viagem de Maria e João são iguais ou diferentes. Para Maria e João, que possuem tipos de viagem diferentes, a matriz de correspondência é 0, pois não há correspondência entre suas categorias de viagem.</p><p>Passo 4: Cálculo da Dissimilaridade<br>Por fim, calculamos a dissimilaridade combinada entre a idade da Maria e o tipo de viagem do João. A dissimilaridade é a média das diferenças normalizadas, que neste caso simplificado, é apenas a idade normalizada da Maria, já que a matriz de correspondência é 0. Portanto, a dissimilaridade é aproximadamente 0.0484/2, o que dá cerca de 0.0242.</p><p>Este cálculo não representa uma aplicação completa da métrica de Gower, que normalmente incorporaria todas as variáveis categóricas e numéricas disponíveis.</p><h4>Agrupar os dados</h4><p>Agora, vou falar sobre o segundo passo: agrupar os dados. No algoritmo K-prototypes, o agrupamento dos dados é feito da mesma forma que o algoritmo K-means faz: utilizando a metodologia silhouette etc….</p><p>Agora, o terceiro passo: Como eu disse, o algoritmo K-prototypes calcula a dissimilaridade de dois dados de naturezas diferentes de duas formas diferentes e, depois, tira a média ponderada dessas duas distâncias.</p><p>Para fazer essa média ponderada, ele utiliza um hiperparâmetro chamado de lambda (λ). Por padrão, o valor de λ é 1. Porém, dependendo do seu problema, você pode alterá-lo. Quanto maior for o valor de λ, mais os dados numéricos influenciarão no cálculo da distância entre os dados e, consequentemente, na formação dos clusters. Por outro lado, quanto menor for o valor de λ, mais os dados categóricos influenciarão no cálculo da distância entre os dados e, consequentemente, na formação dos clusters.</p><p>A fórmula para o cálculo da dissimilaridade entre dois dados de naturezas diferentes é a seguinte:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZF4aYqWLaLXT4fO77aASZQ.png" /><figcaption>Imagem 6: Imagem do autor</figcaption></figure><p>À medida que o valor de λ aumenta, a influência da distância entre os dados categóricos diminui e a influência da distância entre os dados numéricos aumenta.</p><p>No K-Prototypes, do módulo kmodes, o parâmetro é ‘gamma’. E aplicando o K-Prototypes, temos o resultado abaixo da clusterização:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*3nVneJ9EMxiYQ_YSsgIIAw.png" /><figcaption>Imagem 7: Imagem do autor</figcaption></figure><p>Note que os eixos X e Y correspondem, respectivamente, à Distância Percorrida e à Frequência Mensal.</p><p>O cluster 1 é aquele que possui uma baixa frequência mensal, o cluster 0 é aquele que possui uma frequência mensal média e o cluster 2 é aquele que possui a maior frequência mensal. Esse foi o resultado com ‘gamma’ = 1.</p><p>Com ‘gamma’ = 0, temos o seguinte resultado:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*DguSF55RocGyp41sqW8QGg.png" /><figcaption>Imagem 8: Imagem do autor</figcaption></figure><p>Perceba que apenas os clusters mudaram de posição, mas a interpretação continua a mesma. A separação parece ser, ainda, pela frequência mensal de corridas.</p><p>Além disso, você pode perceber um detalhe: há um cálculo de uma “função de custo” a ser minimizada.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/1*MqdyJcJG8t7o4cHoBTBAgQ.png" /><figcaption>Imagem 9: Imagem do Autor</figcaption></figure><p>Qual cálculo é esse? Basicamente, queremos reduzir ao máximo a dissimilaridade das instâncias intracluster, ou seja, das instâncias que pertencem ao mesmo cluster. Isso para que elas sejam mais similares possível.</p><h3>Conclusão</h3><p>É isso, pessoal! Abaixo, vou deixar o código utilizado para esse artigo e o <a href="https://drive.google.com/file/d/17yaoxP0qTiB0We3aXpNA2rn5cMrUGc8s/view?usp=sharing">link do dataframe </a>para vocês brincarem um pouco.</p><p>Se você gostou do conteúdo e quer se aprofundar ainda mais na área de dados, uma das áreas tech que mais crescem no mundo, te convido a ser aluno da FCCD: a Formação Completa em Ciência de Dados.</p><p>Hoje, é a Formação mais completa do mercado pelo preço mais acessível. Estamos com as vagas lotadas, então <a href="https://fccd.com.br/lp">clique aqui </a>e entre para a lista de espera.</p><p>Assim que abrirmos uma nova turma, você terá prioridade se estiver na lista!</p><pre>!pip install kmodes<br><br>import pandas as pd<br>import matplotlib.pyplot as plt<br>import seaborn as sns<br>from kmodes.kprototypes import KPrototypes<br>sns.set_style(&#39;darkgrid&#39;)<br><br>df = pd.read_csv(&#39;dados_uber_simulados.csv&#39;)<br>df = df.drop(columns = [&#39;Id_Usuario&#39;], axis = 1)<br><br>kproto = KPrototypes(n_clusters=3, init=&#39;Cao&#39;, n_init=5, verbose=1, gamma = 0)<br>clusters = kproto.fit_predict(df, categorical=[0, 3, 4, 5])<br>df[&#39;Cluster&#39;] = clusters<br><br>plt.figure(figsize = (16, 9))<br>sns.scatterplot(data = df, x = &#39;Distancia_Percorrida&#39;, y = &#39;Frequencia_Mensal&#39;, hue = &#39;Cluster&#39;)<br>plt.title(&#39;Análise dos Clusters&#39;)<br>plt.show()</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=98a2115a6b9f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Um guia prático sobre Classificação Hierárquica]]></title>
            <link>https://medium.com/@anwarhermuche/um-guia-pr%C3%A1tico-sobre-classifica%C3%A7%C3%A3o-hier%C3%A1rquica-e723e5680c15?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/e723e5680c15</guid>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ciencia-de-dados]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[dados]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Mon, 26 Dec 2022 23:17:50 GMT</pubDate>
            <atom:updated>2023-01-08T13:49:41.587Z</atom:updated>
            <content:encoded><![CDATA[<p>Olá, pessoal! Neste artigo, vou trazer os principais conceitos sobre algoritmos de classificação que levam em conta a hierarquia entre as classes. Se você nunca ouviu falar, não se preocupe, este artigo te dará uma visão clara do que é a abordagem hierárquica para que você possa se aprofundar nos estudos.</p><p>Para iniciar, é válido dizer que a maioria das pesquisas e problemas no mundo do aprendizado de máquina são sobre problemas de classificação “flat”, que são os de classificação binária e multi-classe. Porém, muitos problemas no mundo real são, por natureza, problemas de classificação hierárquica, onde cada classe a ser predita pode ser organizada em hierarquias (em estruturas de árvores ou grafos).</p><p>Um problema muito comum é definir o que é um problema de classificação hierárquica. Saber como diferenciá-lo, por exemplo, de um problema de classificação multi-classe ou multirrótulo.</p><p>Há dois métodos muito conhecidos para abordar problemas de classificação multi-classe. Para algoritmos treinados para resolver estritamente problemas de classificação binária, temos dois métodos mais conhecidos: OvO e OvR (One versus One &amp; One versus Rest). As SVM’s e a regressão logística são um exemplo de algoritmos estritamente binários. No método OvO, se temos n classes, treinamos o algoritmo n*(n-1)/2 vezes, visto que cada classe irá ser treinada, exclusivamente e unicamente, com outra. Já no método OvR, o algoritmo será treinado n vezes, visto que cada classe irá ser treinada para se diferenciar das demais classes, e não uma por uma. Entretanto, há algoritmos, como as árvores de decisão, que são capazes de abordar a classificação multi-classe sem a necessidade de abordar um desses métodos. Visto isso, agora que entra a classificação hierárquica: uma nova abordagem aos problemas de classificação multi-classe.</p><h3>O que é classificação hierárquica?</h3><p>Neste artigo, a abordagem da classificação hierárquica irá explorar hierarquia de classes pré-definidas, e não criá-las a partir da similaridade de cada classe, que seria uma tarefa não supervisionada. A classificação hierárquica pode aparecer com o nome de classificação estruturada, porém não necessariamente os termos são sinônimos. O campo de pesquisa da classificação estruturada envolve muitos tipos diferentes de problemas que não possuem, necessariamente, a ideia de hierarquia. Entretanto, a classificação hierárquica pode ser considerada um tipo particular de classificação estruturada onde o output do algoritmo de classificação é definido a partir da taxonomia pré-definida das classes.</p><p>Já que estamos falando sobre taxonomia das classes, seria interessante definir o que, de fato, significa esse termo. Basicamente, a taxonomia de classes pode ser entendida como um conceito de hierarquia estruturado em um modelo de árvore e construído a partir de um conjunto finito C que contém as classes do problema com uma relação “IS-A”, onde a classe filha herda as características da classe pai. A relação “IS-A” é assimétrica (exemplo: todos os cachorros são animais, mas nem todos os animais são cachorros), anti-reflexiva e transitiva (exemplo: médicos são bacharéis; bacharéis cursaram uma faculdade; logo, médicos cursaram uma faculdade). Novamente, apesar de ser uma definição construída em cima de um modelo de árvore, também pode ser expandida para modelos em grafos.</p><h3>Classificadores mais comuns</h3><p>Saindo um pouco das definições e entrando na parte prática, os métodos de classificação hierárquica são divididos em 3:</p><p>1 — Os classificadores top-down, quando nós utilizamos um conjunto de classificadores percorrendo a estrutura da árvore (ou grafo) de cima para baixo.</p><p>2 — Os classificadores globais (big-bang classifiers), quando utilizamos um único classificador lida com todas as classes da hierarquia.</p><p>3 — Classificadores planos (flat classifiers), que ignoram a hierarquia das classes</p><p>Entretanto, olhando de forma mais profunda para cada abordagem, podemos notar que a abordagem top-down não é completamente uma abordagem hierárquica por si só, mas um método de evitar ou corrigir inconsistências na predição de classes em níveis diferentes na hierarquia. Além disso, há diversas formas de utilizar os dados para criar os classificadores locais, e apesar de que a maioria se refira à abordagem top-down na literatura, eles são muito diferentes durante a fase de treino e um pouco diferente durante a fase de teste.</p><h3>Abordagem utilizando classificadores locais</h3><p>A primeira abordagem com classificadores locais foi proposta em 1997 e ficou conhecida como abordagem top-down. Com esse estudo em mãos, várias pesquisas propuseram novas versões dessa abordagem para problemas de classificação hierárquica. Contudo, o principal ponto aqui não é a abordagem ser top-down (de cima pra baixo) em si, mas sim que a hierarquia entre as classes é levada em conta utilizando-se de dados locais. Parece haver três métodos padrões de utilizar informações locais:</p><p>1 — Classificador local por nó (LCN — Local Classifier per Node)</p><p>2 — Classificador local por nó pai (LCPN — Local Classifier per Parent Node)</p><p>3 — Classificador local por nível (LCL — Local Classifier per Level)</p><p>Em essência, essas três abordagens se diferem muito na fase de treino, e não tanto na fase de teste. Para cada nova instância de teste, o classificador prediz da classe mais genérica para a mais específica. Isso facilita e filtra possíveis erros de classificação, recursivamente, até que a classe mais específica seja atingida. Contudo, como nem tudo são flores, um erro de algum classificador custará todo o restante do processo e a classificação final será comprometida.</p><h4>Classificadores locais por nó</h4><p>De longe, é a abordagem mais utilizada na literatura e aparece com o nome de abordagem top-down. Porém, como dito anteriormente, esse não é um bom nome, visto que a abordagem top-down é, essencialmente, um método para evitar inconsistências na predição de classes em diferentes níveis na hierarquia. A abordagem de classificadores locais por nó consiste em treinar um classificador estritamente binário para cada um dos nós da hierarquia (exceto o nó raiz).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/782/1*fklDJH4J7ZO4jlvgMbDMZQ.png" /><figcaption>Imagem 1</figcaption></figure><h4>Classificadores locais por nó pai</h4><p>Essa abordagem é aquela em que um classificador multi-classe será treinado em cada nó pai. Além disso, é um método muito mais leve que os classificadores locais por nós, o que o torna mais fácil de implementar.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/781/1*RKkpelggM0rArIITGWIOfQ.png" /><figcaption>Imagem 2</figcaption></figure><h4>Classificadores por nível</h4><p>Por fim, essa abordagem é aquela com um classificador multi-classe para cada nível da taxonomia. Essa é a abordagem menos utilizada na literatura, porém é amplamente usada como modelo base de comparação para outros métodos. Um ponto relevante a se destacar é que, a cada nível que descemos na taxonomia, os modelos terão mais e mais classes para distinguirem e a abordagem ignora a relação pai-filho das classes, o que é uma grande desvantagem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/779/1*wtQjdwuikSN3QFmZenAPyQ.png" /><figcaption>Imagem 3</figcaption></figure><h3>Classificadores Globais</h3><p>Dito isso, vamos à abordagem utilizando classificadores globais. Ao contrário da abordagem local, o tamanho do modelo quando o utilizamos para aprender todas as classes de forma global é consideravelmente menor do que todos os modelos juntos treinados localmente. Além disso, dependências hierárquicas (exemplo: se pertence à classe 2.1, logo pertence à classe 2) são levadas em conta de forma natural nos classificadores globais. Abaixo, segue a representação esquemática da abordagem global (big-bang approach).</p><p>1 — Eles consideram a hierarquia de forma única</p><p>2 — Eles carecem de modularidade para treinamento local, que é uma das principais características das abordagens locais</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/772/1*7vAQl08lpLv0qfaMrr0xtg.png" /><figcaption>Imagem 4</figcaption></figure><h3>Framework de categorização de problemas</h3><p>Vendo todas essas possibilidades de abordar e classificar um problema de classificação hierárquica, vamos criar um framework para categorizar os diferentes tipos de problemas de classificação hierárquica</p><p>Primeiramente, vamos especificar qual é o tipo do grafo que utilizaremos para representar a hierarquia das classes e suas relações. As possibilidades são as seguintes:</p><p>T — Quando as classes a serem preditas são arranjadas em uma estrutura de árvore (tree)</p><p>D — Quando as classes a serem preditas são arranjadas em uma estrutura de grafo acíclico (Direct Acyclic Graph)</p><p>Agora, vamos definir se uma instância pode ter sua classe associada a uma ou mais classes na hierarquia de caminhos diferentes. Podemos dividir essa característica em dois grupos:</p><p>SPL — Quando uma instância tem sua classe associada a um único caminho na hierarquia (Single Path of Labels)</p><p>MPL — Quando uma instância pode ter sua classe associada a múltiplos caminhos na hierarquia. Exemplo: uma instância tem sua classe mais específica como sendo a 2.1.1 e 2.2.1, por exemplo. (Multiple Path of Labels)</p><p>Finalmente, vamos definir o nível hierárquico em que as instâncias serão classificadas. Novamente, essa classificação assume dois valores:</p><p>FD — Indica que cada instância será classificada com todos os níveis hierárquicos, indo da classe mais geral até a mais específica (Full Depth)</p><p>PD — Indica que pelo menos uma instância terá sua classe definida em apenas um nível (geralmente, o mais específico)</p><p>Agora, vamos fazer uma comparação entre as diferentes abordagens que vimos até agora para problemas de classificação hierárquica</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*H02_C0DqeEvz-kWhTPFGmw.png" /><figcaption>Imagem 5</figcaption></figure><p>Note que todas as abordagens utilizando classificadores locais durante a fase de treinamento têm como vantagem a simplicidade. Por outro lado, todos também têm como desvantagem a propensão à inconsistência.</p><p>Na fase de teste, entretanto, todos consideram a hierarquia de classes. Porém, ainda na fase de teste, uma desvantagem considerável é que a classificação feita de forma errada de uma das classes se propaga para todas as classes herdeiras.</p><p>Lembrando que todos esses classificadores locais podem ser usados para problemas diferentes. Os classificadores globais, no entanto, não possuem esse artifício. Eles são classificadores específicos para cada problema. No entanto, mais que o dobro das pesquisas na literatura utilizam a abordagem top-down, tornando os classificadores globais ainda pouco explorados.</p><p>Mesmo com vários algoritmos tendo desvantagens, é de fundamental importância tratar um problema de classificação hierárquica como tal. Para se ter uma noção dessa importância, dentre 31 pesquisas feitas comparando a abordagem utilizando classificadores planos com as abordagens citadas acima (LCN, LCPN, LCL &amp; GC), 28 performaram melhor levando-se a hierarquia em consideração e 3 tiveram resultados semelhantes. Ou seja, se estiver lidando com um problema onde há uma relação de hierarquia entre as classes, respeite-a.</p><h3>Métricas para modelos de classificação hierárquica</h3><p>Talvez, uma dúvida pode ter vindo à tona. Se estamos falando que um modelo performou melhor que o outro, alguma medida de desempenho está sendo utilizada. Então, qual medida é essa? Como podemos avaliar um modelo de classificação hierárquica? Dentre acurácia, ROC AUC, log-loss, F1 score etc., qual desses escolher?</p><p>Tenho uma má notícia para te dar: as métricas utilizadas em classificadores planos não são suficientes para trazer as informações necessárias a respeito da performance de modelos hierárquicos. É fácil ver que as métricas têm que ser diferentes, visto que o erro na classificação em diferentes níveis não devem sofrer a mesma penalidade. Porém, apesar de não serem ideais, a maioria das pesquisas citadas acima utilizaram métricas de classificadores planos. Outros autores, entretanto, propuseram suas próprias métricas de desempenho, que são utilizadas apenas por quem a propôs.</p><p>Contudo, em um estudo publicado em 2006 por Cesa-Bianchi, uma métrica chamada h-loss (hierarchical loss) foi proposta, podendo lidar com problemas estruturados em árvore, mas não com os grafos acíclicos. Além desse estudo, Kiritchenko, em 2005, propôs a precisão hierárquica (hP), revocação hierárquica (hR) e o valor F1 hierárquico (hF).</p><p>Há uma lacuna no campo de estudo de classificadores hierárquicos que é justamente uma métrica que possibilite a avaliação de forma justa de classificadores hierárquicos, e não a utilização de uma métrica de classificadores planos. Para se ter noção da importância de ter uma métrica correta, os autores das pesquisas relataram um pequeno ganho percentual no desempenho de um classificador hierárquico quando comparado a um classificador plano utilizando métricas de classificadores planos. No entanto, se utilizarmos as métricas propostas por Kiritchenko (hP, hR e hF), no pior caso, os classificadores hierárquicos superam os planos em 29.39%.</p><p>Assim como nas métricas planas, no mundo da classificação hierárquica não há uma métrica que seja melhor que as outras. No entanto, a recomendação é que sejam utilizadas as medidas hP, hR e hF, visto que podem ser efetivamente aplicadas em problemas de árvores, grafos e em vários outros cenários.</p><h3>Conclusão</h3><p>Com isso, finalizamos este artigo após passarmos pelos principais tópicos sobre as classificações hierárquicas. Este artigo tem como base o paper “<a href="https://link.springer.com/article/10.1007/s10618-010-0175-9">A survey of hierarchical classification across different application domains</a>”.</p><p>Até já, pessoal!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e723e5680c15" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Gradiente Descendente — Uma breve introdução]]></title>
            <link>https://medium.com/@anwarhermuche/gradiente-descendente-uma-breve-introdu%C3%A7%C3%A3o-3eb13b152a51?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/3eb13b152a51</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[inteligencia-artificial]]></category>
            <category><![CDATA[gradient-descent]]></category>
            <category><![CDATA[ciencia-de-dados]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Thu, 01 Sep 2022 04:12:45 GMT</pubDate>
            <atom:updated>2022-09-01T04:12:45.995Z</atom:updated>
            <content:encoded><![CDATA[<h3>Gradiente Descendente — Uma breve introdução</h3><p>Neste artigo, vou abordar o que realmente você precisa saber sobre gradientes aplicados em Machine Learning.</p><p>Quando nos deparamos com ele pela primeira vez, geralmente tomamos um susto, porque envolve conceitos avançados para quem está chegando agora na área de exatas que é o cálculo em si (derivadas parciais, funções etc.), mas te garanto que se você ler este artigo com o coração aberto, suas dúvidas serão esclarecidas!</p><h3>Gradiente Descendente</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*iDYuAOgV1LIMLweOPFmHCQ.gif" /><figcaption>Imagem 1</figcaption></figure><p>O Gradiente Descendente é um método utilizado com o intuito de otimização. E quando falamos sobre otimização, no caso da aplicação em Machine Learning, falamos sobre a otimização dos parâmetros do nosso algoritmo para que a taxa de assertividade do modelo só aumente.</p><p>Como você pode ver pelo GIF da imagem 1, essa malha laranja representa o resultado da <a href="https://medium.com/@anwarhermuche/fun%C3%A7%C3%B5es-de-custo-uma-breve-introdu%C3%A7%C3%A3o-5a472599ac1e"><strong>função de custo</strong></a><strong> </strong>para todas as combinações possíveis de parâmetros do nosso modelo. Sendo assim, algumas combinações vão gerar erros maiores — representados pelos picos na malha — e determinadas combinações de parâmetros vão gerar os erros mínimos (mínimo global ou local), que é justamente o ponto que queremos alcançar.</p><p>Esse método do gradiente descendente é feito a partir de iterações, onde, a cada iteração, o gradiente move-se passo a passo em direção ao maior declive da curva, alcançando o mínimo local (ou global), como está mostrando o GIF.</p><h3>Aplicação em Machine Learning</h3><p>Vamos, então, para a prática. Começaremos com o seguinte dataset:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/96/1*6KN4YJcbwzNzdMvWZXmAlQ.png" /><figcaption>Imagem 2</figcaption></figure><p>Vendo assim, não dá para perceber se há alguma relação entre os dados. Então, para uma melhor visualização, vou utilizar o “scatterplot” do seaborn. Observe como nossa variável X está relacionada com a variável y:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/959/1*PxhslOrjA56zEje0-BQAHw.png" /><figcaption>Imagem 3</figcaption></figure><p>Pelo gráfico, podemos ver que há uma correlação positiva forte entre as duas variáveis. Então, nosso objetivo agora é tentar achar qual é a equação da reta da forma y = a*x + b que melhor se aproxima desses pontos. Para isso, vamos começar com a seguinte equação de reta: y = 0*x + 0, ou seja, a = 0 e b = 0. Observe como fica sua representação gráfica:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/956/1*DR1pDn7MRLZO42-vlWS19g.png" /><figcaption>Imagem 4</figcaption></figure><p>De fato, esta não é a melhor representação da reta que mais se aproxima da configuração dos datapoints. Para poder mensurar o erro do nosso modelo, vamos fazer uso da função de custo. Se fizermos os cálculos, chegaremos em 390.09. Caso não saiba como fazer, recomendo que leia meu artigo sobre Função de Custo <a href="https://medium.com/@anwarhermuche/fun%C3%A7%C3%B5es-de-custo-uma-breve-introdu%C3%A7%C3%A3o-5a472599ac1e"><strong>clicando aqui</strong></a> e confira o código deste artigo no <a href="https://github.com/anwarhermuche/gradient-descent/blob/main/Gradient%20Descent/gradient_descent.ipynb"><strong>meu GitHub</strong></a>.</p><p>Com este resultado em mente, nosso objetivo agora é ir diminuindo cada vez mais o erro. Mas como fazemos isso? Simples, ajustamos os parâmetros de tal forma que o resultado da função de custo seja mínimo. Para isso, vamos recapitular sobre derivadas parciais para, de fato, implementarmos o gradiente descendente neste problema.</p><p>Nós vamos atualizar os pesos de acordo com a seguinte equação:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/741/1*EuWASfrMY3qMeXhkd5PYLw.png" /><figcaption>Imagem 5</figcaption></figure><p>Se você não faz ideia do que se passa nessas duas equações, vou explicar. Neste caso, a e b são o <em>slope</em> (coeficiente angular) e o <em>intercept</em> (coeficiente linear) da nossa reta, respectivamente. A letra grega eta (η) representa o passo de aprendizagem ou o <em>learning rate, </em>ele que determina o tamanho do passo a cada iteração. Por fim, o termo que provavelmente a maioria ficou em dúvida: ∂. Este é o símbolo da derivada parcial. Note que tanto em “a” quanto em “b” estamos subtraindo o seu próprio valor pelo passo de aprendizagem multiplicado pela derivada parcial da Função de Custo em relação a “a” ou “b”. Para simplificar os cálculos, vou colocar qual seria esse resultado de forma pronta, mas caso você já tenha estudado Cálculo II, recomendo fortemente que veja a demonstração desse resultado, que, caso você já tenha estudado, é bem simples.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MessDK2qbKbzXiH-D9LKUg.png" /><figcaption>Imagem 6</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rRhZyGHf_m-eJO85BEiyNw.png" /><figcaption>Imagem 7</figcaption></figure><p>Nas imagens 6 e 7, podemos ver a forma simplificada do algoritmo do gradiente descendente. Lembre-se de que todos os parâmetros (a e b, nesse caso) são atualizados no mesmo instante, ou seja, o resultado da atualização de um, na mesma iteração, não afeta o resultado do outro. Além disso, “n” é o número de amostras do nosso dataset.</p><p>Então, vamos atualizar os parâmetros “a” e “b” com um learning rate igual a 0.005:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RCKPPrcNdWw9o1YQcmT-Lw.png" /><figcaption>Imagem 8</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n_8mctjbkYILFVhZj_Q6aA.png" /><figcaption>Imagem 9</figcaption></figure><p>Atualizando os parâmetros e “replotando” a nossa reta, temos:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/955/1*JjM2vAYHTOLgZL3u9VcUCA.png" /><figcaption>Imagem 10</figcaption></figure><p>Olha que massa. A reta se aproximou mais de como os nossos dados estão distribuídos. Se recalcularmos a função de custo, chegamos em 99.63. Se fizermos esse procedimento várias e várias vezes, vamos chegar em um valor mínimo para a função de custo que significará que encontramos a reta que melhor se aproxima da distribuição dos nossos dados.</p><p>Um detalhe importante a se notar é que em uma regressão linear, a função é convexa, ou seja, o mínimo local é o mínimo global. Em funções de custo utilizadas em redes neurais, por exemplo, temos exemplos de funções não convexas, onde não necessariamente o mínimo local é o mínimo global.</p><p>Para finalizar, vou colocar aqui o resultado dos parâmetros que minimizam a função de custo para o nosso dataset. Utilizando a classe LinearRegression do pacote sklearn, podemos calcular quais são os melhores parâmetros para o nosso modelo. <br>Sendo assim, a nossa equação de reta que possui o mínimo valor de custo nos pontos do nosso dataset é y = 0.674x - 10.848, que nos devolve um custo igual a 7.042. Note que saímos de um custo de 390 para um de 7, o que significa uma baita melhora da nossa reta.</p><p>Para melhor compreensão, vou colocar o resultado final da nossa reta:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/955/1*mZYdVNXQCqs4DR9nfNDq-Q.png" /><figcaption>Imagem 11</figcaption></figure><h3>Conclusão</h3><p>Chegamos ao final de mais um artigo aqui no Medium falando sobre conceitos importantes para Machine Learning. Espero que você tenha compreendido o funcionamento do algoritmo do gradiente descendente, porque realmente não é fácil entender de primeira. Caso não tenha entendido, recomendo pesquisar outras fontes no Google para ter diversas referências e conseguir de fato consolidar o conhecimento. E não se esqueça de que o código feito para utilizar nessa aula está no <a href="https://github.com/anwarhermuche/gradient-descent/blob/main/Gradient%20Descent/gradient_descent.ipynb"><strong>meu GitHub</strong></a>!</p><p>Até já, pessoal!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3eb13b152a51" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Funções de Custo — Uma breve introdução]]></title>
            <link>https://medium.com/@anwarhermuche/fun%C3%A7%C3%B5es-de-custo-uma-breve-introdu%C3%A7%C3%A3o-5a472599ac1e?source=rss-f78a171df2f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/5a472599ac1e</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ciencia-de-dados]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[função-de-custo]]></category>
            <category><![CDATA[deep-learning]]></category>
            <dc:creator><![CDATA[Anwar Hermuche]]></dc:creator>
            <pubDate>Wed, 24 Aug 2022 23:47:36 GMT</pubDate>
            <atom:updated>2022-08-24T23:47:36.420Z</atom:updated>
            <content:encoded><![CDATA[<h3>Funções de Custo — Uma breve introdução</h3><p>Neste artigo vou apresentar a teoria por trás desse termo muito usado em algoritmos de Machine Learning.</p><h3>Função de Custo</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/974/1*RjjrUW4HIro_qGDzhW6edA.png" /><figcaption>Imagem 1</figcaption></figure><p>Um dos objetivos principais em algoritmos de aprendizagem supervisionada é a definição de uma função que será otimizada durante as iterações para encontrar os parâmetros ideais para o nosso modelo. Na maioria dos casos, essa função será a função de custo, que o nosso objetivo será minimizar o seu resultado. Várias pessoas confundem função de custo e função de perda. A função de perda é quando nos referimos ao erro de apenas um exemplo do nosso dataset. Já a função de custo é quando nos referimos à média da função de custo de todos os nossos exemplos do dataset.</p><p>Quando estamos estudando pela primeira vez sobre a função de custo, nos confundimos porque a vemos em modelos de regressão, classificação, redes neurais etc.. Ou seja, parece que cada uma delas tem algo de diferente, apesar de possuírem o mesmo nome. Para resolver isso, é bom falarmos sobre funções de custo para três tipos de modelos: Modelos de Regressão, Classificação Binária e Classificação Multi-classe.</p><h4>Funções de Custo: Modelos de Regressão</h4><p>Vamos iniciar com a função de custo utilizada em modelos de Regressão. Sabemos que modelos de regressão são utilizados para fazermos a predição de alguma variável contínua. Então, na Função de Custo de Regressão, utilizamos a distância entre o valor verdadeiro e o valor previsto como base para a otimização do problema, cujo objetivo seria minimizar essa distância ao máximo.</p><p>Na imagem 1 podemos ver um exemplo de como é a fórmula da função de custo. Muitas pessoas têm a dúvida do porquê algumas fórmulas da função de custo têm o 2 multiplicando o m e outras fórmulas não. A explicação é bem simples: quando a fórmula não possui o 2, significa que podemos chamar a função de custo de erro quadrático médio (MSE). Quando temos o 2 dividindo, perdemos o poder de nomear a função como sendo o MSE, e simplificamos o cálculo do gradiente descendente. Porém, no final das contas, o 2 não interfere quando o nosso objetivo é minimizar o resultado da função.</p><p>Além dessa fórmula da imagem 1, podemos utilizar a função de custo que representa o erro médio absoluto (MAE), que acaba sendo menos sensível a outliers quando comparada ao MSE. Abaixo, vou deixar sua fórmula para quem tenha curiosidade:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/904/1*VslqcqtR9qzEDqwYvUDhpQ.png" /><figcaption>Imagem 2</figcaption></figure><h4>Funções de Custo: Modelos de Classificação</h4><p>Apesar de o nome ser igual (até porque o objetivo das duas são iguais, que é quantificar o erro do modelo), as funções de custo utilizadas nos modelos de classificação têm estruturas diferentes.</p><p>Uma função de perda muito usada é a Entropia Cruzada (cross-entropy). Resumidamente, ela classifica a qual classe aquela amostra pertence baseando-se em probabilidades, logo, a classe que possui maior probabilidade é a escolhida para aquela amostra. Podemos entender a função de entropia cruzada como sendo um meio para medir a distância entre duas distribuições de probabilidade. Imagine que em uma determinada amostra de treino com o dataset Iris a classe prevista para ela é Setosa. Porém, o modelo de machine learning nos diz que ela tem uma probabilidade de 0.8 de ser Setosa, ou seja, devemos reajustar os pesos para que essa distribuição de probabilidade tenda a ficar cada vez mais próxima da real.</p><h4>Classificações Multi-classe</h4><p>Em problemas onde há várias classes e cada amostra do nosso dataset pertence a apenas uma das classes, utilizamos esse tipo de função de custo.</p><p>Para começarmos, vamos definir como a nossa entropia cruzada é calculada. Aqui, vamos fazer a multiplicação de cada uma das probabilidades reais de uma amostra pertencer a uma classe pelo logaritmo da probabilidade prevista. Se ficou confuso explicando com palavras, acho que com um exemplo e um pingo de álgebra pode facilitar o entendimento.</p><p>Sendo assim, imagine, novamente, o dataset Iris. Nele, vamos pegar uma amostra do dataset de treino onde a Iris pertence à classe Setosa. Logo, a probabilidade de ela pertencer à classe Setosa sé igual a 1, e a probabilidade de ela pertencer as outras classes sendo igual a 0. Agora, suponha que o nosso modelo de Machine Learning nos diz que a probabilidade de ela pertencer à classe Setosa é igual a 0.75; à classe Versicolor, 0.2; e à classe Virginica, 0.05. Sendo assim, podemos representar todos esses valores de probabilidades reais e previstas em dois vetores:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ewwigsjHySyxldNdPM6C6g.png" /><figcaption>Imagem 3</figcaption></figure><p>Agora, para calcular o valor da entropia cruzada, vamos utilizar a seguinte fórmula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/866/1*lnROgN9wOpEAIKX_FZwcUw.png" /><figcaption>Imagem 4</figcaption></figure><p>Ou seja, obtemos o vetor transposto de P, aplicamos a função ln (logaritmo natural) em cada um dos seus elementos, fazemos o produto escalar com o vetor Y e, por fim, multiplicamos o resultado por -1. Matematicamente, fica assim:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_lz9Fi-iAtkyQ5DEzkX1pQ.png" /><figcaption>Imagem 5</figcaption></figure><p>Se fizermos o cálculo, chegamos em CE(y, p) = 0.287. Com esse resultado, acabamos de descobrir a entropia cruzada para apenas uma amostra do nosso dataset de treino. Para definirmos qual é o erro de classificação do dataset completo faremos nada mais que a soma de todas as entropias cruzadas para cada amostra do dataset de treino dividido pelo número de amostras, ou seja, a famosa média. Por fim, podemos representar a função de custo da seguinte maneira:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cS0K-AHvvKewZXlddkjsdQ.png" /><figcaption>Imagem 6</figcaption></figure><p>É bom ressaltar que a utilização de diferentes bases muda apenas a unidade de medida do resultado. Se utilizarmos, por exemplo, logaritmo na base 2, o resultado será em bits. No nosso exemplo, utilizamos logaritmo natural, logo o resultado tem como unidade de medida o nat (unidade natural de informação).</p><h4>Classificações Binárias</h4><p>Nas classificações binárias, a saída pode assumir apenas dois valores (1 e 0 são os mais comuns). Um caso onde pode haver a utilização desse modelo de classificação é determinar se uma determinada contém um gato ou não, ou seja, sim ou não (1 ou 0).</p><p>Matematicamente, vamos calcular a entropia cruzada para esse tipo de classificação da seguinte maneira:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9B_uJroJT24AuDCTXvZ4hw.png" /><figcaption>Imagem 7</figcaption></figure><p>Novamente, o erro de classificação do dataset completo será a soma de cada erro individual das amostras dividido pelo número de amostras, isto é, a média. Podemos representar a função de custo da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-p8DApak1vtNSuuk7nrJ-g.png" /><figcaption>Imagem 8</figcaption></figure><h3>Conclusão</h3><p>Pronto, vimos uma boa parte sobre as funções de custo que utilizaremos para montar alguns modelos em artigos futuros. Acho muito válido ficar por dentro da teoria matemática por trás dos modelos para não ficar trabalhando como uma caixa preta, isto é, sem saber o que realmente se passa durante o processamento dos dados (exceto em modelos de redes neurais com várias hidden layers, rs.).</p><p>Espero que com esse artigo eu possa ter esclarecido um pouco sobre as funções de custo.</p><p>Até já, pessoal</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5a472599ac1e" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>