# Kapittel 2 - Intelligent Agents ## Agent An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. ### Agent function Mathematically speaking, we say that an agent’s behaviour is described by the agent function that maps any given percept sequence to an action. ### Rational agent For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. ### Task environment PEAS - Performance, Environment, Actuators, Sensors. ### Properties of task environments #### Fully Observable vs. Partially Observable If an agent's sensors has access to the complete state of the environment, at all times, we say that the environment is _fully observable_. An environment can be _partially observable_ because of noise or inaccurate sensors. It can also be partially observable when sensors only give information about parts of the environment. If an agent don't have sensors, we call the environment _unobservable_. #### Single agent vs. multiagent || **Single agent:** || Example: Crossword, sudoku || || **Multi agent:** || Example: Chess, ludo || || **Competitive multiagent environment:** || E.g. in chess, where two players are playing against each other. One contestant tries to maximize his performance by minimizing the other's. || || **Cooperative multiagent environment:** || When driving cars, drivers cooperate not to crash into each other. || #### Determenistic vs Stochastic || **Deterministic:** || Any action has a single guaranteed effect. There is no uncertainty about the state that will result from performing an action. || || **Strategic:** || If the environment is deterministic except from the actions of other agents, we say that the environment is strategic. || || **Stochastic:** || There is some uncertainty about the outcome of an action. || #### Episodic vs. Sequential || **Episodic:** || The agent's experience is divided into atomic episodes. Each episode consists of the agent perceiving and then performing a single action. The episodes are independent. The choice of action in each episode depends only on the episode itself. || || **Sequential:** || The current decision could affect all future decisions. || #### Static vs. Dynamic || **Static:** || Everything stays unchanged until the agent makes a change. || || **Dynamic:** || The environment might change while the agent is considering what to do. || || **Semidynamic:** || The environment itself does not change with the passage of time, but the agents performance score does. || #### Discrete vs. Continous

#### Known vs. Unknown This isn't so much about the environment as the agent's (or the programmer's) knowledge about the laws of physics in the environment. In a known environment, the outcomes for all actions are given. In an unknown environment you can't predict all outcomes, even if you have a full overview of the environment. This means that the agent must learn from its actions, and how the environment reacts to them. ### Various Agent Types #### Simple reflex agent The simplest kind of agent. Selects actions on the basis of the current percept, ignoring the rest of the percept history. The agent will work only if the correct decision can be made on the basis of only the current percept - that is, only if the environment is fully observable (if it's not fully observable, the agent may also make a decision, but it might not be a optimal one). Infinite loops are often unavoidable operating in partially observable environments. This can sometimes be escaped if the agent randomizes its actions. #### Model-based reflex agents Maintain internal state to track aspects of the world that are not evident in the current percept. Two kinds of knowledge needs to be represented/coded in the agent program to update the internal state info: - How the world evolves independently of the agent (e.g., an overtaking car generally will be closer behind than it was a moment ago) - How the agent's own actions affect the world (e.g., when the agent turns the steering wheel clockwise, the car turns to the right or that after driving for five minutes northbound on the freeway one is usually about five miles north of where one was five minutes ago) #### Goal-based agents Works as model-based, but also take the agent's goals into account. #### Utility-based agents Works like the other agents, in addition to trying to maximize their expected “happiness”. Needs a utility function to determine what action leads to the highest performance measure. #### Learning agents Learns from their actions. A learning agent can be divided into four conceptual components: || **Learning element** || Responsible for making improvements. || || **Performance element** || Responsible for selecting external actions (In the other agents, this is considered as the whole agent). || || **Critic** || Gives feedback to the learning element on how the agent is doing and determines how the performance element should be modified to do better in the future. It tells the agent how well it is doing with respect to a fixed performance standard. || || **Problem generator**  || Responsible for suggesting actions that will lead to new and informative experiences. || # Kapittel 3 - Solving Problems by Searching Search: is a (preferably methodical) process for finding something. ## Uninformed vs. informed: Do points in the search space give information that helps the searcher to determine the next step? ## Partial vs. Complete solutions: Could the current state of the search always be considered a complete solution? Or is it often a partial state that must be incrementally enhanced to become a solution? Søk med complete solutions kalles ofte local search ## Single-state problem formulation: A problem is defined by four items: - Initial state - Successor function - Goal test - Path cost A solution is a sequence of actions leading from the initial state to the goal state. Uninformed Search strategies use only the information available in the problem definition (Breadth-first search, Depth-first serach, Uniform-cost search, Depth-limited search, Iterative deepening depth-first search, bidirectional search) ## Breadth-first search fringe is a FIFO. New successors go at the end complete?: Yes time: O(bd+1) - Horrible space: O(bd+1)- keeps every node in memory optimal?: Yes, if cost=1 per step. Not optimal in general ## Uniform-cost search fringe is a queue ordered by path cost, lowest first (ignoring h and just looking at the g value) ## Depth-first search fringe is a LIFO queue. Put successors at front complete?: No, fails in infinite-depth spaces, and fails with loops time: O(bm)- Horrible space: O(bm)- linear in space :-) (må bare ta vare på alle barna til forfedrene langs ruten) optimal?: No ## Depth-limited search: Depth-first search with a depth limit. Does not go further than the depth limit. ## Iterative deepening search You do depth-limited search, but you may be doing several of them. You start with a limit of 1, and increase the limit with +1 for every time you do the search. complete: yes time: O(bd) space: O(bd) optimal: Yes, if step cost = 1. Altså: Iterative deepening search uses only linear space, and not much more time than other uninformed algorithms ## Best first search Idea: use an evaluation function for each node – estimate of “desirability” Expand most desirable unexpanded node Implementation: fringe is a queue sorted in decreasing order of desirability Special cases: greedy search, A* search ## Greedy serach Evaluation function h(n) (heuristic) = estimate of cost from n to the closest goal Greedy search always expands the node that appears to be closest to goal Complete?: No – can get stuck in loops. But is complete in finite space with repeated-state checking Time: O(bm), but a good heuristic can give dramatic improvement Space: O(bm)- keeps all nodes in memory Optimal?? No ## A\* A\* er en form for best-first search hvor ideen er å ikke utvide veier som er “dyre”. A\* evaluerer noder ved: $f(n) = g(n) + h(n)$ $g(n)$ - kostnaden for å komme seg til noden $h(n)$ - estimert kostnad for å komme seg fra noden til målet. (heuristic) $f(n) = g(n) + h(n)$ - estimert totalkostnad ved å gå gjennom n for å nå målet. $h(n)$ må være slik at den aldri overestimerer, det vil si $h(n) ≤ h*(n)$ hvor $h*(n)$ er den faktiske kostnaden for å gå til n. Når A\* traverserer grafen følger den stien med noder som gir lavest verdi for $g(n)+h(n)$. A\* begynner med å se på rotnoden. Den legges til en liste som holdes over lukkede noder. Alle barna til rotnoden blir lagt til listen som holdes over åpne noder. For hver av disse nodene legges rotnoden til i listen som hver node holder over foreldrenoden. Rotnoden legges også til som “best parent” for hver av de nye nodene. Dette er fordi rotnoden er den eneste noden som på dette tidspunktet kan være hver av de nye nodenes forelder. For å fortsette søket velger vi noden, fra listen over åpne noder, med lavest $f(n)$ verdi, og gjør følgende: Sjekk om dette er en løsning på problemet. Hvis det ikke er det fortsetter man på resten av punktene Drop den fra listen over åpne noder og legg den til listen over lukkede noder Sjekk alle nabonodene . Legg nodene til listen over åpne noder dersom de ikke er der allerede. Gjør den noden vi har valgt til foreldrenoden til de nye nodene. Dersom nabonoder allerede er i listen over åpne noder, sjekker vi for å se om denne stien er bedre. Åltså sjekk om g(n) verdien for noden er lavere dersom vi bruker den valgte noden på å komme dit. Dersom det ikke er det trenger vi ikke gjøre noe annet enn å legge den valgte noden i listen over foreldrenoder. Dersom g(n) verdien til den nye stien er lavere, endrer vi “best parent” til den valgte noden. Så rekalkulerer vi g(n) og f(n) verdiene til noden. Må også oppdatere g(n) og f(n) verdiene til alle nodene som har dene noden vi har oppdatert som forelder. Dette må gjøres rekursivt ved at barna deres også må oppdateres o.s.v. Complete?: Yes, unless there are infinitely many nodes with f ≤ f (G) Time: Exponential in [relative error in h × length of solution.] Space: Keeps all nodes in memory Optimal?: Yes—cannot expand fi+1 until fi is finished ## Hvorfor A\* er optimal Ettersom A\* algoritmen hele tiden utvider den noden med lavest f(n)-verdi, og h(n) verdien aldri skal overestimere, vil det aldri være mulig å komme til målet med en lavere kostnad enn kostnaden til den noden vi utvider. Derfor vil den første noden vi utvider og som så viser seg å være en løsning, også være den optimale løsningen. Heuristic: Admissible: Er alltid underestimert dvs den er admissible. Fordelen er at vi er garantert å finne minimum kostnadsstien dersom den finnes. Monoton/konsistens heuristikk betyr at kostnaden for å ta et skritt er høyere enn reduksjonen i heuristikken. Ved Monoton heuristikk vil alltid den første stien vi finner til en node være den med korteste.\ Når en har grid-søk kan en god heuristikk være: Manhattan distance - kan kun bevege seg frem/bak eller sidelengs. Euclidean - Det er den lengden man vil måle med en linjal (straight line distance) Dominans: En heuristic (h1) dominerer en annen (h2) dersom h1(n) ≥ h2(n) for alle n. Så lenge begge heuristikkene er admissible kan vi forvente at h1 kommer til å genere færre noder enn h2, og lede til et mer effektivt søk til mål-noden. Det er derfor som generelt bedre å velge en heuristikk med høyere verdier gitt at den er admissible. Relaxed problems Admissible heuristics can be derived from the exact solution cost of a relaxed version of the problem Key point: the optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real problem # Kapittel 4 - Beyond Classical Search ## Local Search The path is unimportant; only the final state matters. Nå bruker vi ikke heuristics, men noe lignende som heter “Objective functions”. Objective function svarer på: “hvor god er du, løsning”? ## Hill climbing Greedy: always moves to states with immediate benefits. Quick on smooth landscapes. Easily gets stuck on rough landscapes. ## Simulated Annealing Randomized søk etter en løsning. Algoritmen prøver å unngå lokale maksimum ved å la det være lov å velge noen dårlige løsninger. Den velger i utgangspunktet bare naboer som forbedrer situasjonen, men ved en viss sansynlighet godtar den andre naboer. Denne sannsynligheten avtar avhengig av hvor dårlig valget var og ettersom temperaturen går ned. Den begynner med en node og en F-target (bestemmer hvor nærme en løsning vi ønsker at vår løsning skal være) og bestemmer seg for en temperatur T (T kan være mellom 1 og 0). Denne starttemperaturen er nå Tmax. Evaluer P ved bruk av objektiv-funksjonen, da får du verdien F(P). Hvis F(P) er ≥ F-target så er P løsningen/en god nok løsning. Hvis ikke: 1. Generer naboene til P 2. For hver nabo regn ut objektiv-funksjonen deres 3. Velg den naboen med høyest objektiv-funksjon score. Pmax 4. Regn ut: q = $(F(P_max) - F(P))/F(P)$ 5. $p = min (1, e^(-q/T))$, r = random number in range [0,1] 6. Hvis r > p: sett $P = P_max$ Hvis ikke: velg en av de andre naboene på random. P = random nabo 7. T = T - dT 8. Sjekk F(P) ≥ F-target (P er nå et nytt punkt/node) Jo lavere T er, jo færre dårlige valg er lov. Jobber med fullstendige løsninger (forsøk) som gradvis blir modifisert til en optimal løsning. Objektiv-funksjonen brukes til å avgjøre hvor god løsningen vi har kommet opp med er. Local Beam Search: K parallel searches Søker parallelt. Kan hoppe til en annens nabo K parallel searches are not independent, since Best K neighbors chosen at each step, but some states may contribute 0 or 2+ neighbors to the next step. Good search = efficient distribution of resources (i.e., the K states). Jiggle can be introduced via Stochastic Beam Search: pick some of the K neighbors randomly, with probabilities weighted by their evaluations. Genetic algorithms (Er ikke så viktig til eksamen) Stochastic Local Beam Search with (some of) the K neighbors generated by crossover. Supports long jumps in search space, and combinations of the best of both parents. Crossover more constructive than destructive...sometimes. # Kapittel 5 - Adversarial Search Classes of games: Perfect info: state of playing arena and other players holdings known at all times. Imperfect info: some info about arena or players not available. Deterministic: outcome of any action is certain. Stochastic: some actions have probabilities outcomes ## MiniMax Starting at a top node, each possible move is depicted down to a maximum depth, or a terminal node (win or lose position). For the leaf nodes at the bottom level, each node is assigned an evaluation function value. The maximum function assigns the values from the point of view of the players (called Max). The valuation function must assign high values to win positions and low levels to losing positions, and a value in between for non-terminal nodes. A draw is typically assigned a value of 0. Then, all values are backed up so that a Max node (Max to move) gets the maximum of its daughter nodes (Min nodes), while each Min node gets the minimum value of its daughter nodes (Max nodes). It is only complete if the tree is finite, and it is only optimal against an optimal opponent (meaning the opponent always picks what is best for it self). The tree is explored as a depth-first search. Heuristic only used at the bottom. ## Alpha-Beta Pruning Alpha-Beta pruning is a way to make Min-Max search much more effective. It is a way of essentially saying “you don’t need to generate any more children, because there is no way we are going to take your path”. It is a method where a node is not evaluated further if it can be proved that the node will never influence the choice. This is done by assigning provisional values (alpha values at Max nodes, beta values at Min nodes) when a value is backed up from below. Only a max node can modify alpha, and only min nodes can modify beta. The alpha and beta values are defined locally at different nodes. They can also be passed in from above. Pruning does not affect the final result but can change the efficiency of the search ### Alpha A modifiable property of a max node Indicates the lower bound on the evaluating of that MAX node. Updated whenever a LARGER evaluation is returned from a child MIN node. Used for pruning MIN nodes. ### Beta A modifiable property of a MIN node Indicates the upper bound on the evaluation of that MIN node. Updated whenever a SMALLER evaluation is returned from a child MAX node. Used for pruning MAX nodes. The values (alpha and beta) are used to see if further processing of a branch is necessary. For instance, if a Min node with beta value β is below a Max node with alpha value α, and β <= α then Max will never choose that node anyway, and any further analysis of the subnodes will not change that. Alpha-beta pruning is order dependent. ### AI Critics Critic = a system that evaluates search states. Very similar to both heuristics and objective functions. Many AI applications involve standard AI search algorithms (A*, Minimax, etc.) plus problem-specific critics. Building the critic is the hard part. Actor = a system for mapping search states to actions. Actor-Critic systems use AI to both compute actions and evaluate states. In some versions, the best action is simply the one that leads to a state with the highest evaluation. # Kapittel 6 - Constraint Satisfaction Problems Constraint satisfaction problem (CSP) A CSP problem is a type of state-search problem defined by: a set of variables a set of domains (legal values) for these variables a set of constraint relations between the variables A problem is solved when each variable has a value that satisfies all the constraints on the variable. a problem described this way is called a constraint satisfaction problem. Can be represented in a graph where nodes are variables and arcs show constraints, by doing this we can divide the problem into subproblems. Felles for løsninger av CSP's Initial state: the empty assignment, { } Successor function: assign a value to an unassigned variable that does not conflict with current assignment. → fail if no legal assignments (not fixable!) Goal test: the current assignment is complete Dette er felles for alle CSP algoritmer. Inteligensen kommer i form av å velge riktige variabler å gi verdier til først, og så å velge hvilken verdi du skal gi variabelen. ## Varieties of constraints: || Unary: || involve a single variable. Eksempel: SAgreen || || Binary: || involve pairs of variables. Eksempel SAWA || || Higher-order: || 3 or more variables. Eksempel: AllDiff || || Preferences: || “better than”-constraints - soft constraints || ## Consistency: ### Node consistency: A single variable is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints. we say that a network is node-consistent if every variable in the network is node-consistent. ### Arc consistency: A variable in CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints. X is arc consistent with Y if for every value in the current domain Dxthere is some value in the domain Dythat satisfies the binary constraint on the arc (X,Y). A network is arc-consistent if every variable is arc-consistent with every other variable. We filter on constraints with binary constraints. We filter on one variable at a time. So we use a stack of constraints where we begin with the top constraint and work our way down. The most popular algorithm for arc-consistency is called the AC-3. To make every variable arc-consistent, the AC-3 algorithms maintains a queue of arcs to consider. Initially the queue contains all the arcs in the CSP. AC-3 then pops off an arbitrary arc {X,Y} from the queue and makes X arc-consistent with Y. If this leaves Dxunchanged, the algorithm just moves to the next arc. But if it revises Dx(makes the domain smaller), then we add to the queue all arcs {Z,X} where Z is a neighbor of X. We need to do this because the change in Dxmight anable further reductions in the domains of Dz, even if we have previously considered Z. If Dxis revised down to nothing, then we know the whole CSP has no consistent solution, and AC-3 can immediately return failure. Otherwise, we keep checking, trying to remove values from the domains of variables until no more arcs are in the queue. At that point, we are left with a CSP that is equivalent to the original CSP - they both have the same solutions - but the arc-consistent CSP will in most cases be faster to search because its variables have smaller domains. ### Path consistency: A two-variable set {X,Y} is path-consistent with respect to a third variable Z, if for every assignment {X=a, Y=b} consistent with the constraints on {X,Y}, there is an assignment to Z that satisfies constraints on {X,Z} and {Y,Z}. Focus on two or more constraints at a time. So we filter with more than one constraint at a time ( X>Z and Y<Z). ### Forward checking Forward checking means that each variable is assigned an apriori set of legal values, and that each assignment leads to a subsequent elimination of all other assignments that become impossible. For instance, whenever a variable X is assigned, for each variable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for X ## Backtracking Search for CSPs The term backtracking search is used for a depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign. Keeping track on the variables domains to make it easier to detect fail. So when placing a variable on the board all other variables domains must be checked. The most prominent strategies for solving CSP with backtracking search is: MRV Heuristics: select the variable with the fewest remaining legal values. Variables with the smallest domain. Degree heuristics: select the variable which is involved in the largest number of constraints. (Its a good choice when MRV gives a tie) Least constraining value: prefer the value that rules out the fewest choices of for the remaining variables in the constraint graph. Forward checking: Keep track of remaining legal values for unassigned variables. Terminates when any variable has no legal values. ## Local Search for CSPs Når algoritmen starter så er initial staten utfylt (feks alle dronningene er plassert utover brettet) og søket går ut på å endre en og en variabel av gangen (dvs en dronning bytter plass av gangen). Poenget med algoritmen er å eliminiere de begrensningene som blir brutt i den gjeldene staten. Hvilken variabel som endres velges random, men hvilken endringer som gjøres avgjøres av heuristicen. Heuristicen går ut på å velge det trekket som krenker ferrest begrensninger (min-conflicts). Velger det som ser best ut akkurat nå. # Kapittel 7 - Logical Agents Knowledge base: set of sentences in a formal language. Logics: Er formelle språk for å representere informasjon slik at konklusjoner kan trekkes Syntax: Definerer hvordan setningene skal bygges opp for å gi mening. Man kan si ”fly et Hanne i sitter”, men det gir ikke mening i forhold til syntax-en til norsk. Man må heller si “Hanne sitter i et fly”. Semantics: Definerer betydningen til setningene. Hva er meningen av setningen. World: En mulig verden (model) er et komplett sett av sannhetsverdiene til alle de logiske variablene. Entailment: Betyr at en ting følger fra en annen. KB |= a KB “entails” a KB er et subset av a. M(KB) M(a). Altså for hver verden hvor KB er true er også a true. Satisfiable: En setning er satisfiable dersom den er true i en eller annen model Valid: En setning er valid dersom den er true for alle modeller Number of models: Antallet modeller er antall modeller som er true. Horn Clauses: Alle variablene i en logisk setning er en negasjon, kun en av variablene kan trenger ikke ha negasjon forran seg. ## Standard logisk ekvivalens ()() communitivity of ()() communitivity of ())(()) associativity of ())(()) associativity of () double-negation elimination ()() contraposition ()( ) implication elimination ()(()() biconditional elimination ()() De Morgan ()() De Morgan (())(()() distributy of over (())(()() distributy of over CNF - Conjunction Normal Form Får det på form slik at det blir et produkt av summer. Eksempel:()()() Resolution: cancel out variable with negated variable. To do resolution first you have to get all your facts onto CNF and then take the negation of what you want to prove and cancel out facts based on what you know. When you can cancel out what you want to prove with what you can derive from what you know then you have solved the problem. It may happen that you derive facts that may be irrelevant to what you are trying to prove. # Kapittel 8 - First-Order Logic The world in first order logic contains: objects: people, houses, numbers... Relations: red, round, prime... Functions: father of, best friend... Universal Quantification(∀): For alle Existential Quantification(∃): Det finnes noen ∀x ¬P = ¬∃x P ∃x ¬P = ¬∀x P # Kapittel 9 - Inference in First-Order Logic Unification: Matching a free variable with a constant. θ = {x/John} Forward chaining: start with base facts and try to find out which facts fires which rule. Stop when you have reached the goal. Backward chaining: Start with the goal and work your way backward. Apply rule to the goal and use unification to bind variables to prove the goal. As we apply a rule we get subproblems and try to solve these. If we can solve the subproblems we can solve the whole problem. (Basicly is a depth first search). Conversion to CNF: Eliminate biconditionals and implications (⇒ and ⇔) Move ¬ inwards Standardized variables: each quantifier should use a different one Each existential variable is replaced by a Skolem function of the enclosing universally quantified variables. (F(x), G(x)...) Drop universal quantifiers Use laws to get it on CNF form - forward chaining in propositional logic (start at facs and apply rules) - backward chaining in propositional logic (start at goal and make subgoals) - resolution in propositional logic (negate goal and combine facts with rules) - forward chaining in first-order logic (same but with bindings) - backward chaining in first-order logic (same but with bindings) - resolution in first-order logic (same but with bindings) # Kapittel 10 - Classical Planning Plan: A plan is a collection of actions for performing some task ## STRIPS || Domain || a set of typed objects; usually represented as propositions || || States || are represented as first-order predicates over objects || || Closed-world assumption || everything not stated is false; the only objects in the world are the ones defined || || Operators/Actions || defined in terms of **preconditions**: when can the action be applied? **Effects:** what happens after the action || Effects are represented in terms of: || Add-list: || list of propositions that become true after action || || Delete-list: || list of propositions that become false after action || || Goals: || conjunction of literals || ### Example - bying action: #### PDDL PDDL (Planning Domain Definition Language) describes the four things we need to define a search problem: the initial state, the actions that are available in a state, the result of applying an action, and the goal test. PDDL accepts negative literals in preconditions and goals. ### Eksempel - bying action: #### Planning graph: Is a directed graph organized into levels: s0 represents the first level which is also the initial state of the graph. The initial state consists of node representing each fluent that holds in S0. The next level A0 consisting of nodes representing each fluent that holds in S0. Then alternating levels Si followed by Ai until we reach a termination condition. A persistence action take place if no actions negates it (small empty boxs in the graph). Mutural exclusion links are drawn between states when they are opposite of each other or when the states can not appear together regardless of the choice of action. Meaning that only one of them could be the result. If we get to a point in our graph where two consecutive levels are identical, then the graph has leveled off. ##### A mutex holds when: Inconsistent effects: one action negates an effect of the other. Interference: one of the effects of one action is the negation of a precondition of the other. Competing needs: one of the preconditions of one action is mutually exclusive with a precondition of the other ##### When a solution exist For there to exist a plan in the planning graph, the goal states must not be in mutex with each other at the last level. This is not an existence guarantee for a valid solution however, as any states or actions along the path from the start to the goal states must also not be in any mutex relation with each other. ##### How to find a solution To extract a solution, start at the level where the goal states are not in mutex with each other. Then search backwards (state search) to find a path where actions are not in mutex with each other. If one is able to arrive at the start state S0, a valid plan exist and that path can be extracted. # Kapittel 11 - Planning and Acting in the real World Critical path method: the path whose total duration is longest # Kapittel 12 - Knowledge representation ## Knowledge-based systems(KBS): Is a model of something in the real world (outside the agent). There are 3 main players of modeling: || Knowledge engineer || design,builds and tests the “expert system” || || Domain expert || possesses the skill and knowledge to find a solution || || End User || the final system should meet the needs of the end user. || The KB represent the knowledge using a KB language, which is a system for encoding knowledge. The inference engine has the ability to find implicit knowledge by reasoning over the explicit knowledge. Decides what kind of conclusions can be drawn. || Declarative knowledge || expressed in declarative sentences or indicative propositions. (knowinf of). || || Procedural knowledge || knowledge exercised in the performance of some task (shopping list). || || Domain knowledge || what we reason about || || Strategic knowledge || how we reason || ### 5 rules of knowledge reasoning: Surrogate: A representation is a substitute for direct interaction with the world. All representations are approximations to reality and they are invariably imperfect Fragmentary theory of Intelligent Reasoning Is a medium for efficient computation Is a medium of human expression Rule based systems (early KBs expert systems) Working memory: contains facts about the world, observed directly or derived from a rule. Rule base: contains rules, where each rule is a step in a problem solving process (if-then format) Interpreter: match rules and the current contents of the working memory. KR languages: Syntactic: possible allowed constructions Semantic: what the representation mean, mapping from sentence to world Inferential: interpreter, what conclusions can be drawn Requirements: Representation adequacy: Should allow for representing all the required knowledge Inferential adequacy: should allow inferring new knowledge Inferential efficiency: inferences should be efficient Clear syntax and semantics Naturalness: easy to read and use ### Semantic networks: A semantic net is a structure that shows the relation between concepts, instances and values. The concepts can be categories and sets of entities ("bunches"). The relations can be memberships, subclasses and attributes or others. Semantic networks store our knowledge in the form of a graph, with nodes representing objects in the world, and arcs representing relationships between those objects. It uses the term inheritance which is used when an object belong to a class and hence inherits all the properties of that class. Semantic networks can be translated to frames. Nodes then become frame names, links become slot and the node at the other end becomes the slot value. Frames is a collection of attributes (slots) and associated values and constraints on those values. (F stands for false, and T stands for True in the image) #### Arv i semantiske nett Inheritance of properties are done following the principles: - If a category has an attribute, then all subcategories have that attribute. - If a category has a poperty (e.g. attribute and value), then all subcategories and instances have that property. The exception is when a semantic entity inherits a property or attribute from several superclasses. Then the following apply: - In a hierarchy (one parent for each semantic entity), it is the closest property that is valid. - In a heterarchy ( different parents along different paths), categories blocked by interfering inheritance are excluded from inheritance. # Kapittel 22 - Natural Language Processing ## Information Retrieval Finding documents that are relevant to the user’s need for information. ### Setting source (collection of documents), input (query of what the user wants) , output (result of query) ### By boolean keyword chances for hit and miss, can’t rank for relevancy, hard to use for “normal” people. ### Modern ir based on statistics, ranked by relevancy, need to sample out word that are used alot (stop words), can use inverse document frequency - to give score to the documents if the word you are searching for is to be found in all documents you get a score of 0. Queries can be evaluated to be relevant or irrelevant. Precision/recall? can use F-socre to get a good result: 2*Pres * rec/(prec +rec), ### Information Extraction the task of automatically extracting structured information from unstructured and/or semistructured machine-readable documents. Matching regular expressions to text allows extraction. Regular expressions correspond to finite-state machine. (FSM). ### Text Categorization, Sentiment Analysis Extraction contains selected sentences from original text, while abstract rewrites and combines sentences into new text. Single documents summarization concern one document, while multi document summarization concerns collection of similar documents. Text-to-speech synthesis is the task of converting written text to speech.