Fichas
Sin título
Fichas del conjunto (56)
- 1How a search-based problem-solver worksMakes decisions based on likely consequences of potential actions
Generates states reachable by performing a single action and then selects one and if it's not a goal, expands on it. It continues expanding on nodes until it finds a goal or fully explores the state space. - 2The problem The search tree The state spaceThe problem is a series of problem states
The search tree is a tree grown by exploring the state space.
A state space is all allowed problem states, creating a graph connected by graphs with arcs being legal moves. - 3Combinatorial ExplosionPotential search tree grows explosively with increasing depth
Branch factor b to depth n, b^n new nodes - 4Dynamic Programming PrincipleRemember only the best way of reaching each state, don't repeat work already done
Example: In DTW when matching pattern to template in time-time plane you only consider the best route to a given point given the best route to its predecessors - 5Search strategy requirementsGUARANTEED to find a solution
ADMISSIBLE - finds a optimal/sufficient solution
EFFICIENT - Efficiency is solution nodes / total visited nodes
Optimal strategy would only visit nodes on the optimal solution path - 6Depth-FirstRecursively expand on one of successors from previous iteration until goal is reached or dead-end.
If a dead-end is reached, resume search at last level where there's an alternative, known as backing up.
Not admissible. - 7Breadth-first searchExpand all nodes at level I before moving to level i+1
Admissible if uniform costs, not very efficient as wastes a lot on visiting nodes not on the solution path or even going towards it. - 8Depth-bounds searchAn alternative to depth-first search.
Search depth-first to limit N and keep list of nodes at this level.
If open is empty with no solution, add list of nodes at N to open and increase N
Assuming you only increased the level by 1 each time and started with N=1, it would be admissible but equal to breadth-first - 9Beam searchBreadth-first but it only expands the best few nodes at each level.
- 10Branch-and-boundA generalisation of breadth-first where you visit the node with minimum accumulated cost from the start first
Undirected and wastes efforts on paths not getting closer to goal
With no extra knowledge, best to preserve admissibility - 11Best-first searchHas estimates of remaining cost from any node to goal node
Not admissible because it relies on estimates - 12A* AlgorithmUses best-first and branch-and-bound
Calculates total cost from start to goal through the some node, using the cost of start to that node and the estimated cost to the goal from that node.
Non-optimal complete solution always longer than optimal non-complete solution thus admissible as long as estimates are underestimates. - 13Hill climbingYou have a function that identifies the merit of some state and you need to maximise it by moving to the state with the highest merit, keep going until no state you can move to from the current has a higher merit.
- 14Genetic Algorithm Simulated AnnealingSearch from different starting positions and take the best result
Have a chance to make a move not increasing objective function to try find a better maximum, chance to do this goes down as more moves are made, allowing more of problem space to be explored. - 15Connected Speech Recognition DTWSpeech is distribution of energy through time and frequency represented in spectograms.
Templates of words stored as spectograms in a library
Local distance measures for similarity of singular time-frames of data in template with frame in input data and then plotted in time-time plane.
Minimum-cost path from bottom left to top right, constraints on movement.
To get best to i,j you select minimum cost to i,j then add local cost at i,j
Repeat to get best route to top right - 16Constraints of DTWRequires words to be isolated and only works for a small vocabulary
- 17Viterbi AlgorithmFind best sequence of templates to match data
Consider them together and move forward using DTW.
When a template completes consider restarting each template at next time frame but adding to score and remembering the path.
At the end you get a best path through a template sequence. - 18Constraint satisfaction problemState has factored representation, set of variables and each variable has a domain, also a set of constraints.
Applying constraints changes the domains
After applying a constraint, if the domain changes, propagate the domain to the other constraints recursively
If cardinality of domains of variables is not 1, turns to a search problem.
Attempt to find set of values that satisfy all constraints. - 19Skilled gameplayInvolves look-ahead, planning, strategy, judgement, are well-defined, providing a tractable micro-world, let you test programs against people and other machines.
Important problem solving abilities. - 20Gameplay2-opponent games no chance element, both players complete knowledge of game state at any time.
Search-tree is called game-tree, exploration is called look-ahead.
Terminal nodes/leaves represent board positions where result of game is known for certain. - 21Requirements for gameplayWay of representing board positions, legal move generator using rules, way of detecting terminal board positions, program to explore game tree.
- 22How gameplay search works unoptimizedWIN means player to move after this move wins, LOSS is same but for losing.
If all successors of a node are win, label it loss, else label it win.
Backtrack up a level and repeat once all nodes on that level are labelled
Terminate when root labelled, if labelled win find successor labelled loss and play that. - 23How gameplay search works optimizedBacktrack from win: Label all nodes in same state win, remove their successors recursively from open, if any node labelled win has all children win, label it loss, backtrack from loss.
Backtrack from loss: Label all nodes in same state loss, remove their successors recursively and label their parents win, backtrack from win. - 24Combinatorial explosion in gameplayOnly part of game-tree can be searched, not necessarily up to terminal nods, so need to assess merit of positions we can reach using an evaluation function.
Weighted polynomial with weights and features as functions - 25Problems with evaluation functions in gameplayArguable if turn board position to a number, static not assessing dynamics like building threat, more accurate for simpler positions, assumes features are independent, trade-off between complexity and depth of search.
- 26Partial look-ahead also known as backup NOT minimaxingGrow tree as far as you can, compute merit for each leaf and backtrack through the tree.
A node at maximising level given backed-up value that is maximum of children, minimising level the same but for minimum.
Assumes opponent thinking in similar way with same evaluation function etc - 27Alpha-beta pruningConduct minimax backtrack without backing up all nodes, keep provisional backed-up-value whose value can rise but not decrease, opposite for min
Work left to right starting at bottom, discontinue work below nodes that wont be chosen by their parent
Postpones but doesn't remove combinatorial explosion, returns same values as a full minimax - 28Heuristic PruningMoves are ordered by plausibility, search effort expended according to ranking, low plausibility never considered, not guaranteed as it's heuristic.
- 29Beyond the horizonDelay but not preventing disasters, one way is to continue search past situations considered to be dynamic like check, loss of piece, etc
Another way is to grow a small secondary tree around the move you are considering and calculate its backed up value and compare it to the nodes initial merit. - 30Samuels chess program2 computers playing each other, increase/decrease weights for features contributing to good moves or to defeat
If a weight became too low, feature replaced by new feature in pool
A used fixed evaluation best so far, B would use the same with random adjustments, if B keeps winning B is moved to A and it repeats. - 31Differences between human and machine gameplayProgram has no long-term plan/strategy and considers situation afresh each move, no regard for who their opponent is
Human adapts to opponent has long-term strategy, selective and depth-first search, not considering all moves but just a few optimal ones - 32Knowledge-based systemsUse knowledge about problem domain to solve problems, matching information to current problem state.
Knowledge representation scheme is representation of how knowledge about problem will be stored in a data structure - 33Expert SystemsConfine knowledge to restricted problem domain
Expert System shell: Provides general mechanism for problem solving and then adapted to a specific domain - 34Deduction, Induction, AbductionCreate new facts from prior accepted facts, form if X then Y where you have X and deduce Y
Induction forms generalisation from existing knowledge and shows it being true in one case means it is true in the next, form X1->Y X2->Y X3->Y so induce X->Y
Abduction: Forms conclusion using information known and inferring the most likely explanation for observations, example have Y hypothesize X - 35Forward Chaining Backward ChainingForward-chaining is data driven, moves antecedents to consequents.
Backward-chaining is hypothesis driven, attempts to prove/find some consequent.
Both use monatonic reasoning, fact remains true once asserted. - 36Within and between cycle repetitionFind rules sharing some antecedents, duplicate work of checking these antecedents, create rule network to create intermediate node capturing what they have in common
Remember partial matches called tokens containing remaining antecedents and context formed by those that matched to stop duplicate work - 37Production SystemsImplement controlled forward chaining using short-term memory containing list of facts which can be deleted
Instead of rules there are productions with antecedents, a predicate that returns true/false, modifyContext that modifies context are successful match
In a successful match if predicate returns true modifyContext then fires - 38Production System InterpreterScans through productions in order until successful match, checks predicate, if true runs modify context
Conflict Resolution: If more than one has antecedants and predicate satisfied, which fires? - 39JAVAOOP is a natural framework for representing knowledge, ability to inherit is useful for making artificial intelligence, i.e. adapting a general search problem solver to a specific problem.
Can't store code as knowledge, better known as being unable to treat functions as first-class objects, which is advantage of functional programming languages. - 40PlanningFind sequence of actions to transform initial to goal, but make use of potential actions and how they change the state and their preconditions
- 41Means end analysisFind differences between initial and goal state, find operator to minimise this distance, satisfy its preconditions (by making another plan) and then use the operator
Continue until goal state reached - 42STRIPSEach operator has actList, what to add to plan if used, addList and delList for what's added/removed to current state
List of preconditions to satisfy
STRIPS1 is given goal list and finds plan to reach state where they're satisfied, calls STRIPS2 with differences
STRIPS2 is given difference, finds operator to reduce it and calls STRIPS3 to apply it
STRIPS3 given operator and context, calls STRIPS1 to find plan to satisfy preconditions then applies it - 43Limitations of STRIPSOperators have to come in right order, goal conflict where trying to do one thing undoes another, endless recursion, also no attempt to decide what goal to work on first.
- 44Perception vs KnowledgeReal intelligent systems don't get a given knowledge base and problem, need to acquire knowledge through learning and get input by making sense of data being input from outside world.
- 45Common perception problemsAmbiguous figures
Paradoxical pictures (suggest things that are not possible)
System error: correct unusual hypothesis, so system prefers more believable one
Distortion illusion: Size constancy operating when it shouldn't
Perceptual invention: See something not there because image suggests its existance - 46Why perception is importantPeople's behaviour based on belief or reality, not reality itself.
Important so we can develop AI further so it can understand the world around us - 47McGurk effectShows visual cues override auditory cues when they clash
- 48Auditory PerceptionSums to
Transforming sound waves into signals in the auditory nerve
Filtering out background noise
Reconstructing complex sound patterns into recognisable percepts in the brain - 49Cocktail party effectMultiple sources, listen to one, rest become background noise
- 50Bottom-up and top-down processingInformation processing guided by higher/lower-level models like:
Loudness/frequency/timing/sync
Or
Experiences and expectations - 51Caregiver speechExaggerated information, longer pauses, slower tempo, improves learning
- 52Computational auditory scene analysisGet input speech and break it into features, then build features into discrete objects and group them together
- 53Accuracy of estimatesEstimated cost from state to goal state
/
Actual cost from state to goal state - 54ExperimentsSanity checks are made to make sure it's working correctly
Baseline system is what you're trying to improve on
Significance Testing is where you test if the results are statistically significant, this is done by calculating probability that a change in the dependent variable happened by chance or not. - 55Sequence MatchingProblem is to find the best sequence of models to match the given data, e.g. connected word recognition, gene sequencing.
- 56Book movesHave libraries of standard board positions, example being standard chess openings, shows you what to do in given scenarios.
Problem is recognising when situation isn't identical to a stored book move but is similar.
Información
- Descripción
- Fichas sobre Sin título, creado por thomas jeffery el 23/05/2019.
- Creado por
- thomas jeffery
- Visitas
- 2
- Valoración