regressione lineare di ordine superiore

StackOverflow https://stackoverflow.com/questions/821014

  •  03-07-2019
  •  | 
  •  

Domanda

Ho il sistema a matrice:

A x B = C

A è a di n e B è b di C. Sia <=> che <=> sono sconosciuti, ma ho informazioni parziali su <=> (ho alcuni valori in esso ma non tutti) e <=> è scelto per essere abbastanza piccolo da prevedere un vincolo eccessivo del sistema. Non è necessario che tutte le righe in <=> o le colonne in <=> siano troppo vincolate.

Sto cercando qualcosa come minimi quadrati regressione lineare per trovare la soluzione migliore per questo sistema (Nota: sapevo che non ci sarebbe un'unica soluzione unica ma tutto ciò che voglio è una delle migliori soluzioni)

Per fare un esempio concreto; tutte le a e le b sono sconosciute, tutte le c sono note e le? sono ignorate. Voglio trovare una soluzione dei minimi quadrati tenendo conto solo delle conoscenze. 

[ 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 ]

Si noti che se B viene tagliato solo in b11 e b21 e la riga sconosciuta 4 viene eliminata, questo è quasi un problema di regressione lineare dei minimi quadrati standard.

È stato utile?

Soluzione

Non ho idea di come gestire i valori mancanti, quindi ignorerò questo problema.

Non ci sono soluzioni uniche. Per trovare la soluzione migliore è necessario una sorta di metrica per giudicarli. Suppongo che tu voglia usare una metrica dei minimi quadrati, cioè i migliori valori di ipotesi di A e B sono quelli che minimizzano la somma dei numeri [C_ij- (A B) _ij] ^ 2.

Una cosa che non hai menzionato è come determinare il valore che intendi utilizzare per n. In breve, possiamo trovare soluzioni "buone" se 1 & Lt; = n & Lt; = b. Questo perché 1 & Lt; = rank (span (C)) & Lt; = b. Dove rank (span (C)) = la dimensione dello spazio della colonna di C. Nota che questo assume un & Gt; = b. Per essere più corretti, scriveremmo 1 & Lt; = rank (span (C)) & Lt; = min (a, b).

Ora, supponendo di aver scelto n tale che 1 < = n < = b. Ridurrai al minimo la somma residua dei quadrati se scegli le colonne di A in modo tale che span (A) = span (First n eigen vectors of C). Se non hai altri buoni motivi, basta scegliere le colonne di A in modo che siano i primi n vettori di C. Una volta scelto A, puoi ottenere i valori di B nel solito modo di regressione lineare. Cioè B = (A'A) ^ (- 1) A 'C

Altri suggerimenti

Questo problema è errato come descritto.

Sia A, B e C = 5, siano scalari. Stai chiedendo di risolvere a * b = 5 che ha un numero infinito di soluzioni.

Un approccio, sulle informazioni fornite sopra, è minimizzare la funzione g definita come

g (A, B) = || AB-C || ^ 2 = trace ((AB-C) * (AB-C)) ^ 2

utilizzando il metodo Newton o un approccio quasi secante (BFGS).
(Puoi facilmente calcolare il gradiente qui). M * è la trasposizione di M e la moltiplicazione è implicita. (La norma è la norma frobenius ... Ho rimosso il sottolinea F perché non veniva visualizzato correttamente)

Poiché si tratta di un problema intrinsecamente non lineare, standard lineare non si applicano gli approcci algebrici.

Se fornisci ulteriori informazioni, potrei essere in grado di aiutarti di più.

Qualche altra domanda: penso che il problema qui sia quello senza ulteriori informazioni, non esiste " migliore soluzione " ;. Abbiamo bisogno di determinare un'idea più concreta di ciò che stiamo cercando. Un'idea, potrebbe essere un & Quot; sparsest & Quot; soluzione. Questa zona è una zona di ricerca calda, con alcune delle migliori menti nel mondo che lavora qui (vedi Terry Tao et al. lavoro sulla norma nucleare) Questo problema, sebbene trattabile, è ancora difficile.

Sfortunatamente, non sono ancora in grado di commentare, quindi aggiungerò i miei commenti qui. Come detto di seguito, LM è un ottimo approccio per risolvere questo problema ed è solo un approccio. sulla falsariga del tipo di Newton si avvicina a entrambi il problema di ottimizzazione o il problema di risoluzione non lineare.

Ecco un'idea, usando l'esempio che hai dato sopra: Consente di definire due nuovi vettori, V e U ciascuno con 21 elementi (esattamente lo stesso numero di definiti elementi in C).

V è precisamente gli elementi noti di C, colonna ordinata, quindi (in notazione matlab)

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

U è un vettore che è un ordine di colonna del prodotto AB, LASCIANDO IL ELEMENTI CORRISPONDENTI A "?" nella matrice C . Raccogliere tutte le variabili in x abbiamo
x = [a11, a21, .. a52, b11, b21 ..., b25].

f (x) = U (come definito sopra).

Ora possiamo provare a risolvere f (x) = V con il tuo metodo dei minimi quadrati non lineari preferito.

A parte questo, sebbene un poster in basso suggerisca una ricottura simulata, mi raccomando contro di esso. Ci sono alcuni problemi che funziona, ma è euristico. Quando hai potenti metodi analitici come Gauss-Newton o LM, dico usarli. (nel mio esperienza che è)

Un'ipotesi selvaggia: una decomposizione del valore singolare potrebbe fare il trucco?

Hai un paio di opzioni. L ' algoritmo Levenberg-Marquadt è generalmente riconosciuto come il miglior metodo LS. Un'implementazione gratuita è disponibile all'indirizzo qui . Tuttavia, se il calcolo è veloce e hai un numero decente di parametri, suggerirei fortemente un metodo Monte Carlo come ricottura simulata .

Inizi con una serie di parametri nella risposta, quindi ne aumenti uno di una percentuale casuale fino a un massimo. Quindi si calcola la funzione di fitness per il proprio sistema. Ora, ecco il trucco. Non buttare via le risposte sbagliate. Li accetti con una distribuzione di probabilità Boltzmann. 

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

dove T è un parametro di temperatura e x-x0 è il valore di fitness corrente meno il precedente. Dopo x numero di iterazioni, si diminuisce T di una quantità fissa (questo si chiama il programma di raffreddamento). Quindi ripetere questo processo per un altro parametro casuale. Quando T diminuisce, vengono scelte meno soluzioni scarse e alla fine la procedura diventa un & Quot; avida ricerca & Quot; accettando solo le soluzioni che migliorano la vestibilità. Se il tuo sistema ha molti parametri gratuiti (& Gt; 10 o giù di lì), questo è davvero l'unico modo per andare dove avrai qualche possibilità di arrivare al minimo globale. Questo metodo di adattamento richiede circa 20 minuti per scrivere nel codice e un paio d'ore per modificarlo. Spero che questo aiuti.

Cordiali saluti, Wolfram ha discusso di questo nel contesto del problema del commesso viaggiatore, e lo sto usando con molto successo per risolvere alcuni problemi di minimizzazione globale molto difficili. È più lento dei metodi LM, ma molto meglio nei casi più difficili / relativamente grandi.

In base alla consapevolezza che tagliare B in una singola colonna e rimuoverle con righe sconosciute lo converte in un problema molto vicino, un approccio sarebbe:

  1. seme A con valori casuali.
  2. risolvi per ogni colonna di B. indipendentemente.
  3. rielabora il problema per consentire la risoluzione di ogni riga di A dati i valori B dal passaggio 2.
  4. ripeti al passaggio 2 fino a quando le cose non si risolvono.

Non ho idea se sia persino stabile.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top