Aula 1.1 - Álgebra linear

25 minuto(s) de leitura

Introdução

Seja bem vindo a aula 1.1 do curso de machine learning do blog. Este é o primeiro post de aula do curso e a ideia da mesma é introduzir os conceitos básicos que formarão a base necessária para iniciar na área. Machine learning é fortemente baseado em álgebra linear, cálculo e estatística. A aula 1 será divida em 3 posts que abordarão cada um deste conceitos básicos. Portanto, começameremos com Álgebra linear.

Eu sei que muitos tem traumas de álgebra (principalmente quem já cursou em alguma graduação). Porém, um bom entendimento da disciplina é necessário para aprender machine learning. Portanto, aqui vamos discutir diversos conceitos básicos, mas caso queira se aprofundar, sugiro que procure um livro ou algum curso. Infelizemente, a maioria dos materiais estão em inglês (eis a razão de existência deste blog!) mas você encontra alguns cursos como este no YouTube.

Escalares, vetores e matrizes

Os 3 principais tipos de dados da álgebra linear são descritos a seguir:

  • Escalares: um escalar é apenas um número (as vezes conhecido como crisp). Normalmente este número pertence a um conjunto, como os números reais ou naturais. A notação utilizada para um escalar é uma letra minúscula. Um exemplo de escalar pode ser descrito por , ou seja, é um escalar que pertence aos números reais, logo, ele pode assumir valores como , , etc.

  • Vetores: um vetor é uma coleção de números escalares. Logo, esse objeto é um conjunto de números identificados por um índice. Um vetor pode conter elementos de algum conjunto de números, por exemplo, os números reais. A notação padrão para um vetor é uma letra mínuscula em negrito, por exemplo . No caso, é o primeiro elemento deste vetor. Uma outra maneira de representar um vetor é explicitando seus dados, por exemplo, . Neste caso dizemos que , ou seja, todos os elementos do vetor são números reais.

  • Matrizes: uma matriz é uma conjunto de dados de 2 ou mais dimensões, na qual cada elemento é identificado por dois ou mais índices. A notação padrão de uma matriz é uma letra maiúscula em negrito, por exempplo, . Tomando como exemplo uma matriz de duas dimensões, ela pode conter elementos. Neste caso, dizemos que , ou seja, todos os elementos da matriz são números reais com linhas e colunas. Uma maneira de representar essa matriz é descrita da seguinte maneira:

Observe que matrizes é um conceito que engloba vetores e escalares. Podemos dizer que um vetor é uma matriz com apenas uma linha ou coluna. Da mesma maneira, podemos dizer que um escalar é uma matriz ou um vetor com apenas um elemento, por exemplo,

Operações com matrizes, vetores e escalares

Podemos realizar algumas operações com matrizes. Nesta seção vamos abordar transposição, soma, subtração e multiplicação por escalar, produto escalar e broadcasting. Todas essas operações são bem simples de serem executadas.

Tranposição

Transpor uma matriz nada mais é do que trocar suas linhas por suas colunas, ou vice-versa. Tomando como exemplo a equação 1, todos os elementos de até são chamados de diagonal principal. A transposição espelha todos os elementos da matriz em torno dessa diagnonal. De maneira formal, a transposição é descrita por:

Um exemplo pode ser descrito na equação 2 a seguir. Observe que a diagonal principal se mantém. Uma regra simples para transposição é pensar: o que é linha vira coluna e o que é coluna vira linha. Sempre funcionar!

Vetores também podem ser transpostos. Caso ele seja uma linha, ele vira coluna e vice versa, como mostra o exemplo na equação 3. No caso de um escalar, a transposta dele é ele mesmo, ou seja, .

Soma e subtração

Duas matrizes podem ser somadas quando as mesmas possuem a mesma ordem, ou seja, o mesmo número de linhas e colunas. A soma é realizada simplemente somando cada elemento de cada posição, como descrito na equação 4 e exemplificado na 5. Os vetores funcionam da mesma maneira, com a diferença que estaremos somando uma linha ou coluna apenas.

A subtração funciona da mesma maneira basta apenas trocar o sinal.

Multiplicação por escalares

Também podemos multiplicar matrizes e vetores por escalares. A operação é bem simples e é descrita pela equação 6 e exemplificada pela 7. Em resumo, basta realizar a multiplicação do escalar por todos os elementos do vetor ou matriz.

Produto escalar (dot product)

O produto escalar (ou dot product) entre dois vetores de mesma dimensão é definido por:

Observe que o produto escalar retorna um escalar.

Norma de um vetor

