regressão linear de ordem superior

https://stackoverflow.com/questions/821014

03-07-2019
|

Pergunta

Eu tenho o sistema de matriz:

A x B = C

A é a por n e B é n por b. Ambos A e B são desconhecidas, mas tenho informações parciais sobre C (Eu tenho alguns valores, mas não todos) e n é escolhido para ser pequeno o suficiente para que o sistema está prevista para ser mais restrita. Não é necessário que todas linhas em A ou colunas em B são mais restritos.

Eu estou procurando algo como mínimos quadrados linear de regressão para encontrar um melhor ajuste para este sistema (Nota: eu soubesse que não haverá uma única solução única, mas tudo que eu quero é uma das melhores soluções)

Para fazer um exemplo concreto; todo o um e b do são desconhecidas, todos os do c são conhecidos, e os? 's são ignorados. Eu quero encontrar a menos solução quadrados única tendo em conta o know de c.

[ a11, a12 ]                                     [ c11, c12, c13, c14, ?   ]
[ a21, a22 ]   [ b11, b12, b13, b14, b15]        [ c21, c22, c23, c24, c25 ]
[ a31, a32 ] x [ b21, b22, b23, b24, b25] = C ~= [ c31, c32, c33, ?,   c35 ]
[ a41, a42 ]                                     [ ?,   ?,   c43, c44, c45 ]
[ a51, a52 ]                                     [ c51, c52, c53, c54, c55 ]

Note que, se B é cortado para b11 e só b21 ea linha desconhecido 4 chomped fora, então este é quase uma mínimos quadrados padrão linear problema de regressão.

Solução

Eu não tenho idéia sobre como lidar com os seus valores em falta, então eu vou ignorar esse problema.

Não há soluções únicas. Para encontrar uma melhor solução que você precisa de algum tipo de uma métrica para julgar por eles. Vou supor que você queira usar uma mínimos quadrados métrica, ou seja, os melhores valores suposição de A e B são aqueles que minimizam soma dos números [C_ij- (A B) _ij] ^ 2.

Uma coisa que você não mencionou é como determinar o valor que você vai usar para n. Em suma, podemos chegar a 'boas' soluções se 1 <= n <= b. Isso é porque uma <= classificação (faixa (C)) <= b. Quando posto (faixa (C)) = a dimensão do espaço da coluna de C. Note-se que este está a assumir um> = b. Para ser mais correto que iria escrever 1 <= classificação (span (C)) <= min (a, b).

