Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

computer science > Introduzione all'intelligenza artificiale > Flashcards

Introduzione all'intelligenza artificiale Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

Cos’è il test di Turing?

A

Il test di Turing è un test nel quale si cerca di capire quale dei due interlocutori, che sono disposti in stanze diverse, sia un essere umano e chi sia una macchina

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Cos’è un agente razionale?

A

E’ un agente che per ogni sequenza di percezioni massimizza le prestazioni, basandosi su percezioni passate e conoscenza pregressa

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Cos’è la descrizione PEAS?

A

Serve per descrivere un problema e significa Performance, environment, actuators, sensors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Quali sono le principali proprietà dell’ambiente?

A

L’osservabilità, numero di agenti, predizione dei cambiamenti, episodico o sequenziale, temporale, caratterizzazione dei valori e lo stato di conoscenza dell’agente

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Quali sono i tipi di agente?

A

Agenti basati su tabella, agenti reattivi semplici, agenti basati su modello, agenti con obiettivo, agenti con valutazione di utilità, agenti che apprendono

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Come può essere formulato un problema?

A
  1. Stato iniziale
  2. Possibili azioni nello stato corrente
  3. Modello di transizione
  4. Test obiettivo
  5. Calcolo del costo del cammino
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Il problema dell’itinerario e il problema dell’aspirapolvere sono problemi di che tipo?

A

Problemi di ricerca

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Da che cosa è composto un nodo negli algoritmi di ricerca?

A
  1. Stato del nodo
  2. Il nodo padre
  3. la transizione tra padre e nodo corrente
  4. il costo del cammino dal nodo di partenza fino al nodo corrente
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Che cos’è la frontiera e come può essere implementata?

A

LA frontiera è l’insieme dei nodi ancora da visitare e può essere implementata come una FIFO, una LIFO o una coda con priorità

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Fai alcuni esempi di strategie di ricerca non informate

A

BFS, DFS, UCS, DLS e IDS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Come risolviamo i problemi di ridondanze e cicli nelle ricerche ad alberi?

A
  1. Eliminare il padre dalla frontiera
  2. Controllare che i nodi successori non siano anche antenai
  3. Salvarsi in memoria tutti i nodi già visitati
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Anlisi della BFS

A

Strategia sia completa che ottimale con complessità temporale e spaziale uguale a O(b^d) (la complessità spaziale è molto alta) con b fattore di ramificazione e d profondità

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Analisi della DFS

A

Strategia nè completa nè ottimale (perchè si possono creare loop), complessità temporale O(b^m) con b fattore di ramificazione e m lunghezza massima dela cammino e complessità spaziale O(b*m)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Come vengono gestite le code in BFS e DFS?

A

La BFS utilizza una FIFO, mentre la DFS utilizza una LIFO

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Qual è la differenza tra DFS alberi e DFS grafi?

A

DFS grafi perde il vantaggio in memoria ma è un algoritmo completo su un insieme finito

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Qual è il vantaggio della DFS con backtracking?

A

Salva sullo stack lo stato iniziale di un percorso e in caso di fallimento può tornare lì, occupando in memoria solamente O(m)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Cos’è la DLS

A

E’ la ricerca a profomdità limitata, si pone un limite l alla profondità massima e in questo caso è completa, con stessa complessità della DFS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Cos’è IDS?

A

Ricerca approfondita a partire dalla DLS, ovvero si va a aumentare ad ogni iterazione il valore di l (profondità), in questo modo la strategia è completa e ottimale

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Su cosa scegliamo se ricercare in avanti o indietro?

A

In base a b, il fattore di ramificazione

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

In cosa consiste la bdir?

A