A norma de um vetor é representada por é informalmente conhecida como o “tamanho” de um vetor. Existem diversas normas e de maneira geral para uma função ser considerada uma norma, ela precisa satisfazer as seguintes condições:

  • Não negatividade:
  • se e somente se
  • Homegeniedade:
  • Inequação triangular:

Alguns exemplos de normas são:

  • Norma L1:

  • Norma L2:

  • Norma :

  • Norma :

Perceba que a norma é uma generalização das demais. Tenha em mente também que existem outras diversas normas, basta satisfazer a condições descritas acima.

A norma é muito utilizada em machine learning e de maneira intuitiva, a norma mede a distância de um vetor para com a origem. No caso, a norma L2 é tão utilizada que por vezes é omitido o número 2 e é denotado apenas .

É muito comum medir o tamanho de um vetor elevando essa norma ao quadrado, que é facilmente calculada fazendo . Isso é importante para facilitar o cálculo de derivadas. Como ainda vamos ver, atualmente, os algoritmos de minimização utilizados em ML são baseados em derivadas. Sendo assim, a derivada do quadrado da norma L2 com respeito a um elemento de depende apenas do elemento, enquanto da L2 depende de todo o vetor.

Por fim, o produto escalar entre dois vetores pode ser escrito em termos da norma: , where is the angle between both vectors.

Broadcasting

Em computação é comum encontramos a operação de broadcasting (normalmente não existe uma tradução pra essa palavra). Essa operação simplifica a notação e a computação. Python possui um pacote de computação númerica, chamada NumPy, que da suporte a broadcasting. Ela será muito utilizada neste curso.

Explicando o broadcasting por meio de um exemplo, imagine que desejamos somar uma matriz a um vetor . Bom, sabemos que isso não é possível, uma vez que para a soma ocorrer, ambos devem ter a mesma ordem. Porém, podemos repetir os valores a linha do vetor vezes e ai sim realizar essa soma. Para evitar escrever tudo isso, apenas dizemos que . Como já está convencionado o broadcasting, seja e , sabemos que essa operação significar fazer:

Multiplicação de matrizes

A multiplicação de matrizes é uma das operações mais importantes envolvendo matrizes. A regra de ouro aqui é que o número de linhas de uma matriz deve ser o mesmo de colunas da matrizes na qual deseja-se multiplicar. Isso é descrito na equação 9.

A multiplicação de matrizes não como a soma que basta multiplicar todos os elementos de uma matriz pelos os de mesmo índice da matriz subsequente. Essa operação de multiplicar elemento por elemento é conhecida como element-wise product e tem um símbolo especiar, no caso . A multiplicação de fato é definida da sequinte maneira:

Para exemplificar:

Se observamos a multiplicação acima, percebemos que nada mais é do que um produto escalar esntre as linhas das matrizes. É comum representar o produto escalar como sendo .

Propriedades

A multiplicação de matrizes possuem algumas propriedades que podem ser úteis em alguns casos. Destacamos as seguintes propriedades:

  • Distributiva:
  • Associativa:

Porém a multiplicação não é comutativa, isto é . Porém, o producto escalar é, i.e., .

Além disso, a transposta de uma matriz possui a seguinte propriedade: .

Existem diversas outras propriedas, mas isso aqui é apenas uma introdução então não vamos adentrar nelas e nem nas provas teóricas.

Um simples sistema linear

Com os conceitos explorados até aqui, podemos montar um simples sistema linear da seguinte forma:

Onde , e . Neste caso a variável é valor desconhecido que desejamos descobri. Cada elemento é um elemento desconhecido a ser descorberto. Utilizando os conhecimentos adquiridos até aqui você pode aferir facilmente que a primeira linha desta equação linear será . Como exercício, tente expandir as demais linhas! Essa modelagem matricial é de extrema importância para os algoritmos de machine learning uma vez que basicamente tudo é modelado assim.

Nota: perceba que não existe divisão de matrizes. Você pode realizar a operação por elemento (element-wise), mas a divisão em si não existe.

Inversão de matriz

Para solucionar o sistema linear apresentado na equação 12 vamos precisar uma outra operação matricial chamada de inversão. Mas antes, precisamos definir o conceito de matriz identidade. Uma matriz identidade é definida como a matriz que multiplicada por vetor não o modifica. Formalmente:

Como pode ser observado, uma matriz identidade é obrigatoriamente quadrada, ou seja, o número de linhas é igual ao número de colunas, sua diagnoal principal é composta por uns e o resante de seus indices por zeros. Um exemplo de matriz identidade de ordem 3 é mostrado na equação 14:

Bom, agora podemos definir a matriz inversa. Essa matriz, denotada por é definida como a matriz que multiplicada por retorna a identidade. Formalmente:

Com essa definição é possível solucionar o sistema linear da equação 12 da seguinte maneira:

Observe que foi adicionado em ambos os lados da equação para que ela fosse solucionada. Para essa equação ser válida a inversa da matriz deve ser válida. Acontece que nem sempre a matriz possui uma inversa. Neste caso, quando ela possui uma inversa, dizemos que a matriz é inversível ou não-singular. Caso contrário, dizemos que a matriz é não-inversível ou singular. Vamos discutir isso na próxima seção.

Propriedades

Considerando matrizes não singulares, podemos definir as seguintes propriedades para a matriz inversa:

  • A inversa da inversa é igual a :
  • A inversa de é igual a multiplicação de suas respectivas inversas:
  • A transposta da inversa de é igual a inversa da transposta:

Dependência linear, span e posto

Para que a inversa de exista é necessário que o sistema linear da equação 12 tenha apenas umas solução para cada valor de . Como você deve lembrar do seu ensino médio (eu espero que lembre), esse tipo de sistema pode ter nenhuma, uma ou várias soluções. Neste caso, se e são soluções, então:

também é uma solução para qualquer valor de . Uma maneira de determinar quantas soluções a equação possui é imaginar cada coluna de como um vetor e quantificar quantas vezes esse vetor, saindo da origem, gera o vetor . Desta maneira, cada elemento de especifica o quando o devemos afastar da origem, sendo o quanto se afasta em direção a coluna da matriz:

Essa operação nada mais é do que uma combinação linear. Formalmente, uma combinação linear de um vetor é dada pela soma da multiplicação de cada elemento deste vetor por um escalar:

Dessa forma, o span de um conjunto de vetores é o conjunto de todos os pontos obtidos através de combinações lineares dos vetores originais. Sendo assim, imagine um conjunto de vetores . Esse conjunto de vetores é considerado linearmente independente (LI) se nenhum ventor pertencente a pode ser presentado como combinação linear dos demais. Caso isso ocorra, esse conjunto é considerado linearmente dependente (LD). Caso não tenha entendido, é simples. Considere a seguinte situação: se pode ser obtido através uma combinação linear, de acordo com a equação 19, dos vetores , logo, esse conjunto é LD, caso contrário, LI.

De maneira formal, para determinar se a equação 12 possui uma solução, precisamos saber se está no span das colunas de . Esse span, em particular, é conhecido como espaço das colunas ou intervalo de . Perceba que encontrar todas as combinações lineares de um conjunto de vetores não é algo trivial. Logo, existem algumas condições que precisam ser respeitadas para que a solução exista.

Tomando , é necessário que o espaço de colunas de esteja todo em . Isso implica que deve ter pelo menos colunas com . Todavia, isso é apenas uma condição necessária, mas não suficiente, pois algumas colunas podem ser redundantes. Essa redundância nada mais é do que um dependência linear. Para verificar essa dependência introduzimos o conceito de posto (ou rank).

Considerando o conjunto de colunas (ou linhas) de uma matriz , o posto é igual ao maior número elementos deste conjunto que são linearmente independentes. Esse conjunto pode ser tanto de colunas ou linhas pois ambos os valores de ambos postos são obrigatoriamente iguais. Uma propriedade importante é que posto() min(). Se posto() min(), é chamada de matriz de posto completo (ou full rank). De maneira didática, se é uma matriz e o posto() = 5, logo, é posto completo.

Mas por que o posto é importante? Bom, para garantir que o sistema da equação 12 tenha apenas uma solução, devemos verificar se é posto completo. Isso é condição necessária e suficiente para o que desejamos. Perceba que se juntarmos a condição necessária e a necessária e sufciente apresentadas até aqui, isso significa que a matriz necessáriamente deve ser quadrada, ou seja, e com todas as colunas linearmente independentes. Caso uma matriz quadrada possua alguma coluna linearmente dependente, ela é chamada de singular. E se você se recorda da seção anterior, matrizes singulares não são inversíves. Portanto, após todos esses conceitos, o resultado final é: para uma matriz ser inversível ela deve ser posto completo!

Determinante de uma matriz

O determinante de uma matriz é uma função que associa uma matriz quadrada a um escalar. Este valor pode ser interpretado como uma medida de singularidade da matriz. De maneira formal, o determinante de uma matriz quadrada é a função det: e é denotado por det ou .

A formula geral para calcular o determinate de uma matriz não é trivial de se entender. Por isso (se você se lembrar do ensino médio), temos regras especificas para matrizes e . De qualquer forma, para a matriz definida anteriormente, definimos a a submatriz que será o resultado da exclusão da -ésima linha e a -ésima coluna de . De maneira formal, temos .

Matriz diagonal

Uma matriz diagonal é toda composta por zeros, exceto pela diagonal principal. Formalmente, é uma matriz diagonal se para todo . Um exemplo de matriz diagonal é a identidade, descrita na equação 14.

Um matriz diagonal quadrada composta por elementos de é descrita como diag(). Utilizar esse tipo de matriz é interessante pois a mesma é computacionalmente eficiente. Para calcular diag() basta escalar cada elemento de por . Em outras palavras, diag() .

Além disso, calcular a inversa de uma matriz diagonal é bastante eficiente. Caso a diagonal seja não zero, diag = diag. Essa matriz também é conhecida com matriz de cofatores. Dessa forma, o determinante de é calculado da seguinte forma:

Perceba que a formula é recursiva e bastante trabalhosa. Por conta disso, é difícil encotrar a expansão da mesma para matrizes de ordem superior a . A seguir, é apresentado a expansão da equação 20 para . Caso queira conferir a fórmula, sinta-se a vontade:

O determinante possui algums propriedades interessantes e muito importantes:

  • Para :
  • Para :
  • Para : se e somente se é singular
  • Para e :

Se você voltar ao início dessa seção, definimos que o determinante é uma medida de singularidade e isso é descrito na terceira propriedade anterior. Essa propriedade é muito importante e se você conectou os pontos ela diz, em outras palavras que: para uma matriz ser inversível, obrigatóriamente seu determinante deve ser diferente de zero!. Convenhamos que isso é muito mais fácil do que determinar todoas as combinações lineares das colunas da matriz.

Por fim, a partir da definição e das propriedades de determinante, surge a definição da matriz adjunta:

A partir desta matriz adjunta é possível calcular a inversa de da seguinte forma:

Todavia, apesar dessa formula ser explícita, ela é computacionalmente custosa de ser computada.

Traço de uma matriz

O traço (ou trace) de uma matriz quadrada nada mais é do que a soma da sua diagonal principal. Dessa forma, seja , o seu traço tr() é definido como:

Algumas das propriedades do traço de são descritas a seguir:

  • Para : tr() = tr()
  • Para : tr() = tr() + tr()
  • Para e : tr() = tr()
  • Para em que é uma matriz quadrada: tr() = tr()

Vamos utilizar esse conceito mais para frente.

Tipos especiais de matrizes e vetores

Algumas matrizes e vetores são bastantes úteis. Nesta seção serão apresentadas algumas:

Matriz simétrica

Uma matriz simétrica é definida como $$ A_{ij} = A_{ji}. Ou seja, os valores acima da diagonal é igual aos abaixo. Isso ocorre, quando calculamos, por exemplo, uma matriz de covariância (não se preocupe, chegaremos lá). Um exemplo de matriz simétrica é descrito a seguir:

Uma propriedade interessante deste tipo de matriz é que ela é igual a sua transposta, ou seja, .

Vetor normal, ortogonal e ortonormal

Um vetor é considerado normal (ou unitário) se sua norma L2 é unitária:

Um detalhe importante é que qualquer vetor com norma maior do que zero pode ser normalizado, basta dividir o mesmo por sua norma, ou seja, se então .

Dois vetores e são ortogonais entre si se o produto escalar entre eles for igual a zero, ou seja:

Se a norma de ambos os vetores for diferente de zero, isso significa que o ângulo formado entre os vetores é igual a 90°. Além disso, se os vetores são ortogonais e ambos possuem normas unitárias, eles recebem o nome de ortonormal

Matriz ortogonal

Uma matriz ortogonal é uma matriz quadrada na qual suas linhas e colunas são mutualmente ortonormais entre si, respectivamente (importante: é linha com linha e coluna com coluna). Caso isso ocorra, a seguinte propriedade é observada:

O que implica em outra propriedade muito importante:

Isso significa que a inversa desse tipo de matriz possui um custo computacional muito baixo e por isso ela é interessante. Por fim, uma última propriedade importante deste tipo de matriz é: o produto entre matrizes ortogonais resulta em outra matriz ortogonal.

Autovalores e Autovetores

Muitos conceitos matemáticos podem ser melhores compreendidos se formos capazes de quebrá-los em partes menores ou encontrando propriedades úteis. Como por exemplo, um número inteiro pode ser decomposto pelos seus fatores. Considere o número . Podemos escrevê-lo da seguinte forma: . A partir dessa decomposição podemos concluir que não é divisível por e que qualquer múltiplo dele também é divisível por . Desejamos utilizar esse conceito demostrado neste simples exemplo para matrizes. E uma forma de alcançar isso é utilizando os autovalores e autovetores. Este conceito é bem importante e muito utilizados em alguns algoritmos de machine learning. Por conta disso, vamos dar uma atenção especial a ele.

Definição e exemplos

Vamos começar definindo o que é um autovalor e autovetor de um operador linear. Seja um operador linear tal que , um vetor tal que , é chamado de autovetor de se existe um número real tal que:

Neste caso, é denominado autovalor de associado ao autovetor . Pela definição é possível perceber que geometricamente é um vetor que não muda de direção quando aplicamos o operador . Em outras palavras, um autovetor é um vetor que é levado em um múltiplo de si próprio.

Para entendermos melhor, vamos a dois exemplos:

Exemplo 1: Considere o operador linear tal que . Agora considere o vetor . Aplicando temos:

Neste caso, é um autovalor associado ao autovetor do operador .

Exemplo 2: Considere o operador linear tal que . Neste caso, observe que a seguinte equação é valida:

Neste caso, qualquer vetor é um autovetor de com autovalor igual a . Este exemplo mostra que um mesmo autovalor pode ser associando a vários autovetores.

Determinando autovalores e autovetores

Vamos entender o conceito através de um exemplo simples. Considere o operador linear descrito por . Determinar os autovalores e autovetores é a mesma coisa que: encontrar tal que exista e .

Isso é o mesmo que encontrar:

na qual . A título de curiosidade, o polinômio obtido por esta equação é chamado de polinômio característico.

Coincidentemente (só que não), caímos em um sistema linear igual ao da equação 12. Se ainda está por dentro dessa aula, você vai se lembrar que esse sistema possui uma solução não-nula se e somente se:

Portanto, o autovalores de são encontrados através da equação 34, se existirem. Por sua vez, os autovetores associados a cada autovalor são as soluções não nulas da equação 33.

Decomposição matricial por autovalores e autovetores

Para realizar uma decomposição matricial utilizando autovalores e autovetores temos que calculá-los para uma dada matriz. Todavia, já fizemos isso nas subseções anteriores e só vamos “substituir” o operador linear pela matriz. Portanto, dado uma matriz , os autovalores e autovetores são obtidos da seguinte forma:

Se você observar as equações 33 e 34 vai perceber que estamos fazendo exatamente a mesma coisa mas com uma notação diferente. Logo, para determinar seus autovalores e autovetores, vamos reescrever a equação 34 da seguinte forma:

Portanto, é um autovetor de associado a um autovalor se e somente se ambos satisfazem a equação 36. Caso queira um exemplo numérico, neste artigo da Wikipedia você encontra um excelente exemplo inclusive com uma ilustração bem legal do significado geométrico.

Dado a definição, agora temos que adentrar para a decomposição de fato. Porém, é necessário um teorema, que é descrito a seguir:

  • Se são autovetores de uma matriz com diferentes autovalores associados, então o conjunto de autovetores é linearmente independente

Tendo em vista o teorema acima, considere a matriz . Se essa matriz possui autovalores linearmente independentes, ou seja, basta aplicar o teorema acima, podemos decompor ela de acordo com os seguintes passos:

  1. Construir uma matriz composta pelos autovalores, um por coluna:
  2. Da mesma maneira, construir um vetor de autovalores:

A partir dos passos acima, a decomposição é obtida da seguinte forma:

Com já foi dito, essa decomposição é bastante útil para analisar algumas propriedades da matriz. Esses conceitos serão melhor abordados quando estivermos estudandando os algoritmos Análise de Componentes Principais (PCA) e Decomposição de Valores Singulares (SDV).

Considerações finais

Essa primeira aula é bastante teórica e muita gente pode achar ela chata. Mas se você pretende de fato aprender os algoritmos de machine learning para além de uma simples chamada de função em uma biblioteca, é importante saber a teoria por trás deles. Portanto, este começo a assim mesmo, mas acredite em mim, ainda vamos ser capazes de fazer bastante coisa interessante neste curso. A pŕoxima aula vamos entrar nos principais conceitos de Cálculo necessários em machine learning.

Principais referências

  • Deep learning - Ian Goodfellow, Yoshua Bengio e Aaron Courville link

  • Linear algebra review and reference - Zico Kolter link

  • Autovetor e Autovalor de um Operador Linear - Luis Crocco link

Deixe um comentário