Aprendizado de máquina e redes neurais - página 27

 

Aula 12. Calculando Autovalores e Valores Singulares



12. Cálculo de Autovalores e Valores Singulares

Neste vídeo, é apresentado o método QR para calcular autovalores e valores singulares. O processo envolve começar com a matriz desejada e fatorá-la em QR, criando uma matriz triangular superior R que conecta a base não ortogonal com a base ortogonal. O processo é iterado até que as entradas diagonais se tornem pequenas, ponto em que elas podem ser usadas para aproximar os autovalores. O palestrante também discute um método de deslocamento para calcular autovetores para acelerar o processo. Os benefícios do uso do MATLAB para matrizes simétricas também são destacados. O vídeo também aborda o conceito de vetores Krylov para resolver problemas de autovalor para grandes matrizes.

  • 00:00:00 Nesta seção, o professor apresenta o método QR para calcular autovalores e valores singulares de uma matriz. O método QR envolve começar com uma matriz cujos autovalores são desejados e fatorá-la em QR. As colunas da matriz são transformadas em uma base ortogonal ortogonalizando-as e criando uma matriz R que conecta a base não ortogonal com a base ortogonal, que é triangular superior. Em seguida, o método envolve inverter a ordem e fazer a mesma coisa novamente para produzir a próxima matriz. O professor afirma que os autovalores são os mesmos antes e depois da transformação, e as matrizes são semelhantes, o que é útil para calcular os valores singulares da matriz.

  • 00:05:00 Nesta seção, o professor explica o processo de cálculo de autovalores usando fatoração QR. O processo envolve iterar a fatoração QR várias vezes até que as entradas diagonais da matriz resultante se tornem muito pequenas. Neste ponto, as entradas diagonais estão próximas dos autovalores reais da matriz original e podem ser usadas para aproximá-los. O professor também destaca a rápida convergência do método, com as entradas fora da diagonal ficando cúbicas e se aproximando rapidamente de zero, tornando o método extremamente preciso.

  • 00:10:00 Nesta seção, o vídeo discute uma melhoria no algoritmo para calcular autovetores, que envolve a introdução de um deslocamento. Em vez de pegar a matriz A, eles pegam a matriz A - siI, onde si é algum múltiplo da matriz identidade. Isso desloca todos os autovalores da matriz A por si. Eles então trabalham com essa matriz deslocada, executam o processo de Gram-Schmidt e invertem a ordem para obter uma matriz que seja o mais próxima possível de A. Finalmente, eles desfazem o deslocamento para obter uma nova matriz, A1. A esperança é que A1 ainda seja semelhante a A, mas com um tempo computacional mais rápido.

  • 00:15:00 Nesta seção, o professor discute o método QR para calcular autovalores de uma matriz. Ele demonstra um exemplo incompleto onde usa o método QR para mostrar que a parte triangular inferior da matriz começa a desaparecer e os autovalores começam a aparecer na diagonal. O professor então discute como melhorar a eficiência do método QR aproveitando quaisquer zeros na matriz original. Se houver diagonais extras com zeros, o método pode ser acelerado pulando algumas etapas no processo de fatoração QR.

  • 00:20:00 Nesta seção, o palestrante discute como calcular autovalores e valores singulares. Não é possível obter todos os autovalores, pois é impossível obter toda uma parte triangular inferior igual a zero, o que nos daria os autovalores. Isso ocorre porque os autovalores resolvem uma equação de grau enésimo e, séculos atrás, provou-se que é impossível resolver uma equação instantânea por etapas simples. Além disso, não existe uma fórmula simples para encontrar lambdas ou valores singulares. No entanto, é possível chegar o mais próximo possível, continuando com o método QR e reduzindo uma matriz à forma de Hessenberg com um triangular mais um diagonal, mas muitos zeros. O MATLAB e outros sistemas matriciais usam la pack e Linpack para calcular esses valores.

  • 00:25:00 Nesta seção do vídeo, o palestrante discute os benefícios do uso do MATLAB e fornece informações sobre as características das matrizes simétricas. Ele explica que, se uma matriz é simétrica, pode-se prever com segurança que ela terá apenas uma diagonal acima da diagonal principal, tornando-a uma matriz tri-diagonal. Isso reduz significativamente o tempo para fazer o cálculo do QR, pois requer apenas trabalhar com 2n números em vez de N^2. O palestrante também aborda brevemente os valores singulares, afirmando que eles são os autovalores de uma matriz de transposição, mas adverte contra calculá-los usando determinantes, pois é lento, mal condicionado e leva à perda de informações.

  • 00:30:00 Nesta seção, o palestrante discute o conceito de usar matrizes ortogonais para simplificar matrizes simétricas, tornando-as tridiagonais para que seus autovalores possam ser facilmente encontrados. Em seguida, o falante coloca a questão do que pode ser feito com uma matriz geral para simplificá-la de forma a deixar seus valores singulares inalterados. O palestrante conecta essa questão ao SVD e discute a invariância dos valores singulares sob certas operações, como a multiplicação por uma matriz ortogonal. A questão de quais outras operações deixam os valores singulares invariantes é deixada em aberto para o público considerar.

  • 00:35:00 Nesta seção, o palestrante discute o efeito de multiplicar uma matriz ortogonal Q em uma matriz diagonal com valores singulares. É mostrado que a multiplicação de Q na matriz diagonal não altera os valores singulares e que isso pode ser feito em ambos os lados da equação usando diferentes matrizes ortogonais. Essa maior flexibilidade permite que a matriz seja reduzida de tri-diagonal para bi-diagonal, o que torna o algoritmo mais rápido à medida que avança em cada etapa. O palestrante também discute a utilidade de uma matriz bi-diagonal na simplificação da multiplicação de matrizes.

  • 00:40:00 Nesta seção, o palestrante discute o cálculo de autovalores e valores singulares, especificamente para matrizes de ordem até mil. O SVD envolve olhar para uma transposta de uma matriz, que seria tri-diagonal. Para encontrar valores singulares, pode-se chegar à transposição de uma matriz, mas encontrar seus autovalores exigiria que ela fosse simétrica e tri-diagonal. Este método é eficaz para matrizes até um determinado tamanho, além do qual o método de Krylov pode ser usado para matrizes esparsas. O método de Krylov restringe a matriz a um determinado tamanho, normalmente cem por cem, e encontra o autovetor naquele espaço.

  • 00:45:00 Nesta seção, o palestrante explica uma abordagem chamada vetores Krylov que pode ser usada para resolver problemas de autovalor para grandes matrizes. Aplicando a operação matricial aos vetores Krylov, que possuem uma dimensão menor que a matriz original, um problema de autovalor menor pode ser criado e resolvido. Embora não forneçam autovalores exatos, os vetores de Krylov podem fornecer boas aproximações para certos problemas. O palestrante também apresenta a ideia de amostragem aleatória para grandes matrizes e menciona que isso será explorado na próxima aula.
 

Aula 13: Multiplicação de Matrizes Randomizadas



Aula 13: Multiplicação de Matrizes Randomizadas