Effettua sia una ricerca in avanti che una all’indietro e quindi è sicuramente completa e ottimale con complessità di tempo e spazio O(b^d/2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

In cosa consiste la UC?

A

La ricerca uniforme è una BFS con pesi tutti uguali, la coda è una priority queue ordinata in base al costo del cammino (prima quelli meno costosi). Il goal vieste testato prima del ciclo per creare la frontiera del nodo che stiamo guardando e subito dopo il pop dalla frontiera.
E’ una stretia completa e ottimale a patto che il costo degli archi sia maggiore di 0 e la complessità spaziale e temporale è O(b^1+[C/alpha]), con C/alpha numero di mosse al caso pessimo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

In cosa consiste la ricerca euristica?

A

Dato che la ricerca esausitiva bruteforce è spesso impraticabile, si usa la conoscenza euristica per scremare le varie possibilità con una funzione f(n)=g(n)[costo del cammino] + h(n)[funzione tipo distanza in linea d’aria]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Cosa si intende per BFH

A

La best first heuristic è simile a una UC ma usa la funzione eurstica f(n) per ordinare la priority queue e la funzione h(n) corrisponde al valore stimato da n al goal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Che cos’è il GBF?

A

Il greedy best first è un BFH che mette f(n) = h(n) e quindi si espande sempre verso il nodo più vicino (non tenendo conto del costo)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Descrivi l’algoritmo A

A

A è un best first ma se h(n)=0 ottengo un UC, se g(n)=0 ottengo un GBF. E’ completo se e solo se g(n)>=d(n)*alpha con alpha costo minimo dell’arco

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Descrivi brevemente l’algoritmo A*

A

A* è un UC con f(n) = g(n) + h(n) per ordinare la coda. Possiamo effettuare una sottostima o una sovrastima della funzione ideale f(n) = g(n) + h(n). Se una euristica è ammissibile, A è ottimale sugli alberi, ma per garantire l’ottimalità sui grafi bisogna garantire la monotonicità (o consistenza)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Quali sono i principali vantaggi di A*?

A

A* non espande i nodi con f(n)>C* ovvero del costo della soluzione ottima, si può eseguire il pruning per risparmiare memoria (che comunque rimane O(b^d+1)) e velocizzare ed è garantita l’ottimalità

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Come scelgo h(n) e g(n) in un algoritmo A*?

A

Devo scegliere un g(n) sottostimato per garantire l’ottimalità, ma allo stesso tempo piu vicino possibile a g*(n) in modo da non fare troppo lavoro inutile. h(n) lo devo scegliere tra le euristiche ammissibili e il più grande possibile per evitare di espandere tutti i nodi

29
Q

Cosa significa che un euristica domina su un’altra?

A

Un’euristica domina su un’altra se i nodi espansi con h2 sono un sottoinsieme dei nodi espansi con h1 e h2 si dice più informata di h1

30
Q

Come valutiamo un euristica?

A

La valutiamo a partire da b* (fattore di ramificazione), dato che riducendo b* anche di poco riduciamo significativamente il numero di nodi espansi o raggiumgiamo profondità nettamente superiori

31
Q

Descrivi i vantaggi dell IDA* rispetto a A*

A

IDA* ad ogni iterazione ricerca più in profondità, se i costi sono tutti uguali (costo k) allora iteriamo di k, se i costi sono variabili dobbiamo garantire che f-limit <= del costo minimo degli archi. Il vataggio è che occupa solo O(b*d) memoria

32
Q

Descrivi i vantaggi dell’RBFS rispetto a A*

A

E’ un algoritmo best first ricorsivo che se si accorge di aver trovato un fallimento, secondo la funzione f(n) allora torna indietro fino al nodo più promettente e riparte da lì. In questo modo lo spazio occupato è lineare O(n) ma si fanno alcuni passaggi in più

33
Q

Qual è la principale caratteristica degli algoritmi a ricerca locale?

A

Non conta l’ordine in cui scelgo i nodi, si cerca solamente di minimizzare o massimizzare il percorso attuale con una funzione f

34
Q

Descriv brevemnte l’algoritmo hill climbing

A

Algoritmo greedy, vengono valutati solamente i successori del nodo attuale e si cerca di massmizzare il valore finale. Se non si trovano nodi con valore più alto di quello attuale si termina.

35
Q

Quali sono i tipi di algoritmo hill climbing?

A

A salita rapida, stocastico o a prima scelta

36
Q

Cosa aggiunge l’algoritmo simulated annealing rispetto all’hill climbing?

A

Introduce un fattore T preso in input che riduce man mano le probabilità di trovare scelt peggiorative

37
Q

Differenze tra beam search e local beam search

A

Nella local beam search ci si salva k stati in memoria e ad ogni passo (se non si trova il goal) si procede con i successori migliori. Se k=1 abbiamo un hill climbing a prima scelta, se k=infinito allora abbiamo un hill climbing a salita rapida. Il local beam stocastico (come gli algoritmi genetici) sceglie i k successori in maniera random e non tra quelli migliori

38
Q

Com’è definito l’hill climbing iterativo?

A

x_new = x_old + eta * delta f(x) con delta f(x) la derivata della funzione e eta come step-size. Se si hanno più dimensioni si usa il gradiente

39
Q

Come può essere definito lo spazio degli stati in giochi con avversario?

A
  1. Stati di gioco
  2. Stato iniziale
  3. Player(s), a chi tocca fare la mossa
  4. Action(s), che mosse puoi fare da s
  5. Result(s,a), fatta la mossa in che stato mi trovo
  6. Terminal-test, costrollo se la partita è terminata
  7. Utility(s,p), pay-off numerico che assegnamo a quella posizione
40
Q

Come si calcola il valore di minmax senza ottimizzazione e qual è la sua complessità?

A

“controllare dispense pagina 5 capitolo 2” con complessità temporale O(b^m) e spaziale di O(m)

41
Q

Qual è la differenza tra minmax e h-minmax?

A

Si introduce una funzione euristica eval(s) per valutare lo stato s, si effettua l’albero fino a profondità d e poi si fa backtracking fino alla radice e si sceglie il percorso migliore

42
Q

Qual è la differenza tra terminal-test e cut-off-test?

A

Il terminal test si fa allo stato terminale, il cut-off-test si fa ogni d passi di profondità

43
Q

Che cos’è l’effetto orizzonte?

A

Potrebbero essere privilegiate mosse che fanno scappare dall’obiettivo, rischiando di finire in un loop

44
Q

Quali sono le condizioni per l’alpha-beta pruning e quali sono le complessità?

A

Eseguo il taglio se v<=alpha o se v>=beta e complessità temporale di O(b^m/2) e spaziale O(m)

45
Q

Quali sono alcune ottimizzazioni che potrebbero essere fatte per l’alpha-beta pruning?

A
  1. Ordinamento dinamico
  2. Potatura in avanti
  3. Database di mosse
46
Q

Com’è formulato un problema CSP?

A
  1. X insieme di variabili
  2. D indieme di domini D_i
  3. C insieme di vincoli
  4. Stato (assegnamento valore a variabile)
  5. Stato iniziale
  6. Azioni
  7. Soluzione
47
Q

Qual è il vantaggio della ricerca nei problemi CSP?

A

Si possono usare euristiche specializzate e ridurre l’insieme dei domini, attraverso le inferenze e il backtracking

48
Q

Descrivi brevemente l’algoritmo di ricerca con backtracking per problemi CSP

A

Le variabili vengono selezionate o tra quelle che hanno meno valori legali che possono assumere o quelle che sono coinvolte in più vincoli possibile.
Il valore da assegnare viene scelto in base a quello meno vincolante
L’inferenza ti permette di verificare in avanti ed eliminare le inconguenze
Il backtracking può essere esguito in maniera cronologica o in maniera intelligente, riducendo i fault

49
Q

Cosa si intende per agenti KB?

A

Sono agenti Knowledge based, ovvero che hanno una base di conoscenza del mondo che li circonda

50
Q

Quali sono le 3 operazioni che può effettuare un agente KB?

A
  1. Tell: inserire una nuova proposizione in KB
    2: Ask: interrogare KB
  2. Retract: eliminare una proposizione dalla KB
51
Q

Qual è la differenza tra KB e DataBase?

A

Le proposizioni nella KB possono essere inserite e vengono inferenziate

52
Q

Quali sono i formalismi con cui si rappresenta la conoscenza?

A
  1. Una sintassi
  2. Una semantica
  3. Un meccanismo inferenziale
53
Q

Descrivi brevemente l’algoritmo TT-Entails

A

L’algoritmo enumera tutte le possibili interpretazioni per KB e valuta se l’interpretazione I soddisfa KB o no

54
Q

Descrivi brevemente l’algoritmo DPLL

A

A partire da una forma congiuntiva classica ci si riconduce a una forma a clausole. I vantaggi di questo approccio sono:
1. Terminazione anticipata
2. Simboli puri
3. Clausole unitarie

55
Q

Descrivi brevemente l’algoritmo WALK-SAT

A

L’algoritmo sceglie cosualmente tra una clausola non ancora valutata e prova a eseguire un flip con probabilita solitamente 0.5 tra un passo casuale o un passo di ottimizzazione (in base all’euristica scelta).
Il numero di flip è determinato da max flip

56
Q

Com’è strutturato un sistema di ML?

A
  1. DATA: ovvero l’input del sistema
  2. MODEL: modello parametrizzato
    2a. TASK
    2b. LEARNING ALGORITHM
    2c. VALIDATION
  3. PREDICTION: ovvero l’output
57
Q

Qual è la differenza tra supervised learning e unsupervised learning?

A

Il supervised learning fornisce un training set composto da coppie <input, output>. Quindi il modello basandosi sul training set deduce anche gli altri evetuali dati. L’unsupervised learning invece riclassificherà da solo il training set fornito utilizzando uno degli algoritmi principali tra il clustering, Preprocessing e Modelling the data density

58
Q

Descrivi alcuni esempi di modelli

A
  1. Modelli lineari
  2. Regole simboliche
  3. Modelli probabilistici
  4. Approcci basati su un’istanza
59
Q

Quali sono le due fasi della validazione (generalizzazione)?

A
  1. Fase di apprendimento
  2. Fase predittiva
60
Q

Cosa si intende per comcept learning?

A

Apprendimento per categoria, ovvero vengono mostrati prima una serie di esempi gia categorizzatie e successivamente vengono riconosciuti a partire dagli esempi precedenti

61
Q

Quali sono gli algoritmi del concept learning che abbiamo analizzato?

A

Find-S, Version Space, List-Then-Eliminate e il Candidate Elimination

62
Q

Nel concept learning come è definito un training example e qual è la regola di coerenza?

A

Un esempio di training è la coppia <x,c(x)> e l’ipotesi h è soddisfatta se h(x)=1. h è consistente se per ogni x appartenente a X h(x)=c(x)

63
Q

Qual è la dimensione dello spazio delle ipotesi nel concept learning?

A

|H|=2^numero_di_istanze

64
Q

Descrivi brevemente l’algoritmo Find-S

A

Si parte dall’ipotesi più specifica h={0,0,0,0} e valutando un’istanza positiva alla volta la andiamo sempre di più a generalizzare e ritorniamo in output l’ipotesi coerente

65
Q

Descrivi brevemente l’algoritmo Candidate elimination

A

Definisci S0 ={0,0,0,0,0} e G0={?,?,?,?,?}. SI va a valutare ciascuna instanza, sia positiva che negativa e se è positiva si generalizza S e se è negativa si specifica G

66
Q

Il learning Unbiased è utile?

A

No, non solo è conveniente ma è anche necessario avere delle conoscenze preliminari per riuscire a genereare un h generalizzata

67
Q

Che cos’è l’inductive bias?

A

Il sistema con inductive bias che introduce l’asserzione “H contiene il concetto target” è uguale a un sistema input-output con candidate elimination, quindi il bias ci permette di trasformare il problema da induttivo a deduttivo

68
Q
A

computer science (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions