Capítulo 03 - Álgebra linear

Álgebra linear é o ramo da matemática que lida com espaços vetoriais. Embora eu não possa esperar ensinar álgebra linear em um breve capítulo, ela sustenta um grande número de conceitos e técnicas de ciência de dados, o que significa que você deve pelo menos tentar. O que aprendemos neste capítulo usaremos fortemente durante o restante do estudo.

Vetores

De modo simples, os vetores são objetos que podem ser adicionados para formar novos vetores e podem ser multiplicados por escalares (ou seja, números), também para formar novos vetores.

Concretamente (para nós), os vetores são pontos em algum espaço finito-dimensional. Embora você possa não pensar em seus dados como vetores, eles geralmente são uma maneira útil de representar dados numéricos.

Por exemplo, se você tiver alturas, pesos e idades de um grande número de pessoas, poderá tratar seus dados como vetores tridimensionais [altura, peso, idade]. Se você está dando uma aula com quatro exames, pode tratar as notas dos alunos como vetores quadridimensionais [nota_1, nota_2, nota_2, noeta_2].

A abordagem mais simples é representar vetores como listas de números. Uma lista de três números corresponde a um vetor no espaço tridimensional e vice-versa.

Vejamos como criar um vetor:

from typing import List

Vetor = List[float]

altura_peso_idade = [178,  # centímetros

                     77,   # quilos

                     40    # anos

                     ]

notas = [95,  # exame 1

         80,  # exame 2

         75,  # exame 3

         62   # exame 4

         ]

Também queremos realizar aritmética em vetores. Como as listas de Python não são vetores (e, portanto, não fornecem instalações para a aritmética vetorial), precisamos construir essas ferramentas aritméticas. Então, vamos começar com isso.

Para começar, frequentemente precisamos adicionar dois vetores. Os vetores adicionam componente. Isso significa que, se dois vetores v e w têm o mesmo comprimento, sua soma é apenas o vetor cujo primeiro elemento é v[0] + w[0], cujo segundo elemento é v[0] + w[0] e assim por diante. Se eles não tiverem o mesmo comprimento, não podemos somá-los.

Por exemplo, adicionar os vetores [1, 2] e [2, 1] resulta em [1 + 2, 2 + 1] ou [3, 3], como mostra a Figura 1.

Podemos implementar facilmente isso, abrindo os vetores e usando uma compreensão de lista para adicionar os elementos correspondentes:

def somar(v: Vetor, w: Vetor) -> Vetor:

  """Somar os elementos correspondentes."""

  assert len(v) == len(w), 'Os vetores devem ter o mesmo tamanho'

  return [v_i + w_i for v_i, w_i in zip(v, w)]

assert somar([1, 2, 3], [4, 5, 6]) == [5, 7, 9]

Da mesma forma, para subtrair dois vetores, apenas subtraímos os elementos correspondentes:

def subtrair(v: Vetor, w: Vetor) -> Vetor:

  """Somar os elementos correspondentes."""

  assert len(v) == len(w), 'Os vetores devem ter o mesmo tamanho'

  return [v_i - w_i for v_i, w_i in zip(v, w)]

assert somar([1, 2, 3], [4, 5, 6]) == [5, 7, 9]

Às vezes, também queremos resumir componentes uma lista de vetores, ou seja, criar um novo vetor cujo primeiro elemento é a soma de todos os primeiros elementos, cujo segundo elemento é a soma de todos os segundos elementos, e assim por diante:

def soma_vetorial(vetores: List[Vetor]) -> Vetor:

  """Somar todos os elementos correspondentes."""

  # --- Verificar se há vetores informados --- #

  assert vetores, 'Não há vetores informados'

  # --- Verificar se os vetores tem o mesmo tamanho --- #

  num_elementos = len(vetores[0])

  assert all(len(v) == num_elementos for v in vetores), 'Vetores de diferentes tamanhos'

  # --- O i-ésimo elemento do resultado é a soma de vetor[i] --- #

  return [sum(vetor[i] for vetor in vetores)

          for i in range(num_elementos)]

assert soma_vetorial([[1, 2], [3, 4], [5, 6], [7, 8]]) == [16, 20]

Também precisaremos multiplicar um vetor por um escalar, o que fazemos simplesmente multiplicando cada elemento do vetor por esse número:

def multiplicacao_escalar(c: float, v: Vetor) -> Vetor:

  """Multiplicar cada elemento por c."""

  return [c * v_i for v_i in v]

assert multiplicacao_escalar(2, [1, 2, 3]) == [2, 4, 6]

Isso nos permite calcular as médias componentes de uma lista de vetores:

def media_vetorial(vetores: List[Vetor]) -> Vetor:

  """Calcula a média dos elementos."""

  n = len(vetores)

  return multiplicacao_escalar(1/n, soma_vetorial(vetores))

assert media_vetorial([1, 2], [3, 4], [5, 6]) == [3, 4]

Uma ferramenta menos óbvia é o produto dot. O produto dot de dois vetores é a soma de seus produtos:

def dot(v: Vetor, w: Vetor) -> float:

  """Calcular a soma dos produtos dos elementos correspondentes."""

  assert len(v) == len(w), 'Os vetores devem ter o mesmo tamanho'

  return sum(v_i * w_i for v_i, w_i in zip(v, w))

assert dot([1, 2, 3], [4, 5, 6]) == 32  # 1 * 4 + 2 * 5 + 3 * 6

Se w tiver magnitude 1, o produto dot mede até que ponto o vetor v se estende na direção w. Por exemplo, se w = [1, 0], então o dot(v, w) é apenas o primeiro componente de v. Outra maneira de dizer que é que é o comprimento do vetor que você obteria se você projetou v em w (Figura 2).

Usando isso, é fácil calcular a soma de quadrados de um vetor:

def soma_quadrados(v: Vetor) -> float:

  """Calcular a soma dos quadrados dos elementos do vetor."""

  return dot(v, v)

assert soma_quadrados([1, 2, 3]) == 14  # 1 * 1 + 2 * 2 + 3 * 3

Que podemos usar para calcular sua magnitude (ou comprimento):

def magnitute(v: Vetor) -> float:

  """Retorna a magnitude (comprimento) do vetor v."""

  return math.sqrt(soma_quadrados(v))  # math.sqrt() é a função da raíz quadrada

assert magnitute([3, 5]) == 5

Agora temos todas as peças que precisamos calcular a distância entre dois vetores, definidos como:

Em código:

def distancia_quadrado(v: Vetor, w: Vetor) -> float:

  """Calcular o quadrado da distância entre os elementos correspondentes dos vetores."""

  return soma_quadrados(subtrair(v, w))

def distancia(v: Vetor, w: Vetor) -> float:

  """Calcula a distância entre v e w."""

  return math.sqrt(distancia_quadrado(v, w))

Isso fica mais claro se escrevermos como:

def distancia(v: Vetor, w: Vetor) -> float:

  return magnitute(subtrair(v, w))

Isso deve ser muito para nos iniciar. Usaremos essas funções fortemente ao longo do estudo.

O uso de listas como vetores é ótimo para exposição, mas terrível para o desempenho. No código de produção, você deseja usar a biblioteca Numpy, que inclui uma classe de matriz de alto desempenho com todos os tipos de operações aritméticas incluídas.

Matrizes

Uma matriz é uma coleção bidimensional de números. Representaremos matrizes como listas de listas, com cada lista interna tendo o mesmo tamanho e representando uma linha da matriz. Se A é uma matriz, então A[i][j] é o elemento na i-ésima linha e na j-tésima coluna. Por convenção matemática, frequentemente usaremos letras maiúsculas para representar matrizes. Por exemplo:

Matriz = List[List[float]]

# --- A tem 2 linha e 3 colunas --- #

A = [[1, 2, 3],

     [4, 5, 6]]

# --- B tem 3 linhas e 2 colunas --- #

B = [[1, 2],

     [3 , 4],

     [5 , 6]]

Em matemática, você geralmente nomearia a primeira linha da matriz "Linha 1" e a primeira coluna "Coluna 1." Como estamos representando matrizes com listas de Python, que são indexadas zero, chamaremos a primeira linha de uma matriz de "linha 0" e a primeira coluna "coluna 0".

Dada essa representação de lista de listas, a matriz A possui colunas len(A) linhas e len(A[0]), que consideramos sua forma:

def shape(A: Matriz) -> Tuple[int, int]:

  """Retorna a quantidade de linhas e colunas de A."""

  num_linhas = len(A)

  num_colunas = len(A[0]) if A else 0  # números de elementos na primeira linha

  return num_linhas, num_colunas

assert shape([[1, 2, 3], [4, 5, 6]]) == (2, 3)  # 2 linhas e 3 colunas

Se uma matriz tiver n linhas e k colunas, iremos nos referir a ela como uma matriz n × k. Podemos (e às vezes) pensar em cada linha de uma matriz n × k como um vetor de comprimento k e cada coluna como um vetor de comprimento n:

def obter_linha(A: Matriz, i: int) -> Vetor:

  """Retorna a i-ésima linha de A como um Vetor."""

  return A[i]

def obter_coluna(A: Matriz, j: int) -> Vetor:

  """Retorna a j-tésima coluna de A como um Vetor."""

  return [A_i[j]        # j-tésimo elemento da linha A_i

         for A_i in A]  # para cada linha A_i

Também queremos criar uma matriz, dada sua forma e uma função para gerar seus elementos. Podemos fazer isso usando uma compreensão de lista aninhada:

def criar_matriz(num_linhas: int,

                 num_colunas: int,

                 fn_entrada: Callable[[int, int], float]) -> Matriz:

    """

    Retorna uma matriz de n_linhas x num_colunas a partir

    de uma função de entrada (fn_entrada(i, j)).

    """

    return [[fn_entrada(i, j)

            for j in range(num_colunas)]

            for i in range(num_linhas)]

Dada essa função, você pode fazer uma matriz de identidade 5 × 5 (com 1s na diagonal e 0s em outros lugares) desse modo:

def matriz_identidade(n: int) -> Matriz:

  """Criar uma matriz identidade n x n."""

  return criar_matriz(n, n, lambda i,j: 1 if i == j else 0)

assert matriz_identidade(5) == [[1, 0, 0, 0, 0],

                                [0, 1, 0, 0, 0],

                                [0, 0, 1, 0, 0],

                                [0, 0, 0, 1, 0],

                                [0, 0, 0, 0, 1]]

As matrizes serão importantes para nós por vários motivos. Primeiro, podemos usar uma matriz para representar um conjunto de dados que consiste em vários vetores, simplesmente considerando cada vetor como uma linha da matriz. Por exemplo, se você tivesse alturas, pesos e idades de 1000 pessoas, poderá colocá-las em uma matriz de 1000 × 3:

dados = [[70, 170, 40],

         [65, 120, 26],

         [77, 250, 19],

          # ....

         ]

Segundo, como veremos mais adiante, podemos usar uma matriz n × k para representar uma função linear que mapeia os vetores k-dimensionais para vetores n-dimensional. Várias de nossas técnicas e conceitos envolverão essas funções.

Terceiro, as matrizes podem ser usadas para representar relacionamentos binários. No Capítulo 1, representamos as conexões de uma rede como uma coleção de pares (i, j). Uma representação alternativa seria criar uma matriz A tais que A[i][j] seja 1 se os nós i e j estiverem conectados e 0 caso contrário:

amizades = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4),

            (4, 5), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9)]

Também poderíamos representar isso como:

           # usuário 0  1  2  3  4  5  6  7  8  9

matriz_amizade = [[0, 1, 1, 0, 0, 0, 0, 0, 0, 0], # usuário 0

                  [1, 0, 1, 1, 0, 0, 0, 0, 0, 0], # usuário 1

                  [1, 1, 0, 1, 0, 0, 0, 0, 0, 0], # usuário 2

                  [0, 1, 1, 0, 1, 0, 0, 0, 0, 0], # usuário 3

                  [0, 0, 0, 1, 0, 1, 0, 0, 0, 0], # usuário 4

                  [0, 0, 0, 0, 1, 0, 1, 1, 0, 0], # usuário 5

                  [0, 0, 0, 0, 0, 1, 0, 0, 1, 0], # usuário 6

                  [0, 0, 0, 0, 0, 1, 0, 0, 1, 0], # usuário 7

                  [0, 0, 0, 0, 0, 0, 1, 1, 0, 1], # usuário 8

                  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]] # usuário 9

Se houver poucas conexões, essa é uma representação muito mais ineficiente, pois você acaba tendo que armazenar muitos zeros. No entanto, com a representação da matriz, é muito mais rápido verificar se dois nós estão conectados - você só precisa fazer uma pesquisa de matriz em vez de (potencialmente) inspecionar todas as arestas:

assert matriz_amizade[0][2] == 1, '0 e 2 são amigos'

assert matriz_amizade[0][8] == 0, '0 e 8 não são amigos'

Da mesma forma, para encontrar as conexões de um nó, você só precisa inspecionar a coluna (ou a linha) correspondente a esse nó:

# --- Basta olhar apenas para uma linha --- #

amigos_do_5 = [i for i, amigo in enumerate(matriz_amizade[5]) if amigo]

Com um grafo pequeno, você pode simplesmente adicionar uma lista de conexões a cada objeto de nó para acelerar esse processo; mas para um grafo grande e em evolução que provavelmente seria muito caro e difícil de manter. Vamos revisitar matrizes ao longo do nosso estudo.

Para uma exploração adicional

A álgebra linear é amplamente utilizada pelos cientistas de dados. Não seria uma má ideia ler um livro. Você pode encontrar vários disponíveis gratuitamente online:

• Linear Algebra, por David Cherney, Tom Denton, Rohit Thomas e Andrew Waldron (UC Davis);

• Se você está se sentindo aventureiro, Linear Algebra Done Wrong, por Sergei Treil (Brown University), é uma introdução mais avançada.

Os livros estão em inglês, mas nada que um Google tradutor não resolva.

Todas as funções que construímos neste capítulo que você recebe de graça se usar o Numpy. Você também obtém muito mais, incluindo desempenho muito melhor.