Esta videoaula discute o conceito de multiplicação aleatória de matrizes, que envolve a amostragem das colunas da matriz A e das linhas correspondentes da matriz B com probabilidades que somam um. O valor médio das amostras aleatórias pode ser calculado para obter a resposta correta, mas ainda haverá variação. A palestra continua a discutir os conceitos de média e variância e como escolher as melhores probabilidades que minimizam a variância. O processo envolve a introdução de uma variável desconhecida chamada Lambda e derivações em relação a ela para encontrar o melhor PJ. O foco então muda para a questão de como ponderar as probabilidades ao observar quais colunas em uma matriz são maiores ou menores. O palestrante sugere duas possibilidades: ponderar as probabilidades de acordo com a norma ao quadrado ou misturar as colunas da matriz e usar probabilidades iguais. No geral, o vídeo fornece uma explicação detalhada da multiplicação de matrizes aleatórias e o processo de otimização de probabilidades para obter a menor variância.

  • 00:00:00 Nesta seção do vídeo, o palestrante explica o conceito de multiplicação de matrizes aleatórias, que é uma ideia que se enquadra na álgebra linear aleatória. Este método é usado para matrizes grandes, amostrando as colunas da matriz A e as linhas correspondentes da matriz B, mas não todas elas. Em vez disso, peças diferentes são amostradas aleatoriamente com probabilidades que somam um. Ao calcular o valor médio das amostras aleatórias, a resposta correta pode ser obtida, mas ainda haverá variação. O objetivo então é escolher as melhores probabilidades que minimizam a variância. A palestra continua discutindo os conceitos de média e variância e praticando com um exemplo.

  • 00:05:00 Nesta seção, o palestrante descreve um processo de amostragem aleatória para multiplicação de matrizes. O processo envolve pegar duas colunas com probabilidades de metade cada, adicioná-las e depois dividir pelo número de vezes que são amostradas. A média da matriz aleatória é então calculada usando a fórmula para calcular a média das duas amostras. A variância é calculada usando qualquer um dos dois métodos, um dos quais envolve a adição das probabilidades de diferentes valores de saída ao quadrado, enquanto o outro envolve a tomada da distância média ao quadrado da média.

  • 00:10:00 Nesta seção do vídeo, o palestrante discute os conceitos de média e variância em estatística e como eles se relacionam com seu exemplo atual de computação de variância para multiplicação de matrizes aleatórias. Ele explica que a variância é uma medida da soma dos quadrados entre os pontos de cada lado da média e que, em seu exemplo, ele está somando os quadrados das diferenças entre sua produção e a média. Ele então calcula a variância para seu exemplo específico, que envolve dois resultados possíveis e probabilidades para cada um.

  • 00:15:00 Nesta seção, o palestrante discute o cálculo da variância e apresenta uma nova fórmula para a variância usando probabilidades e distâncias da média ao quadrado. O palestrante também traz o conceito de amostragem aleatória em álgebra linear e como o ajuste de probabilidades pode ajudar a diminuir a variância quando B é muito maior que A. A probabilidade ideal vem do quadrado do tamanho de B dividido por A, e os planos do palestrante para discutir isso mais adiante no futuro. Por fim, o palestrante menciona uma segunda fórmula para variância que envolve probabilidade e distância da saída ao quadrado.

  • 00:20:00 Nesta seção, o palestrante discute a média e a variação da probabilidade e demonstra as duas maneiras de calcular a média ao quadrado ao subtrair a média. O foco então muda para a questão de como ponderar as probabilidades ao observar quais colunas em uma matriz são maiores ou menores. O palestrante sugere duas possibilidades: ponderar as probabilidades de acordo com a norma ao quadrado ou misturar as colunas da matriz e usar probabilidades iguais. O palestrante prefere a primeira abordagem e explica como usar probabilidades proporcionais à norma ao quadrado.

  • 00:25:00 Nesta seção, o palestrante explica como redimensionar as probabilidades para que elas somem um. Ele então discute seu plano para escolher linha coluna e coluna linha J com probabilidades particulares e como ele irá multiplicá-las. Sua aproximação, o aB aproximado, será a soma de todas essas amostras sobre S amostras. O palestrante também menciona que o plano é escolher os PJs para minimizar a variância total e que a média esteja correta.

  • 00:30:00 Nesta seção, o palestrante explica como calcular a variância de uma amostra na multiplicação de matrizes aleatórias. A média da soma de todas as amostras é calculada multiplicando a média de uma amostra pelo número de amostras, o que leva à parte difícil de calcular a variância. O cálculo da variação dependerá da peça, P1 a PR que foi escolhida com probabilidades dependentes do tamanho. Cada amostra certamente está errada porque é uma classificação, então, ao calcular a variância, definitivamente não obteremos zero. A variância de uma amostra acaba sendo a soma da probabilidade de transposição AJ AJ ao quadrado. A média ao quadrado é subtraída desse cálculo para obter a variância completa.

  • 00:35:00 Nesta seção, o alto-falante conecta os valores para PJ e simplifica o denominador para uma soma de um JPG de um JP j bj normas. Somando a primeira potência e obtendo C, o falante obtém a expressão para a variância. Depois de pegar s amostras e combiná-las, a variação é um número fixo, que é C que eles gostariam de diminuir. O falante deseja mostrar que esta é a melhor escolha escolhendo os pesos das probabilidades com base no comprimento de a vezes o comprimento de B.

  • 00:40:00 Nesta seção, o palestrante discute a etapa final de otimização das probabilidades P1 a PR para as linhas ou colunas da matriz A e as linhas da matriz B, sujeitas à restrição de que somam 1. O objetivo é minimizar a expressão de variância escolhendo os PJs ótimos. O palestrante introduz a ideia de Lagrange para construir a restrição na função, introduzindo um número desconhecido, muitas vezes chamado de lambda, para encontrar o melhor PJ. Esta seção conclui a discussão sobre amostragem aleatória e conduz ao subproblema final.

  • 00:45:00 Nesta seção, o palestrante discute o conceito da ideia de Lagrange na otimização de probabilidades sob a condição de que elas somem um. O processo envolve construir a equação na função e derivar em relação a lambda, uma variável desconhecida. Depois de zerar as derivadas e resolver, chega-se à resposta final recomendada, que pode ser validada tomando a derivada em relação a P. O palestrante também explica que o multiplicador de Lagrange é o número correto para tornar a equação igual a um.

  • 00:50:00 Nesta seção, o professor explica o processo de escolha de probabilidades para obter a menor variância em um sistema aleatório. Ele menciona que as probabilidades ideais são maiores quando a coluna é maior, portanto, encontrar os comprimentos das colunas é um pré-requisito antes da amostragem aleatória. Embora a variância possa ser um pouco desafiadora de calcular, ele incentiva os alunos a ler as anotações lentamente e revisitar as fórmulas para melhor compreensão, pois eles usarão a probabilidade com mais seriedade no futuro.
 

Aula 14. Mudanças de classificação baixa em A e seu inverso



14. Mudanças de classificação baixa em A e seu inverso

O vídeo discute o conceito de matrizes de posto baixo e sua importância em matrizes de funções, particularmente a fórmula de inversão de matrizes que encontra o inverso de uma matriz N por n em termos de uma matriz 1 por 1 mais simples. A fórmula é útil para encontrar o inverso de matrizes com perturbações de classificação baixa e pode simplificar o processo de encontrar inversos. O palestrante mostra como a fórmula funciona apresentando a fórmula para a segunda matriz e mostra como a mesma lógica foi aplicada para chegar à resposta. O vídeo também discute aplicações práticas desta fórmula, particularmente em problemas de mínimos quadrados e o filtro de Kalman.

  • 00:00:00 Nesta seção, o professor discute o conceito de matrizes de posto baixo e sua importância em matrizes de funções. O tópico de foco é uma fórmula famosa chamada fórmula de inversão de matrizes, também conhecida como mudanças de classificação baixa em A e seu inverso. A fórmula encontra o inverso de uma matriz N por n em termos de uma matriz 1 por 1 mais simples usando uma transposta UV e dividindo-a por 1 menos a transposta de V vezes U. A fórmula é útil para encontrar a inversa de matrizes que têm baixo perturbações rank e pode ser usado para simplificar o processo de encontrar inversas. O professor explica como funciona essa fórmula e suas aplicações práticas.

  • 00:05:00 Nesta seção, o palestrante discute como a mudança de uma matriz de posto 1 resultará em uma mudança em seu inverso de posto um. A fórmula que ele apresenta calcula um inverso de N por n em termos de um inverso de 1 por 1, o que é muito útil. O palestrante então demonstra como verificar a fórmula multiplicando o inverso reivindicado pela matriz original e esperando obter uma matriz identidade. O palestrante mostra como a fórmula funciona apresentando a fórmula para a segunda matriz e mostra como a mesma lógica foi aplicada para chegar à resposta.

  • 00:10:00 uma fórmula para uma mudança de classificação baixa na matriz A e seu inverso. A fórmula envolve tomar o inverso de uma matriz N por n, mas pode ser alterada para uma matriz K por K, que é uma perturbação menor da matriz de identidade. A fórmula se mostra verdadeira através de uma verificação e pode ser útil para perturbar uma matriz A. Os nomes das pessoas que descobriram esta fórmula também estão listados.

  • 00:15:00 Nesta seção, o palestrante está discutindo as mudanças que ocorrem ao tomar a inversa de uma matriz A de posto baixo. Eles usam manipulações algébricas para mostrar que ao tomar a inversa de A, existem certos termos que podem ser eliminado, levando a uma expressão simplificada. O palestrante observa que, embora sejam capazes de provar a fórmula verificando se ela produz a matriz de identidade, é importante considerar como a fórmula pode ser derivada em primeiro lugar. Eles sugerem usar a fórmula para resolver um sistema linear com uma nova medição ou observação no método dos mínimos quadrados.

  • 00:20:00 Nesta seção, o palestrante explica como lidar com novas medições ao resolver problemas de mínimos quadrados. Com uma matriz retangular A, adicionar mais uma medida ou ponto de dados à solução resulta em uma nova matriz e lado direito a ser resolvido. No entanto, em vez de recalcular a multiplicação da matriz A^TA, o palestrante descreve como expandir a matriz com a nova medição, transpô-la e usá-la para calcular a solução atualizada. Ao usar o que já foi calculado, isso permite uma solução computacionalmente mais eficiente de problemas de mínimos quadrados.

  • 00:25:00 Nesta seção, o palestrante discute a perturbação de A e seu inverso com novos dados, o que fornece uma alteração de classificação 1 em A transposta A. Esse conceito é aplicável a problemas de mínimos quadrados, e o filtro de Kalman é um exemplo de um método de mínimos quadrados recursivo que usa essa abordagem. O filtro de Kalman é utilizado para guiar mísseis e satélites rastreando novos dados e atualizando a solução, o que é uma importante aplicação deste conceito na prática.

  • 00:30:00 Nesta seção do vídeo, o palestrante explica como aplicar a fórmula de Sherman-Morrison-Woodbury para calcular mudanças de classificação baixa em A e seu inverso. Eles mencionam que o filtro de Kalman, que é usado para mínimos quadrados dinâmicos, tem dois fatores adicionais que são levados em consideração - a matriz de covariância e a equação de estado. A matriz de covariância trata de como os erros são correlacionados, e a equação de estado informa quanto o satélite (no exemplo) deve estar se movendo. O filtro de Kalman é uma versão aprimorada de quadrados recursivos que lida com a mudança de medidas, deixando uma grande parte inalterada.

  • 00:35:00 Nesta seção, o palestrante discute o uso da fórmula de atualização de classificação baixa na solução de sistemas lineares. A fórmula envolve perturbar a matriz de um problema resolvido por nível um e usar o inverso da matriz original para resolver rapidamente o novo problema. Essa abordagem pode reduzir significativamente o tempo necessário para resolver um novo problema e é especialmente útil para grandes matrizes em que os métodos de eliminação tradicionais seriam demorados.

  • 00:40:00 Nesta seção, o palestrante explica como encontrar a inversa de uma matriz combinando soluções para diferentes problemas. Ao fatorar a matriz A em Lu, todo o trabalho pesado é feito no lado esquerdo, e encontrar as soluções para os diferentes lados à direita requer apenas a substituição inversa. Usando a fórmula de Sherman-Morrison-Woodbury, a resposta X pode ser obtida combinando as soluções W e Z. A fórmula altera a solução W por um termo que vem de Sherman-Morrison Woodbury, e o termo no numerador é um múltiplo de Z vezes X.

  • 00:45:00 Nesta seção, o palestrante discute como mudanças de classificação baixa em uma matriz A podem afetar seu inverso e fornece uma fórmula para inverter uma matriz N por N alternando e invertendo uma matriz K por K. A fórmula envolve a subtração de uma cópia do inverso e a adição de algumas outras peças e, finalmente, resulta em uma mudança de classificação K para o inverso original. O palestrante observa que esta fórmula tem aplicações práticas e incentiva os espectadores a escrevê-la para referência futura.

  • 00:50:00 Nesta seção, o palestrante discute o inverso de uma matriz K por K e reconhece a abundância de fórmulas abordadas na hora e 50 minutos anteriores. A seção conclui afirmando que as notas abrangem algumas aplicações e passarão a abordar outros aspectos do baixo escalão.
 

Aula 15. Matrizes A(t) Dependendo de t, Derivada = dA/dt



15. Matrizes A(t) Dependendo de t, Derivada = dA/dt

Este vídeo aborda vários tópicos relacionados a matrizes, incluindo mudanças em matrizes e suas inversas, bem como mudanças em autovalores e valores singulares ao longo do tempo. O palestrante explica as principais fórmulas para calcular essas mudanças e enfatiza a importância de entender o cálculo na álgebra linear. Além disso, a palestra discute a importância da normalização e explora teoremas entrelaçados para autovalores em matrizes simétricas e de classificação 1. Por fim, o vídeo termina com uma revisão dos tópicos abordados e com a promessa de expandi-los em palestras futuras.

  • 00:00:00 Nesta seção, o palestrante discute as mudanças em matrizes, autovalores e valores singulares quando uma matriz muda. O foco está na compreensão das fórmulas para a mudança na matriz inversa, a derivada da inversa e mudanças nos autovalores e valores singulares quando uma matriz muda. O palestrante explica que, embora uma fórmula exata para a mudança de autovalores e valores singulares não possa ser
    possível, eles ainda podem derivar desigualdades para entender o tamanho da mudança. A palestra também aborda a configuração da matriz A, que depende do tempo (T) e o inverso A inverso.

  • 00:05:00 Nesta seção, o palestrante discute uma identidade em cálculo que complementa a discussão da seção anterior sobre a inversa de matrizes. A fórmula afirma que a derivada da matriz inversa é igual a menos um vezes o inverso da matriz, multiplicado pela derivada da matriz e o inverso da matriz. O palestrante explica como encontrar a derivada da matriz inversa chamando-a de "mudança no inverso" e dividindo ambos os lados da fórmula por delta T. Finalmente, o palestrante aplica o cálculo para deixar Delta T ir para zero, levando a uma compreensão da fórmula. O palestrante também expressa sua opinião sobre a ênfase do cálculo na matemática universitária, afirmando que ofusca a álgebra linear.

  • 00:10:00 Nesta seção, o palestrante explica a fórmula para a derivada de uma matriz A como dA/dt em relação ao tempo t, quando delta T vai para zero. A proporção Delta a dividida pela Delta T tem um significado e, à medida que Delta T se aproxima de zero, a equação se torna inversa. A derivada de um sobre X no caso um a um é apenas 1 sobre X ao quadrado, e isso é paralelo às fórmulas quando Delta a é de tamanho normal, mas de classificação baixa. O foco da palestra então muda para os autovalores de lambda e como eles mudam quando uma matriz muda, com duas possibilidades, uma pequena mudança e uma ordem de tamanho real de uma mudança. A palestra termina com fatos envolvendo autovalores e autovetores.

  • 00:15:00 Nesta seção, é explicado o conceito de autovetores e autovalores para matrizes que dependem de um parâmetro. A matriz A é explorada em detalhes, com o autovetor X à esquerda, que tem o mesmo autovalor de AX. Em contraste, o autovetor Y, para uma matriz simétrica A, é usado da mesma forma com a transposta de A ou AT. A importância da normalização, especificamente Y transposta vezes X igual a um, é enfatizada. O autor passa a derivar uma fórmula e discute como contorcer a equação para ajustá-la a esse novo contexto.

  • 00:20:00 Nesta seção, o palestrante explica como a derivada de uma matriz pode ser usada para encontrar a derivada de seus autovalores e autovetores à medida que o tempo muda. Usando a regra do produto, eles derivam uma fórmula para a derivada do produto de três termos que dependem do tempo. Ao reorganizar os termos e aplicar a fórmula de diagonalização, eles chegam a uma fórmula simples para a derivada do autovalor. O palestrante observa que, embora seja uma técnica clássica, nem sempre é amplamente conhecida ou ensinada em cursos.

  • 00:25:00 Nesta seção, o palestrante discute uma fórmula para encontrar a derivada de um autovalor usando a taxa na qual a matriz está mudando e os autovetores à esquerda e à direita. Eles simplificam a fórmula para mostrar que dois termos se cancelam e o termo restante é a resposta correta para a derivada. Eles usam o fato de que a derivada de um é zero para provar esse cancelamento. O palestrante também menciona que esta fórmula não envolve a derivada do autovetor e também pode ser usada para encontrar derivadas de nível superior.

  • 00:30:00 Nesta seção, o palestrante discute a mudança nos autovalores após uma mudança de nível um para uma matriz simétrica. Ele observa que a mudança é um vetor verdadeiro e não um diferencial, portanto não há uma fórmula exata para os novos autovalores. No entanto, ele compartilha alguns fatos conhecidos, como os autovalores estão em ordem decrescente e a mudança de posto um é positiva semidefinida. Ele também pede ao público que considere o autovetor da matriz de transposição uu e explica que é uma coluna de matriz n por n completa vezes uma linha. Ele conclui afirmando que o número resultante desse cálculo é maior que zero.

  • 00:35:00 Nesta seção, o palestrante discute uma matriz simétrica e o que acontece quando uma matriz de classificação um é adicionada a ela. Eles concluem que isso resulta em matrizes semidefinidas positivas, e os novos autovalores (lambdas) são maiores que os autovalores originais (gamas). No entanto, a diferença de tamanho não é significativa e existe um teorema chamado "entrelaçamento" que garante que os autovalores não passem um para o outro. Especificamente, lambda 1 é maior que gamma 1, mas lambda 2 é menor que gamma 1. Este é um teorema útil que garante a ordem dos autovalores quando uma matriz positiva de posto um é adicionada a uma matriz simétrica.

  • 00:40:00 Nesta seção, o professor discute os autovalores de uma matriz de posto 2 resultante de uma matriz simétrica e uma mudança de posto 1. Ele explica que o posto da matriz de mudança é 2, indicando dois autovalores diferentes de zero, e sua natureza semidefinida positiva significa que os autovalores aumentariam ao adicioná-los à matriz original. No entanto, ele revela um teorema que afirma que os autovalores não podem ser maiores que os autovalores originais ao adicionar uma matriz positiva semidefinida. Ele aplica isso aos valores alfa e os compara com os lambdas, concluindo que o valor alfa 2 não pode ultrapassar o lambda 1 e o valor alfa 3 permanece desconhecido.

  • 00:45:00 Nesta seção, o palestrante explica o entrelaçamento de autovalores com um exemplo de matriz simétrica. A versão reduzida desta matriz também possui autovalores, e eles se entrelaçam com os autovalores da matriz original. No entanto, o palestrante levanta uma preocupação sobre o entrelaçamento de autovalores quando o posto é alterado. Se o novo autovetor for multiplicado por um número grande, ele pode mover o autovalor para cima, o que parece contradizer o teorema do entrelaçamento. O palestrante deixa isso como uma pergunta para responder na próxima aula.

  • 00:50:00 Nesta seção, o palestrante discute autovalores e autovetores e por que um determinado autovetor com um autovalor lambda 2 mais 20 não invalida as declarações anteriores feitas. A palestra é encerrada com uma revisão dos tópicos abordados e uma nota para continuar a discussão na próxima aula.
 

Aula 16. Derivadas de Valores Inversos e Singulares


16. Derivadas de Valores Inversos e Singulares

Este vídeo cobre uma variedade de tópicos, incluindo a derivada dos valores inversos e singulares de uma matriz, entrelaçamento e a norma nuclear de uma matriz. O palestrante apresenta uma fórmula para a derivada de valores singulares, usando o SVD, para entender como uma matriz muda ao longo do tempo, enquanto estabelece limites para mudanças em autovalores em matrizes simétricas. A desigualdade de Vial é introduzida como uma forma de estimar os valores lambda de uma matriz, e a busca de bases é usada em problemas de completação de matrizes. O palestrante também discute a ideia de que a norma nuclear de uma matriz vem de uma norma que não é bem uma norma e introduz o conceito de laço e sensoriamento comprimido a ser discutido na próxima palestra.

  • 00:00:00 Nesta seção, o instrutor discute vários tópicos, incluindo encontrar a derivada da inversa de uma matriz, a derivada de um autovalor e a derivada do valor singular. O instrutor compartilha uma fórmula para a derivada do valor singular, que descobriu recentemente, e menciona que a fórmula para a derivada do inverso não é simplesmente a derivada da matriz original. Ele também fala sobre o dever de casa do laboratório, pede conselhos sobre um projeto e menciona a próxima palestra do professor Townsend sobre álgebra linear aplicada. O instrutor continua explicando como encontrar sistematicamente a derivada de uma matriz quadrada e por que a fórmula comumente assumida está incorreta.

  • 00:05:00 Nesta seção, o palestrante discute a derivada de valores singulares, que é semelhante à derivada de autovalores. A fórmula para a derivada de valores singulares é dada pela transposta de da/dt vezes o vetor singular de a. Essa fórmula se baseia no SVD, que diz que a vezes V é igual a Sigma U. Usando esses fatos e manipulando a equação, é possível derivar a fórmula para a derivada de valores singulares. Essa fórmula é útil para entender como uma matriz muda com o tempo e pode ser aplicada em vários campos, como física e engenharia.

  • 00:10:00 Nesta seção, o palestrante discute as derivadas de valores inversos e singulares. Eles começam explicando a fórmula para os valores singulares em termos do SVD de uma matriz e, em seguida, calculam a derivada da equação. O palestrante usa a regra do produto e simplifica a equação resultante para encontrar o termo que dará a resposta que procura. Eles então demonstram que os outros dois termos serão zero, o que prova que o termo escolhido é o correto. Finalmente, eles usam produtos escalares e um número para mostrar que a derivada de U com U transposta é igual a zero.

  • 00:15:00 Nesta seção, o palestrante discute derivadas de valores singulares e autovalores de uma matriz simétrica. Embora não seja possível calcular uma fórmula exata para a mudança nos valores próprios ou singulares, os limites podem ser estabelecidos reconhecendo que mudanças positivas nos valores próprios não farão com que eles diminuam. O entrelaçamento dos valores antigos e novos é ilustrado pelo fato de que o segundo autovalor não excederá o primeiro autovalor antigo, e o primeiro novo autovalor não será menor que o primeiro autovalor antigo, tornando esses conceitos úteis para entender o SVD.

  • 00:20:00 Nesta seção do vídeo, o palestrante apresenta uma questão de quebra-cabeça sobre o efeito de exagerar o segundo autovetor nos autovalores de uma matriz. Ele aponta que se o segundo autovalor for aumentado em uma certa quantidade, denotada como Theta, ele pode eventualmente superar o primeiro autovalor, o que representa um problema potencial. No entanto, ele explica seu processo de pensamento e mostra que isso não é realmente um problema porque o primeiro autovalor permanece inalterado, enquanto o segundo autovalor é aumentado, mas eventualmente converge para a soma de lambda 1 e Theta.

  • 00:25:00 Nesta seção, o palestrante discute o entrelaçamento e a desigualdade de Vial. A desigualdade de Vial é uma forma de estimar os valores lambda de uma matriz, que são os autovalores ordenados do maior para o menor. A desigualdade é verdadeira para qualquer matriz simétrica e afirma que o maior autovalor da soma de duas matrizes simétricas é menor ou igual à soma dos maiores autovalores de cada matriz individualmente. Essa propriedade de entrelaçamento é válida não apenas para perturbações de nível um, mas também para perturbações de outros níveis. O palestrante usa o exemplo de adicionar uma matriz positiva, T, em S e explica como isso se relaciona com a desigualdade de Vial.

  • 00:30:00 Nesta seção, o palestrante discute a desigualdade de Vile e como ela se relaciona com o entrelaçamento. A desigualdade de Vile dá um limite de quanto um autovalor pode aumentar, e esse fato é crucial para a compreensão do fenômeno de entrelaçamento. O palestrante menciona que existem duas maneiras de provar o entrelaçamento, incluindo a desigualdade de Vile e outro método envolvendo um gráfico. A seção também apresenta a detecção comprimida, que será discutida na próxima parte do vídeo.

  • 00:35:00 Nesta seção, é introduzido o conceito de norma nuclear de uma matriz, que é a soma dos valores singulares da matriz. Isso pode ser pensado como a norma L1 para um vetor. Tem uma propriedade especial, semelhante à norma L1, onde minimizar a norma nuclear com uma restrição resulta em uma solução esparsa. Esta propriedade é útil em problemas de completação de matrizes, onde os dados que faltam em uma matriz precisam ser preenchidos. Os números que minimizam a norma nuclear são uma boa escolha para preencher os dados que faltam. A norma zero de um vetor, que representa o número de não zeros, não é uma norma, mas pode ser movida para a norma mais próxima, que é a norma L1. Esta norma é a soma dos valores absolutos das componentes do vetor. Minimizar essa norma sujeita a algumas condições é chamado de busca de base e é usado em problemas de completação de matrizes.

  • 00:40:00 Nesta seção, o palestrante discute a ideia de que a norma nuclear de uma matriz vem de uma norma que não é bem uma norma. Ele explica que o posto da matriz é equivalente a essa norma, mas deixa de ser uma norma porque não é escalável se o tamanho da matriz for dobrado. O palestrante passa a descrever a conjectura de que o algoritmo de aprendizagem profunda de gradiente descendente encontra a solução para o problema mínimo na norma nuclear e apresenta o conceito de laço e detecção comprimida que será discutido na próxima palestra.
 

Aula 17: Diminuindo Rapidamente Valores Singulares



Aula 17: Diminuindo Rapidamente Valores Singulares

A palestra enfoca matrizes e suas classificações, e como os valores singulares decrescentes são predominantes na matemática computacional. O palestrante examina matrizes de classificação baixa e demonstra como elas têm muitos zeros em sua sequência de valores singulares, tornando mais eficiente enviar a matriz a um amigo na forma de classificação inferior do que na forma de classificação completa. Eles também introduzem a classificação numérica de uma matriz, que é definida permitindo algum espaço de manobra para definir a tolerância de valores singulares de uma matriz. Ao amostrar funções suaves, que podem ser bem aproximadas por polinômios, a classificação numérica pode ser baixa, resultando em uma aproximação de classificação baixa da matriz X. A palestra também inclui exemplos de matrizes gaussianas e de Vandermonde para explicar como elas podem levar a matrizes de baixo escalão e discute a utilidade dos números de Zolotarev na delimitação de valores singulares.

  • 00:00:00 Nesta seção, um professor explica por que as matrizes de classificação baixa são tão prevalentes no mundo da matemática computacional. Ele discute a importância dos valores singulares, que nos informam sobre o posto de uma matriz e quão bem ela pode ser aproximada por uma matriz de posto baixo. Ele continua explicando que uma matriz X pode ser decomposta em uma soma de K matrizes de posto um se tiver K valores singulares diferentes de zero. Além disso, o espaço da coluna e o espaço da linha de X têm dimensão K. A sequência de valores singulares é exclusiva de uma matriz e o foco está na identificação das propriedades de X que fazem com que as matrizes de classificação baixa apareçam em vários problemas matemáticos.

  • 00:05:00 Nesta seção, o palestrante discute matrizes de classificação baixa e como elas têm muitos zeros em sua sequência de valores singulares. Uma matriz de classificação baixa é aquela em que é mais eficiente enviar a matriz para um amigo na forma de classificação baixa do que na forma de classificação completa. A palestra usa diferentes sinalizadores para demonstrar o conceito de matrizes de classificação baixa, com classificações extremamente baixas sendo altamente alinhadas com as coordenadas das linhas e colunas. À medida que a classificação aumenta, o alinhamento fica embaçado e fica mais difícil ver se a matriz é de baixa classificação. Matrizes de classificação alta são ineficientes para enviar na forma de classificação baixa.

  • 00:10:00 Nesta seção, o professor examina a matriz de bandeira triangular para entender por que os padrões diagonais não são bons para compactação de classificação baixa. A matriz de todos os uns tem uma propriedade semelhante à matriz favorita de Gil quando sua inversa é tomada. Ao examinar os valores singulares dessa matriz, o palestrante mostra que os padrões triangulares não são passíveis de compressão de classificação baixa. No entanto, a caixa circular e o padrão de bandeira japonesa são convenientes para compactação de classificação baixa.

  • 00:15:00 Nesta seção, o palestrante discute a classificação de um círculo, particularmente a bandeira japonesa. Ao decompor a bandeira em um círculo, uma peça de classificação um no meio e um quadrado, a classificação pode ser determinada adicionando as classificações de cada peça. O palestrante mostra que a peça de nível um é limitada por um e, em seguida, usa a simetria para determinar o nível da peça quadrada, que depende do raio do círculo. Fazendo alguns cálculos com trigonometria, o palestrante conclui que o posto é aproximadamente 1/2, tornando-se eficiente para representar a bandeira japonesa na forma de posto baixo. No entanto, a maioria das matrizes em matemática computacional não tem classificação finita, mas classificação numérica, que é semelhante à classificação, mas permite alguma aproximação.

  • 00:20:00 Nesta seção, aprendemos sobre a classificação numérica de uma matriz, que é definida permitindo algum espaço de manobra para definir a tolerância de valores singulares de uma matriz. A classificação numérica é K se K for o primeiro valor singular acima do epsilon, que denota a tolerância, e a classificação for igual ao último valor singular acima do epsilon e for o primeiro valor singular abaixo do epsilon. Matrizes numericamente de posto baixo não são apenas matrizes de posto baixo, mas também matrizes de posto completo com valores singulares decrescentes rapidamente. Isso nos permite comprimir matrizes usando aproximação de baixo escalão enquanto permite um nível de tolerância razoável na prática. A matriz de Hilbert é um exemplo de matriz de posto completo com posto numérico baixo.

  • 00:25:00 Nesta seção, o palestrante discute como as matrizes podem ser de classificação numérica baixa, mas não necessariamente de classificação baixa em geral. A matriz de Vandermonde é usada como um exemplo clássico disso. Essa matriz surge na interpolação polinomial em pontos reais e muitas vezes é numericamente baixa, dificultando a inversão. No entanto, a classificação numérica baixa nem sempre é desejável, principalmente ao tentar encontrar o inverso. O palestrante explica que a razão pela qual existem tantas matrizes de baixo escalão é que o mundo é suave, o que significa que as matrizes são numericamente de baixo escalão. Um exemplo é dado onde um polinômio em duas variáveis é amostrado, e é mostrado que a matriz resultante é matematicamente de baixo escalão com epsilon igual a zero.

  • 00:30:00 Nesta seção, o palestrante discute como obter uma aproximação de baixo escalão para uma matriz X por amostragem de uma função e aproximando essa função por um polinômio. Se um polinômio de duas variáveis puder ser escrito, com grau M em x e y, e depois amostrado, o x resultante terá classificação baixa com epsilon igual a zero, tendo no máximo classificação M ao quadrado. Ao amostrar funções suaves, que podem ser bem aproximadas por polinômios, o posto numérico pode ser baixo, resultando em uma aproximação de posto baixo da matriz X. No entanto, o raciocínio por trás desse método não funciona bem para a matriz de Hilbert, que é posto completo.

  • 00:35:00 Nesta seção, o palestrante discute como encontrar uma razão apropriada para limitar o posto de uma matriz. Muitas pessoas tentaram criar um polinômio que pudesse prever com precisão a classificação de uma matriz, mas os métodos foram insatisfatórios. O palestrante apresenta a ideia das matrizes de Sylvester, que são matrizes que satisfazem uma certa equação chamada equação de Sylvester. Ao encontrar A, B e C que satisfaçam a equação, pode-se mostrar que uma matriz tem classificação numérica baixa. O palestrante fornece um exemplo usando a matriz de Hilbert e uma maneira específica de multiplicar pela metade à esquerda e à direita para satisfazer a equação de Sylvester.

  • 00:40:00 Nesta seção, a palestra forneceu exemplos de matrizes gaussianas e de Vandermonde para explicar como permutações e multiplicações podem levar a matrizes de classificação baixa. A palestra explica que se X satisfaz uma equação semestral, então um limite pode ser encontrado nos valores singulares de qualquer matriz que satisfaça uma expressão similar àquela das matrizes Gaussiana e Vandermonde, chamada norma de Frobenius. O Fuller and bound é usado para demonstrar essa classificação numérica baixa em matrizes, com exemplos dados para demonstrar uma conexão entre a satisfação de certas equações e a aparência dessas matrizes de classificação baixa na prática.

  • 00:45:00 Nesta seção, o palestrante discute como o problema abstrato de valores singulares sendo limitados por números de Zolotarev é útil porque muitas pessoas já estudaram esses números. A principal razão pela qual isso é útil é que os conjuntos E e F são separados, e é isso que faz com que o número de Zolotarev fique pequeno extremamente rapidamente com k. O palestrante usa a matriz de Hilbert como exemplo para mostrar como o número de Zolotarev pode dar um limite no posto numérico, indicando por que existem tantas matrizes de posto baixo na matemática computacional. O palestrante também menciona a maldição não oficial em torno das duas pessoas-chave que trabalharam no problema de Zolotarev; ambos morreram aos 31 anos, por isso há um ponto de interrogação ao lado do nome de Pencil.
 

Aula 18: Parâmetros de contagem em SVD, LU, QR, pontos de sela



Aula 18: Parâmetros de contagem em SVD, LU, QR, pontos de sela

Nesta palestra, o palestrante analisa várias fatorações de matrizes, como L&U, Q&R e matrizes de autovetores, e conta o número de parâmetros livres em cada uma dessas matrizes. Eles também discutem o cálculo de Qs versus SVD e contam o número de parâmetros no SVD para uma matriz rank-R. O palestrante também explica o conceito de pontos de sela em matrizes e como encontrá-los usando técnicas de otimização e multiplicadores de Lagrange. Por fim, o palestrante discute o sinal dos autovalores de uma matriz simétrica e como o quociente de Rayleigh pode ajudar a determinar o valor máximo e o autovetor correspondente da matriz.

  • 00:00:00 Nesta seção, o palestrante analisa as grandes fatorações de uma matriz, como L&U, Q&R e matrizes de autovetores, e conta o número de parâmetros livres em cada uma dessas matrizes. O palestrante observa que o número de parâmetros livres em L&U ou Q&R deve concordar com o número de parâmetros na matriz original e que os parâmetros livres das matrizes de autovalores e autovetores somam N ao quadrado. O palestrante observa que este exercício não é visto com frequência em livros didáticos, mas é uma revisão importante para a compreensão da álgebra linear.

  • 00:05:00 Nesta seção, o palestrante discute o número de parâmetros livres em diferentes fatorações de matrizes, incluindo SVD, LU, QR e decomposição polar. O palestrante observa que o número de parâmetros livres em uma matriz ortogonal N por n Q é N-1 para a primeira coluna e N-2 para as colunas subsequentes devido às condições de normalização e ortogonalidade. Eles também discutem o número de parâmetros livres em uma matriz simétrica S, que é 1/2 N vezes N menos 1 mais o número de elementos diagonais. Eles então mostram como essas contagens se somam para diferentes fatorações, incluindo L vezes U, Q vezes R e Q vezes S. Finalmente, eles mencionam a decomposição polar como outra fatoração que resulta em uma matriz ortogonal vezes uma simétrica.

  • 00:10:00 Nesta seção, o palestrante discute o cálculo de Qs versus SVD e, em seguida, conta os parâmetros no SVD. A maior classificação que a matriz retangular pode ter é M, o que resultará em uma matriz M por N para o SVD. O professor espera que a soma seja o total da matriz original, que tem parâmetros MN. A contagem para S é igual a M e a contagem para V é igual a N. A contagem para U é igual a 1/2 (M^2 + M) se for uma matriz ortogonal M por M.

  • 00:15:00 Nesta seção, o palestrante explica como contar os parâmetros importantes na decomposição de valor singular (SVD) de uma matriz para uma matriz rank-R. As M colunas de V que correspondem a valores singulares diferentes de zero são as únicas partes importantes da matriz. Para contar o número de parâmetros, o locutor usa uma fórmula que contabiliza os diferentes números de parâmetros necessários em cada coluna ortogonal de V, até a M-ésima coluna. A fórmula envolve somar 1 a NM para cada coluna e subtrair esse número da metade de M ao quadrado mais M mais 1. O resultado da fórmula é a contagem final dos parâmetros no SVD de uma matriz rank-R.

  • 00:20:00 Nesta seção, o palestrante discute matrizes de classificação R e o número de parâmetros que elas possuem. Matrizes de posto R não são um subespaço porque matrizes diferentes podem ter o mesmo posto, tornando-a mais parecida com uma superfície, com peças diferentes. O palestrante acredita que uma matriz de posto R possui R parâmetros. Eles então encontram o número de parâmetros em uma matriz de classificação R. O número de parâmetros é R para Sigma, (R + 1) / 2 para V e (M - 1) + (M - 2) + ... + (M - R) para U.

  • 00:25:00 Nesta seção da palestra, o instrutor discute o conceito de pontos de sela em matrizes, que são diferentes de máximos e mínimos. Os pontos de sela surgem ao otimizar uma função de custo quadrática sujeita a restrições lineares usando multiplicadores de Lagrange. O instrutor apresenta o lambda e mostra como ele é usado no Lagrangeano para formar uma função que depende tanto de X quanto de lambda. Esta função pode então ser otimizada para encontrar quaisquer pontos de sela que possam surgir. O instrutor também menciona outra fonte de pontos de sela, que surgem em matrizes que não são definidas positivas ou definidas negativas.

  • 00:30:00 Nesta seção, o palestrante discute como encontrar pontos de sela de uma função e mostra como eles surgem em uma classe importante de problemas representados por uma matriz de blocos. A função tem pontos de sela, não um máximo. A contribuição de Lagron para este problema está tomando as derivadas em relação a X e lambda, produzindo n e m equações, respectivamente. Em última análise, a matriz representada pela matriz de bloco indica que não é positiva definida e esta informação pode ser usada para determinar pontos de sela.

  • 00:35:00 Nesta seção, o palestrante discute como o determinante de uma matriz pode ajudar a determinar os sinais de seus autovalores. Usando um exemplo simples, ele mostra que se o determinante for negativo, deve haver autovalores de ambos os sinais. Ele então relaciona isso com as matrizes KKT usadas na otimização e argumenta que elas são geralmente indefinidas, mas têm um bloco definido positivo associado a elas. Ele demonstra que, ao usar a eliminação de bloco neste bloco definido positivo, todos os n pivôs serão positivos, o que leva à conclusão de que as matrizes KKT têm autovalores positivos e negativos.

  • 00:40:00 Nesta seção, o palestrante discute os pontos de sela e como eles se relacionam com as restrições. Ele explica como determinar o sinal dos autovalores de uma matriz simétrica, com base nos sinais de seus pivôs. O palestrante também define o quociente de Rayleigh e analisa como ele pode nos ajudar a determinar o valor máximo e o autovetor correspondente de uma matriz simétrica. A palestra termina com uma explicação de como qualquer valor que inserirmos no quociente de Rayleigh será menor que o valor máximo.

  • 00:45:00 Nesta seção, o palestrante discute o conceito de pontos de sela no quociente de Rayleigh. Há dificuldade em lidar com lambdas intermediários entre o mínimo e o máximo. No entanto, no máximo e no mínimo, os valores do quociente são fáceis de medir. Se qualquer vetor for selecionado em qualquer dimensão, podemos calcular R de X, que está entre o máximo e o mínimo. O palestrante diz que falar sobre os detalhes dos pontos de sela ficará para a próxima palestra, mas antes disso será ministrado o terceiro laboratório, que ensina sobre overfitting, deep learning, e fica para depois do intervalo.
 

Aula 19. Continuação dos Pontos de Sela, Princípio Maxmin



19. Continuação dos Pontos de Sela, Princípio Maxmin

Neste vídeo, o palestrante continua discutindo pontos de sela e como encontrar valores mínimos e máximos usando o quociente de Rayleigh no espaço bidimensional. O teorema do entrelaçamento é explicado, o que envolve escrever pontos de sela como o máximo de um mínimo para encontrar rapidamente máximos e mínimos. O palestrante também adverte contra o overfitting ao ajustar dados com um polinômio de alto grau e discute dois laboratórios abertos para a classe, envolvendo pontos de sela e uma rede neural simples. Os conceitos de média e variância em estatísticas e variância e covariância da amostra são explicados, com o palestrante observando que a matriz de covariância para saídas totalmente dependentes não seria invertível, e para cenários de pesquisa com várias pessoas morando em uma casa, alguma covariância é esperada, mas não totalmente independente.

  • 00:00:00 Nesta seção, o palestrante discute a importância de entender os pontos de sela em relação a encontrar o mínimo da função de custo total no aprendizado profundo. Eles fornecem um exemplo de quociente de Rayleigh e uma matriz S simples para ilustrar os principais fatos dos pontos de sela, os valores máximo e mínimo da função e a presença de um ponto de sela. O palestrante também menciona seus planos para discutir o laboratório três, projetos e estatísticas básicas, particularmente a matriz de covariância.

  • 00:05:00 Nesta seção, o palestrante discute os pontos de sela e como encontrar os valores mínimo e máximo carregando tudo em uma variável e calculando as derivadas para descobrir onde elas são iguais a zero. Eles demonstram como encontrar o valor mínimo e mostram que os autovetores e autovalores da matriz ajudam a encontrar a localização e o valor do ponto de sela. O palestrante também fala sobre como calcular as segundas derivadas e a matriz simétrica. Eles enfatizam a importância de calcular os valores do ponto de sela e sugerem trabalhar com códigos e estar atentos ao processo.

  • 00:10:00 Nesta seção, o palestrante discute a ideia de pontos de sela e como escrevê-los como máximo ou mínimo para voltar rapidamente aos máximos e mínimos. Ele explica que isso leva ao teorema do entrelaçamento e dá um exemplo de obtenção do mínimo em um subespaço bidimensional para encontrar o mínimo do quociente de Rayleigh. Tomando o máximo desse mínimo sobre todos os subespaços, ele consegue obter lambda, o valor do ponto de sela.

  • 00:15:00 Nesta seção, o palestrante explica como encontrar os valores máximo e mínimo em um espaço bidimensional usando o quociente de Rayleigh. Ele demonstra que o valor máximo é três tomando o máximo em todos os espaços 2D possíveis e mostrando que esta escolha particular de V deu a resposta de três. O locutor então explica como o valor mínimo ficará abaixo de três para qualquer outro subespaço, significando que o valor máximo para os mínimos também é três. O conceito de pontos de sela também é discutido, com o palestrante observando que esses pontos geralmente ocorrem nos pontos mais altos de certas regiões e podem ser Máximos de Mínimos ou Mínimos de Máximos. O vídeo termina com uma discussão sobre os projetos e um convite para que os espectadores façam perguntas sobre eles.

  • 00:20:00 Nesta seção, o palestrante explica um modelo de overfitting no qual um polinômio de grau 5 é usado para ajustar 6 pontos. O palestrante aponta que o polinômio de 5º grau seria um ajuste exato aos pontos de dados, mas também seria um modelo falho porque não seria suave ou agradável. Este exemplo serve como um aviso contra o overfitting, que ocorre quando um modelo é muito complexo e muito ajustado aos dados de treinamento.

  • 00:25:00 Nesta seção, o palestrante discute o problema de ajuste de dados com um polinômio de alto grau. Embora o ajuste de uma linha reta possa resultar em underfitting, o ajuste de um polinômio de alto grau pode levar ao overfitting, pois cria um ajuste perfeito para todos os pontos de dados fornecidos, sem considerar o ruído nos dados. A ideia de ajuste perfeito está relacionada à matriz de Vandermonde, que possui um grande inverso devido ao vetor de coeficientes gigante resultante do ajuste perfeito. A matriz tem uma ampla gama de valores singulares, com valores minúsculos ocorrendo ao lado de valores de tamanho normal. Como tal, pode ser um desafio encontrar o grau correto de polinômio para ajustar aos dados para encontrar um equilíbrio entre underfitting e overfitting.

  • 00:30:00 Nesta seção, o palestrante descreve dois exemplos de laboratórios abertos para sua aula, um envolvendo pontos de sela e outro envolvendo uma rede neural simples. Para o exemplo do ponto de sela, o palestrante sugere enviar gráficos e tabelas de dados para avaliar o escopo e tirar conclusões sobre a segurança e o risco de aumentar K. Em relação ao exemplo da rede neural, o palestrante descreve um problema básico de classificação e incentiva os alunos a modificar o modelar como acharem melhor, enquanto ainda usam álgebra linear. O palestrante também menciona uma próxima reunião do corpo docente sobre os planos do MIT para cursos de pensamento computacional, dos quais este curso é um exemplo. Por fim, o palestrante convida os alunos a enviarem um e-mail com ideias preliminares de projetos e preferências do grupo.

  • 00:35:00 Nesta seção, o professor discute a ideia de um projeto para a aula e esclarece seu escopo. Ele menciona que o projeto não seria muito grande, talvez equivalente a três tarefas de casa, mas também não seria trivial. Ele pede aos alunos que façam perguntas e sugestões sobre o projeto, sugerindo a possibilidade de incluir tópicos como redes neurais convolucionais. O professor também menciona que alguns alunos iniciaram uma reunião no Media Lab, e ela ocorreu com sucesso. Ele pergunta se as pessoas estariam interessadas em tais reuniões novamente após as férias de primavera.

  • 00:40:00 Nesta seção, o palestrante apresenta os conceitos de média e variância nas estatísticas, como eles se relacionam com o resultado real e o resultado esperado e a diferença entre a média da amostra e a média esperada. A média amostral é calculada a partir da saída real de um experimento, enquanto a média esperada é calculada a partir das probabilidades desses resultados. A variância também é discutida, distinguindo-se a variância amostral e a variância esperada. O palestrante explica que os valores esperados de média e variância se aproximarão dos valores reais conforme o número de amostras ou possibilidades aumenta.

  • 00:45:00 Nesta seção, o conceito de variância da amostra é discutido, que mede a distância média ao quadrado da média de um conjunto de n amostras. Em estatística, a divisão de n menos um significa que essa distância é calculada a partir da média da amostra, não zero, e quando n é grande, a diferença entre n e n menos um não é significativa. A covariância, por outro lado, é uma ideia mais profunda que envolve a manipulação da matriz quando vários experimentos são realizados e a probabilidade conjunta de dois eventos separados é calculada.

  • 00:50:00 Nesta seção, o palestrante discute os dois extremos da saída de covariância: saídas independentes e saídas totalmente dependentes. Enquanto as saídas independentes têm uma covariância de 0, as saídas totalmente dependentes têm uma covariância máxima, onde uma saída é inteiramente determinada pela outra. O palestrante usa o exemplo de lançar moedas coladas para explicar esse conceito. A matriz de covariância para saídas dependentes não seria invertível e simétrica positiva definida, ou semidefinida para o caso colado. O palestrante menciona que em cenários de votação em que várias pessoas moram em uma casa, haveria alguma covariância esperada, mas não seria totalmente independente.
 

Aula 20. Definições e Desigualdades



20. Definições e Desigualdades

Nesta seção do vídeo, o palestrante discute vários conceitos da teoria da probabilidade, incluindo valor esperado, variância e matrizes de covariância. A desigualdade de Markov e a desigualdade de Chebyshev também foram introduzidas como ferramentas fundamentais para estimar probabilidades. O palestrante passa então a explicar a relação entre a desigualdade de Markov e a desigualdade de Chebychev, ilustrando como elas levam ao mesmo resultado. O conceito de covariância e matriz de covariância, uma ferramenta fundamental na teoria da probabilidade, também foi introduzido. O vídeo também explora a ideia de probabilidades e tensores conjuntos, explicando como colar moedas adiciona dependência e altera as probabilidades. Por fim, o palestrante discute as propriedades da matriz de covariância, enfatizando que ela é sempre semidefinida positiva e é uma combinação de matrizes semidefinidas positivas de posto 1.

  • 00:00:00 Nesta seção, o palestrante discute o valor esperado, a variância e a matriz de covariância. O valor esperado, simbolizado como 'e', é definido como a média ponderada de todos os resultados possíveis com base em suas probabilidades. A variância, por outro lado, é o valor esperado do quadrado da distância entre a média e cada ponto de dados. A matriz de covariância também pode ser expressa de maneira semelhante. O professor então explora uma segunda expressão para variância escrevendo os quadrados e combinando-os de forma diferente, resultando em uma maneira mais eficiente de calcular a variância.

  • 00:05:00 Nesta seção, o palestrante discute um processo algébrico de simplificação de uma equação para encontrar o valor esperado de x ao quadrado. Ele mostra que o valor esperado de x ao quadrado menos o valor esperado de x menos M ao quadrado é equivalente à soma das probabilidades de x ao quadrado. O palestrante então apresenta a desigualdade de Markov, que é uma desigualdade estatística que envolve probabilidades e expectativas. Ele observa que Markov foi um grande matemático russo e que eles verão cadeias e processos de Markov mais adiante no livro.

  • 00:10:00 Nesta seção, o palestrante explica a desigualdade de Markov, que pode ajudar a estimar a probabilidade de X ser maior ou igual a um determinado número. A desigualdade afirma que a probabilidade de X ser maior ou igual a a é menor ou igual à média de X dividida por a. O locutor dá um exemplo usando uma média de um e um valor de a de três, mostrando que a probabilidade de X ser maior ou igual a três é menor ou igual a 1/3. No entanto, o palestrante observa que essa desigualdade se aplica apenas a eventos não negativos e não pode ser usada com eventos que tenham saídas que variam de negativo a infinito positivo.

  • 00:15:00 Nesta seção do vídeo, o palestrante fala sobre o uso de um caso especial para demonstrar a probabilidade de ser maior ou igual a 3. Eles usam a definição de média para escrever uma equação específica e, em seguida, fazer suposições sobre os valores de X1 a X5 para satisfazer a desigualdade de Markov. Eles declaram o fato de que as probabilidades somam 1 e são todas maiores ou iguais a 0. O falante então passa a manipular a equação para mostrar que a probabilidade de ser maior ou igual a 3 é menor ou igual a 1/ 3 subtraindo certos valores da equação. Eles concluem mostrando que a equação satisfaz a desigualdade de Markov.

  • 00:20:00 Nesta seção, o palestrante discute as desigualdades de probabilidade de Markov e Chebyshev. A desigualdade de Markov envolve estimar a probabilidade de uma variável ser maior ou igual a um determinado valor e só se aplica quando as variáveis são todas maiores ou iguais a zero. A desigualdade de Chebyshev, por outro lado, lida com a probabilidade de uma variável estar a uma certa distância da média e não faz nenhuma suposição sobre as entradas. Essas duas desigualdades são ferramentas fundamentais para estimar probabilidades na teoria da probabilidade.

  • 00:25:00 Nesta seção, o palestrante explica a relação entre a desigualdade de Markov e a desigualdade de Chebychev. Ele introduz uma nova variável Y, que é X menos M ao quadrado, e explica como calcular sua média. O orador então aplica a desigualdade de Markov a Y e a desigualdade de Chebychev a X, demonstrando como elas levam ao mesmo resultado. Finalmente, ele introduz o conceito de covariância e matrizes de covariância.

  • 00:30:00 Nesta seção, o palestrante apresenta o conceito de covariância e matriz de covariância, que é uma matriz M por M onde M é o número de experimentos sendo feitos de uma só vez. Para ilustrar esse conceito, o palestrante usa o exemplo de lançar duas moedas com uma saída (X) por moeda. Se as duas moedas forem lançadas independentemente, não haverá correlação entre as saídas, mas se elas forem coladas, as saídas serão correlacionadas e as probabilidades conjuntas serão colocadas em uma matriz 2x2.

  • 00:35:00 Nesta seção, o palestrante discute o conceito de probabilidades conjuntas e matrizes para configurações experimentais envolvendo moedas independentes. Eles exploram a ideia de uma estrutura de três vias, ou tensor, nos casos em que há três experimentos com moedas justas independentes ou quando as moedas são coladas. As entradas resultantes no tensor seriam as probabilidades conjuntas, que podem ser usadas para calcular a probabilidade de diferentes resultados. O palestrante observa que, embora as entradas em um caso simples de um experimento não colado sejam um oitavo, colar as moedas adiciona dependência e altera as probabilidades.

  • 00:40:00 Nesta seção do vídeo, o palestrante discute a probabilidade conjunta de lançar três moedas e como ela pode ser representada em uma matriz de 3 vias. Ele menciona o conceito de tensores e matrizes de covariância, definindo o último como a variância do resultado conjunto de dois experimentos, X e Y, expresso como uma soma de todos os resultados possíveis. O palestrante também explica o símbolo P IJ e como ele se relaciona com a colagem e descolagem de moedas em diferentes configurações.

  • 00:45:00 Nesta seção do vídeo, o palestrante discute a probabilidade conjunta de dois eventos - X e Y - e como calcular essa probabilidade para diferentes pares de valores. O palestrante fornece exemplos de como usar a probabilidade conjunta, incluindo o cálculo da probabilidade de uma certa idade e altura. O palestrante também define as probabilidades marginais, que são as probabilidades individuais de cada evento, e explica como somar as probabilidades ao longo de linhas ou colunas em uma matriz. O palestrante passa a definir a matriz de covariância e explica como calcular suas entradas.

  • 00:50:00 Nesta seção, o palestrante fala sobre a matriz de covariância e suas propriedades. Ele explica que a variância do experimento X é derivada da soma de todos os P IJs, enquanto a variância do experimento Y é dada pelo valor quadrado de Sigma Y. A covariância entre X e Y é a soma dos P IJ vezes a distância de X de sua média e a distância de Y de sua média. No caso de moedas independentes, a covariância seria zero, enquanto no caso de moedas coladas, seria igual a Sigma X ao quadrado Sigma Y ao quadrado. O determinante da matriz é zero no caso das moedas coladas, o que mostra que a covariância ao quadrado é igual a Sigma X ao quadrado Sigma Y ao quadrado. A matriz de covariância é sempre semidefinida positiva e é uma combinação de semidefinida positiva de classificação 1, portanto, semidefinida positiva ou definida positiva.
 

Aula 21: Minimizando uma função passo a passo



Aula 21: Minimizando uma função passo a passo

Esta palestra em vídeo discute os algoritmos básicos usados para minimizar uma função e suas taxas de convergência, particularmente o método de Newton e a descida mais íngreme. Ele também destaca a importância da convexidade, que garante que a função tenha um mínimo, e introduz o conceito de conjuntos convexos e funções convexas. O palestrante explica como testar a convexidade em uma função, que determina se ela possui pontos de sela ou mínimos locais, em oposição a um mínimo global. O vídeo termina com uma discussão sobre Levenberg Marquardt, uma versão mais barata do método de Newton que não é totalmente de segunda ordem.

  • 00:00:00 Nesta seção, o palestrante discute os fundamentos da otimização, que é o algoritmo fundamental que entra no aprendizado profundo. A palestra começa explicando a série de Taylor e passa a mostrar como estender a série de Taylor quando a função é de mais de uma variável. O professor então introduz o gradiente de F, que são as derivadas parciais de F em relação a cada variável X. Finalmente, o termo quadrático é explicado e a palestra termina discutindo as segundas derivadas e como elas mudam com mais variáveis.

  • 00:05:00 Nesta seção da palestra, é introduzido o conceito de matriz Hessiana, que é a matriz das segundas derivadas de uma função. A matriz Hessiana é simétrica e seu cálculo é viável para valores pequenos a moderadamente grandes de n. Existe uma imagem paralela para a função vetorial, que é a matriz jacobiana, com as entradas sendo as derivadas da função em relação a diferentes variáveis. Esses são fatos do cálculo multivariável, que são usados para resolver equações em problemas de otimização.

  • 00:10:00 Nesta seção, o palestrante discute o método de Newton para resolver sistemas de equações em n incógnitas, que envolve a minimização de uma determinada função. O método de Newton é a melhor maneira de resolver n equações em n incógnitas, que podem ser expressas como F igual a 0, onde F de um é igual a zero e há n equações no total. O palestrante mostra como usar o método de Newton para resolver a equação x ao quadrado menos 9 igual a 0, que pode ser escrita como uma função, e demonstra como aplicar o método passo a passo.

  • 00:15:00 Nesta seção, o palestrante discute como o método de Newton é usado para minimizar uma função e como determinar a rapidez com que ela converge. Eles começam simplificando a fórmula que determina X sub K + 1 e mostram que se X sub K é exatamente 3, então X sub K + 1 também será 3. Eles então se concentram em quão rápido o erro se aproxima de zero e subtraem 3 de ambos lados para fatorar 1 sobre X sub K. A simplificação da equação mostra que o erro na etapa K + 1 é elevado ao quadrado a cada etapa, o que prova por que o método de Newton é fantástico se executado próximo o suficiente.

  • 00:20:00 Nesta seção, o palestrante discute o uso do método de Newton para otimização e como ele é aplicável a funções de perda muito complicadas com milhares ou até centenas de milhares de variáveis. A palestra abrange dois métodos - descida mais íngreme e método de Newton - em que a descida mais íngreme envolve mover-se na direção do gradiente de F, mas com liberdade para decidir sobre o tamanho do passo. Por outro lado, o método de Newton leva em consideração a segunda derivada de F e permite uma convergência mais rápida, mas também pode convergir para soluções indesejáveis ou explodir para determinados pontos de partida. Isso leva ao conceito de regiões de atração, onde certos pontos de partida levam à solução desejada, enquanto outros levam a indesejáveis ou ao infinito.

  • 00:25:00 Nesta seção, o palestrante discute dois métodos para minimizar uma função passo a passo: a descida mais íngreme e o método de Newton. Ambos envolvem escolher iterativamente uma direção no espaço n-dimensional e mover uma certa distância ao longo dessa direção, mas a descida mais íngreme usa o gradiente da função para escolher a direção, enquanto o método de Newton usa o Hessian, ou segunda derivada. A palestra também explica o conceito de busca de linha exata e a importância de escolher uma taxa de aprendizado apropriada nesses métodos.

  • 00:30:00 Nesta seção, o palestrante discute os algoritmos básicos usados para minimizar uma função e suas taxas de convergência. O palestrante explica que o método de Newton tem uma taxa de convergência quadrática, tornando-o super rápido se iniciado próximo o suficiente. Em contraste, o algoritmo de descida mais íngreme tem uma taxa de convergência linear, tornando-o menos eficiente. O palestrante enfatiza que o ponto de partida para a resolução desses problemas deve ser a convexidade, o que garante que a função tenha um mínimo. O palestrante define conjuntos e funções convexas e explica sua importância na minimização de uma função para pontos em um conjunto convexo. A palestra termina com uma discussão sobre Levenberg Marquardt, uma versão mais barata do método de Newton que não é totalmente de segunda ordem.

  • 00:35:00 Nesta seção do vídeo, o palestrante discute como minimizar uma função. As restrições para a função são definidas por um conjunto convexo, o que significa que qualquer linha traçada entre dois pontos dentro do conjunto deve permanecer dentro do conjunto. O palestrante dá o exemplo de dois triângulos sobrepostos, que não formam um conjunto convexo quando combinados.

  • 00:40:00 Nesta seção, o conceito de conjuntos convexos e funções convexas é introduzido. Note-se que a interseção de dois conjuntos convexos é sempre convexa, e o conjunto vazio é considerado um conjunto convexo. As notas do vídeo destacam a importância de entender esses conceitos ao minimizar funções, pois o problema do protótipo envolve encontrar funções com uma imagem convexa. O vídeo também conecta a definição de uma função convexa à definição de um conjunto convexo, observando que o gráfico de uma função convexa se assemelha a uma tigela, enquanto os pontos nessa superfície não são conjuntos convexos. No entanto, o conjunto de pontos no gráfico é um conjunto convexo.

  • 00:45:00 Nesta seção da palestra, o palestrante discute um teste para a função convexa. Ele explica que duas funções convexas podem ser usadas para criar uma função mínima e máxima, e uma delas será convexa enquanto a outra não. A função mínima terá uma torção e, portanto, não será convexa, enquanto a função máxima será convexa. O orador refere ainda que este teste pode ser alargado a um máximo de 1500 funções, sendo que se todas as 1500 funções forem convexas, o seu máximo também será convexo.

  • 00:50:00 Nesta seção, o palestrante explica como testar a convexidade em uma função. Para uma função com apenas uma variável em cálculo, uma função convexa pode ser provada verificando se a segunda derivada é positiva ou zero. Ao lidar com uma função vetorial com múltiplas variáveis, uma matriz simétrica F seria adicionada à função. O teste de convexidade aqui seria semidefinido positivo para o Hessiano, pois as segundas derivadas resultam em uma matriz. Problemas convexos não possuem pontos de sela ou mínimos locais, apenas o mínimo global, tornando-os desejáveis.