Consenso del campione casuale: Stima robusta nella visione artificiale

Di Fouad Sabry

Che cos'è il consenso al campione casuale

Il consenso al campione casuale, noto anche come RANSAC, è un metodo iterativo utilizzato per stimare i parametri di un modello matematico basato su una raccolta dei dati osservati che includono valori anomali. Questo metodo viene utilizzato in situazioni in cui è consentito che i valori anomali non abbiano alcun impatto sui valori delle stime. La conclusione è che è anche possibile vederlo come uno strumento per individuare valori anomali. Un algoritmo è considerato non deterministico se è in grado di generare un risultato adeguato solo con una certa probabilità, e questa probabilità aumenta all'aumentare del numero di iterazioni consentite dal metodo. Nel 1981, Fischler e Bolles, che lavoravano presso SRI International, furono i primi a pubblicare l’algoritmo. Per risolvere il problema della determinazione della posizione (LDP), che è un problema in cui l'obiettivo è trovare i punti nello spazio che si proiettano su un'immagine e quindi convertire tali punti in una serie di punti di riferimento con posizioni note, hanno utilizzato RANSAC.

Come trarrai vantaggio

(I) Approfondimenti e convalide sui seguenti argomenti:

Capitolo 1: Consenso del campione casuale

Capitolo 2: Stimatore

Capitolo 3: Minimi quadrati

Capitolo 4: Valore anomalo

Capitolo 5: Convalida incrociata (statistiche)

Capitolo 6: Errori e residui

Capitolo 7: Modello di miscela

Capitolo 8: Statistiche robuste

Capitolo 9: Unione di immagini

Capitolo 10: Ricampionamento (statistiche)

(II) Rispondere alle principali domande del pubblico sul consenso del campione casuale.

(III) Esempi del mondo reale per l'utilizzo di consenso campione casuale in molti campi.

A chi è rivolto questo libro

Professionisti, studenti universitari e laureati, appassionati, hobbisti e coloro che vogliono andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di consenso del campione casuale.

 

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 30 apr 2024

Anteprima del libro

Capitolo 1: Consenso a campione casuale

Al fine di stimare i parametri di un modello matematico da un insieme di dati osservati che includono valori anomali, è possibile utilizzare il processo iterativo noto come consenso a campione casuale (RANSAC). In quanto tale, può anche essere visto come una tecnica per identificare i valori anomali. Questo algoritmo non è deterministico poiché genera solo un risultato adatto con una data probabilità, che aumenta con il numero di iterazioni consentite. Nel 1981, Fischler e Bolles di SRI International rilasciarono l'algoritmo al pubblico per la prima volta. Con RANSAC, sono stati in grado di risolvere il problema della determinazione della posizione (LDP), che consiste nel trovare i punti nello spazio che si mappano su un'immagine come una raccolta di punti di riferimento con coordinate fisse.

RANSAC è un metodo che impiega il sottocampionamento casuale molte volte. Gli inlier sono dati la cui distribuzione può essere spiegata da un insieme di parametri del modello, anche se con un notevole rumore, mentre gli outlier sono dati che non corrispondono al modello, in base a un'ipotesi fondamentale sui dati. Esempi di fonti di valori anomali includono valori eccessivi del rumore, misurazioni errate e dati interpretati in modo errato. RANSAC implica anche l'esistenza di un processo in grado di stimare i parametri di un modello che idealmente spiega o adatta questi dati, dato un insieme (spesso limitato) di inlier.

L'adattamento bidimensionale della linea è una semplice illustrazione di questo principio. Se questa raccolta include sia gli inlier (punti che possono essere approssimativamente adattati a una linea) che gli outlier (punti che non possono essere adattati a questa linea), il metodo dei minimi quadrati per adattare le linee probabilmente risulterà in una linea che non si adatta correttamente ai dati. Il modello è abbinato in modo ottimale a tutti i punti dati, anche quelli estremi. Tuttavia, RANSAC cerca di trovare un modello lineare che non includa i valori anomali e utilizzi invece solo gli inlier nei suoi calcoli. A tale scopo, vengono utilizzati molti campioni casuali dei dati per adattare i modelli lineari e viene quindi restituito il modello che fornisce il massimo adattamento a una parte dei dati. Un sottoinsieme casuale costituito completamente da inlier avrà il miglior adattamento del modello perché è più probabile che gli inlier siano connessi linearmente rispetto a una combinazione casuale di inlier e outlier. La probabilità che l'algoritmo abbia successo dipende dalla percentuale di inlier nei dati e dalla selezione di numerosi parametri dell'algoritmo, e infatti non vi è alcuna garanzia che un sottoinsieme di inlier venga scelto in modo casuale.

Un set di dati con diversi valori anomali che richiede un'analisi di regressione lineare.

Regressione RANSAC; I valori anomali non hanno alcun effetto sulla media.

L'algoritmo RANSAC è un metodo di apprendimento basato sui dati per stimare i parametri del modello da campioni osservativi. RANSAC utilizza il metodo di voto per ottenere il risultato più adatto per un determinato set di dati i cui elementi di dati includono sia gli inlier che gli outlier. I punti dati del set di dati vengono utilizzati come schede elettorali per uno o più modelli. Questa tecnica di voto è implementata in base a due presupposti: (a) ci sono abbastanza caratteristiche per concordare su un modello decente, e (b) le caratteristiche rumorose non voteranno in modo coerente per un singolo modello (pochi valori anomali) (pochi dati mancanti). L'algoritmo RANSAC è costituito principalmente da due fasi, entrambe eseguite in modo iterativo:

Un sottoinsieme casuale del set di dati di input viene scelto per fungere da campione nella prima fase. Gli elementi di questo sottocampione vengono utilizzati per calcolare un modello di raccordo con i parametri del modello. I parametri del modello possono essere calcolati utilizzando solo i dati della cardinalità del sottocampione.

La seconda fase del processo prevede la verifica di quali parti dell'intero set di dati sono in accordo con il modello istanziato dai parametri stimati del modello. Se un'informazione non è conforme al modello entro un margine di errore predeterminato, viene classificata come valore anomalo. I punti dati al di fuori di questo intervallo sono considerati valori anomali.

Il gruppo di valori anomali utilizzato per calibrare il modello è noto come set di consenso. Fino a quando non viene formato un insieme di consenso con un numero sufficiente di valori anomali, l'algoritmo RANSAC ripeterà iterativamente i due passaggi precedenti.

I valori dei dati osservati, un modello adatto a tali osservazioni e i parametri di confidenza che indicano i valori anomali sono gli input dell'algoritmo RANSAC. L'algoritmo RANSAC raggiunge il suo scopo eseguendo iterativamente i seguenti passaggi, che vengono elaborati di seguito:

Scegli un campione dei dati originali a caso. Puoi pensare a questo gruppo come ai valori anomali fittizi.

L'insieme di valori anomali potenziali viene utilizzato come input per una procedura di modellazione.

Segue una verifica di tutti i dati rispetto al modello montato. L'insieme di consenso è il sottoinsieme di punti dati originali che minimizza la funzione di perdita per il modello stimato (ad esempio, l'insieme di inlier per il modello).

Se una percentuale sufficientemente ampia di osservazioni rientra nell'insieme di consenso, il modello stimato può essere considerato di qualità adeguata.

È possibile che la ristima del modello con i dati dell'intero set di consenso produca risultati migliori. L'affinamento dell'adattamento del modello nel tempo verrà eseguito con l'aiuto della qualità dell'adattamento, una misura di quanto bene il modello si adatta all'insieme di consenso (ad esempio, impostando questa misura come criterio di qualità dell'adattamento all'iterazione successiva).

Ogni iterazione di questo processo comporta il rifiuto di un modello perché troppo pochi punti fanno parte dell'insieme di consenso, oppure un modello rivisto con una dimensione maggiore dell'insieme di consenso rispetto all'iterazione precedente. Questo processo viene ripetuto fino a quando non viene trovato un set di parametri del modello sufficientemente valido.

Valori anomali e valori anomali in RANSAC. Questo esempio di adattamento lineare punto per punto include 7 valori anomali (punti dati che si adattano bene al modello in base ad alcuni criteri). Poiché la maggior parte dei punti dati si raggruppa attorno a una linea lineare, l'adattamento è scadente (cioè più inlier).

Di seguito è riportato uno pseudocodice che implementa l'algoritmo RANSAC di base:

Dedito:

data: un insieme di osservazioni.

model: un modello per spiegare i punti dati osservati.

n – Il numero minimo di punti dati necessari per stimare i parametri del modello.

k – Il numero massimo di iterazioni consentite nell'algoritmo.

t – Un valore di soglia per determinare i punti dati che si adattano bene al modello (inlier).

d – Il numero di punti dati vicini (inlier) necessari per affermare che il modello si adatta bene ai dati.

Ritorno:

bestFit: i parametri del modello che possono adattarsi meglio ai dati (o null se non viene trovato alcun modello valido).

iterazioni = 0

bestFit = null

bestErr = qualcosa di veramente grande // Questo parametro viene utilizzato per affinare i parametri del modello in modo che i dati si adattino al meglio man mano che le iterazioni procedono.

mentre le iterazioni < k fanno

maybeInliers := n valori selezionati in modo casuale dai dati

maybeModel := parametri del modello adattati a maybeInliers

confirmedInliers := insieme vuoto

per ogni punto nei dati do

se il punto si adatta maybeModel con un errore minore di t allora

aggiungi un punto a confirmedInliers

fine se

fine per

se il numero di elementi in confirmedInliers è > d allora

Ciò implica che potremmo aver trovato un buon modello.

Ora prova quanto è buono.

betterModel := parametri del modello adattati a tutti i punti in confirmedInliers

thisErr := una misura di quanto betterModel si adatti a questi punti

se questoErr < miglioreErr allora

bestFit := betterModel

bestErr := thisErr

fine se

fine se

Incrementa iterazioni

fine mentre

return bestFit

Lo pseudocodice, rispecchiato in Python. Inoltre, questa definizione LinearRegressor basata sui minimi quadrati, l'applicazione RANSAC e la rappresentazione grafica risultante risolvono un problema di regressione 2D:

Da Copia Importa Copia

Importa numpy come NP

Da numpy.random import default_rng

rng = default_rng()

classe RANSAC:

def __init__(self, n=10, k=100, t=0.05, d=10, model=Nessuno, loss=Nessuno, metrico=Nessuno):

se stesso.n = n # 'n': numero minimo di punti dati per stimare i parametri

se stesso.k = k # 'k': Numero massimo di iterazioni consentite

se stesso.t = t # 't': Valore di soglia per determinare se i punti sono adatti bene

se stesso.d = d # 'd': numero di punti dati vicini necessari per asserire che il modello si adatta bene

se stesso.model = model # 'model': classe che implementa 'fit' e 'predict'

se stesso.loss = loss # 'loss': funzione di 'y_true' e 'y_pred' che restituisce un vettore

se stesso.metric = metric # 'metric': funzione di 'y_true' e 'y_pred' e restituisce un float

se stesso.best_fit = Nessuno

se stesso.best_error = np.Inf

def fit(auto, X, y):

for _ in range(self.k):

ids = rng.permutazione(X.shape0])

maybe_inliers = ids[: se stesso.n

maybe_model = copia(se stesso.modello).adatta(Xmaybe_inliers], ymaybe_inliers])

soglia = (

se stesso.perdita(yids][sé.n :], maybe_model.predict(Xids][self.n :]))

< me stesso.t

)

inlier_ids = idsself.n :][np.flatnonzero(soglia).appiattire()]

se inlier_ids.taglia > sé.d:

inlier_points = np.hstack([maybe_inliers, inlier_ids])

better_model = copia(se stesso.modello).fit(Xinlier_points], yinlier_points])

this_error = sé.metrica(

yinlier_points], better_model.predict(Xinlier_points])

)

se this_error < se stesso.best_error:

se stesso.best_error = this_error

se stesso.best_fit = maybe_model

Ritorna se stesso

def prevedere(se stesso, X):

Ritorna se stesso.best_fit.prevedere(X)

def square_error_loss(y_true, y_pred):

Andata e ritorno (y_true - y_pred) ** 2

def mean_square_error(y_true, y_pred):

Ritorno NP.somma(square_error_loss(y_true, y_pred)) / y_true.forma0

classe LinearRegressor:

def __init__(auto):

se stesso.params = Nessuno

def