Agora, supondo que você tenha escolhido n tal que 1 <= n <= b. Você está indo para minimizar a soma dos quadrados dos resíduos se você escolheu as colunas de A tal que extensão (A) = vão (Primeira n eigenvetores de C). Se você não tem quaisquer outras razões boas, basta escolher as colunas de A para ser a primeira n eigenvetores de C. Depois de ter escolhido A, você pode obter os valores de B na forma de regressão linear habitual. Ou seja, B = (A'A) ^ (- 1) A' C

Outras dicas

Este problema é illposed como descrito.

Sejam A, B, e C = 5, ser escalares. Você está pedindo para resolver a * b = 5 que tem um número infinito de soluções.

Uma abordagem, nas informações fornecidas acima, é minimizar a função g definida como

g (A, B) = || AB-C || ^ 2 = traço ((AB-C) * (AB-C)) ^ 2

usando o método Newtons ou uma abordagem quasi-secante (BFGS).
(Você pode facilmente calcular o gradiente aqui). M * representa o transposto de H e multiplicação é implícito. (A norma é a norma Frobenius ... eu removi o sublinhado F vez que não foi exibido corretamente)

Como este é um problema inerentemente não-linear, linear padrão álgebra se aproxima não se aplicam.

Se você fornecer mais informações, eu posso ser capaz de ajudar mais.

Alguns mais perguntas: Eu acho que a questão é aqui é que, sem obter mais informações, não há "melhor solução". Nós precisamos determinar uma ideia mais concreta do que estamos procurando. Uma idéia, poderia ser uma solução "sparsest". Esta área é uma área importante de pesquisa, com algumas das melhores mentes do mundo do trabalho aqui (Veja Terry Tao et al. trabalhar em Norm Nuclear) Este problema, embora tratável ainda é difícil.

Infelizmente, eu ainda não sou capaz de comentar, por isso vou adicionar meus comentários aqui. Como disse abaixo, LM é uma ótima abordagem para resolver isso e é apenas uma aproximação. ao longo das linhas do tipo Newton abordagens para ambos o problema de otimização ou a resolução de problemas não-linear.

Aqui está uma idéia, usando o exemplo que você deu acima: Permite definir dois novos vectores, V e L, cada um com 21 elementos (exactamente o mesmo número de definida elementos em C).

V é precisamente os elementos conhecidos de C, coluna ordenada, de modo que (na notação Matlab)

V = [C11; C21; C31; C51; C12; ....; C55]

U é um vetor que é uma ordenação de coluna do produto AB, deixando de fora a Elementos correspondentes '?' na matriz C . Recolhendo todas as variáveis ??em x temos
x = [a11, a21, a52 .., b11, b21 ..., b25].

f (x) = L (como definido acima).

Agora podemos tentar resolver f (x) = V com a sua não-linear método favorito de mínimos quadrados.

Como um aparte, embora um cartaz abaixo do recomendado recozimento simulado, eu recomendo contra isso. Existem alguns problemas que funciona, mas é uma heurística. Quando voce tem poderosos métodos analíticos tais como Gauss-Newton ou LM, eu digo usá-los. (no meu próprio experiência que é)

Um palpite:? A valor singular decomposição pode fazer o truque

Você tem um par de opções. A Levenberg-Marquadt algoritmo é geralmente reconhecido como o melhor método LS. A aplicação está disponível gratuitamente em aqui . No entanto, se o cálculo é rápido e você tem um número razoável de parâmetros, Gostaria de sugerir um método de Monte Carlo, como simulado recozimento.

Você começa com um conjunto de parâmetros na resposta, e então você aumentar uma delas por uma percentagem aleatória até um máximo. Você, então, calcular a função de aptidão para o seu sistema. Agora, aqui está o truque. Você não jogue fora as respostas ruins. Você aceitá-los com uma distribuição de probabilidade Boltzmann.

P = exp(-(x-x0)/T)

onde T é um parâmetro de temperatura e x-x0 é o valor atual da aptidão menos o anterior. Após x número de iterações, é diminuir a T por um valor fixo (isto é chamado a programação de arrefecimento). Você, então, repetir este processo para um outro parâmetro aleatório. Como T diminui, menos soluções pobres são escolhidos, e, eventualmente, o processo torna-se uma "busca gananciosa" aceitando apenas as soluções que melhoram o ajuste. Se o seu sistema tem muitos parâmetros livres (> 10 ou mais), esta é realmente a única maneira de ir para onde você vai ter alguma chance de chegar a um mínimo global. Este método montagem leva cerca de 20 minutos para escrever em código, e um par de horas para ajustar. Espero que isso ajude.

FYI, Wolfram tem uma boa discussão sobre isso no contexto do problema caixeiro-viajante, e eu tenho usado com muito sucesso para resolver alguns problemas de minimização globais muito difíceis. É mais lento do que os métodos LM, mas muito melhor na maioria dos difíceis relativamente grandes casos /.

Com base na constatação de que o corte B para uma única coluna e deles retirar linha com incógnitas convertidos isso muito perto de um problema conhecido, Uma abordagem seria:

semente A com valores aleatórios.
resolver para cada coluna de B de forma independente.
retrabalhar o problema de permitir resolver para cada linha de um dado os valores de B a partir do passo 2.
repita a etapa 2 até que as coisas se fora.

Eu não tenho idéia se isso é mesmo estável.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow