12 posts tagged with "iai"

Structural Knowledge​

• Structural knowledge: the relationship between concepts and objects in the world.
• Hierarchical approach: built on classification and uses hierarchies as the structures for knowledge representation, presented in a graphical format.
  • Semantic networks: nodes represent concepts, and edges represent relationships between concepts.
  • Ontologies
    • A formal specification of concepts, relationships, and constraints within a domain that enables machines to reason automatically.
    • It defines classes (concepts), subclasses (hierarchical relations), and properties (attributes or relations) that describe how entities interact.
    • Unlike simple taxonomies, ontologies also include logical axioms and constraints that specify allowable relationships and permit inference and consistency checking through automated reasoning.
    • Classes: Main concepts or categories (e.g. Person, Animal).
    • Subclasses: Subcategories (e.g. Dog ⊂ Animal).
    • Properties: Attributes (e.g. hasPart, hasColor).
    • Relations: Connection rules (e.g. MemberOf, SubsetOf).
    • Constraints: Logical constraints (e.g. disjointness, transitivity) that enable inference.

Requirement of hierarchices​

• Inclusiveness: Dog ⊆ Mammal ⊆ Animal
• Species/differentia: Dog = Mammal + (barks, canine traits, etc.)
• Inheritance: Mammal: has_fur, gives_live_birth → Dog: inherits all Mammal properties
• Transitivity: If Dog ⊆ Mammal and Mammal ⊆ Animal, then Dog ⊆ Animal
• Systematic and predictable rules for association and distinction
• Mutual exclusivity: Reptile ∩ Mammal = ∅
• Necessary and sfficient criteria:
  • Necessary: $\forall x,\ \text{Mammal}(x) \Rightarrow \text{Vertebrate}(x) \land \text{ProducesMilk}(x)$
  • Sufficient: $\forall x,\ \text{Vertebrate}(x) \land \text{ProducesMilk}(x) \Rightarrow \text{Mammal}(x)$

Advantage of hierarchical approach​

• Inferring from incomplete evidence (if the shared criteria are not obvious or easily observable).
  • Animal → Mammal → Dog: If an entity is classified as a Mammal, we can infer properties such as having fur and giving live birth, even if the entity is not explicitly identified as a Dog.
• Excellent representations in mature domains
  • Domains where entities and relationships are well understood and stable
  • e.g. medical diagnosis, biological taxonomy, type systems in programming languages.
• Useful for entities that are well defined and have clear class boudnaries.
  • Good fit: HTTP status codes, chemical elements, and biological species
  • Poor fit: emotions, social roles, and cultural practices
• Some theory or model is necessary to guide the identification
  • Provides criteria for defining entities and relationships
  • e.g. Evolutionary theory in biological taxonomy, Type theory in programming languages

Partition​

A partition of a category is a set of subcategories that form a disjoint, exhaustive composition of that category.

• Disjoint: Two or more categories are disjoint if they don't share common members.
• Exhaustive composition: The subcategories together cover all members of the parent category, leaving no member unclassified.
• Examples:
  • ❌ Category: Animal (Not a partition)
    • Mammal, Bird (Reptiles, fish, insects are missing, not exhaustive)
  • ✅ Category: Integer (Partition)
    • Even, Odd (Disjoint and exhaustive)

Physical composition​

• PartOf Relation: Partof(a, b) is a relation representing that one thing, 'a', is a part of another thing, 'b'.
• BunchOf Relation: BunchOf(a) is a relation, taking a set of objects 'a', to represent a composite object made up of those parts.
• Examples:
  • Partof(Wheel, Car): A wheel is part of a car (one-to-one relation).
  • BunchOf({Wheel1, Wheel2, Wheel3, Wheel4}): A car is a bunch of four wheels (many-to-one relation).
• Link between PartOf and BunchOf:
  • $\forall x (x \in s \implies PartOf(x, BunchOf(s)))$
  • $\forall y \Big[\big(\forall x (x \in s \implies PartOf(x, y)\big) \implies PartOf(BunchOf(s), y)\Big]$
• Why useful?
  • Reasoning from individual parts -> group -> larger object.
  • Avoiding ambiguity between: "this thing is part of", "these things together form"
  • Without BunchOf, ontologies cannot represent: piles, colleciton, aggregates, composite physical structures.

Measurements​

• Quantitive measures (Ratio, Interval)
  • Represented as numbers with units
  • Support arithmetic and unit conversion
  • Enable numeric reasoing (e.g. 2.54cm = 1 inch)
• Non-quantitative measures (Ordinal)
  • Cannot be meaningufully represented as numbers
  • Can still be compared using ordering relactions (<, >, =)
  • Suppor qualitative reasoning (e.g. one task is more difficult than another)

Objects​

• Stuff
  • Represents substances
  • Uncountable masses
  • Definitions include only intrinsic properties (e.g. Butter, Unsalted Butter)
  • $b \in Butter \land PartOf(p, b) \implies p \in Butter$
• Things
  • Represents discrete objects
  • Countable entities
  • Definitions include extrinsic properties (e.g. PoundOfButter, StickOfButter)
    • It depends on measurement
    • It depends on contextual constraints

Time​

• Fluent: a condition whose truth value can change over time.
  • e.g. "The box is on the table", $On(box, table)$, $On(box, table, t)$
  • a time-dependent proposition.
• Time scale and absolute time
  • Ontology represents time along a single continuous timeline with a fixed reference point.
  • $Date(0, 20, 21, 24, 1, 1995) = Seconds(300000000)$
  • It allows arithmetic operations on time and comparisons between time points.
• Time intertvals
  • Time can be represented as moments (instants) or intervals (durations).
  • $Duration(i) = Time(End(i)) - Time(Start(i))$
• Partition of time
  • $Partition({Moments, ExtendedIntervals}, Intervals)$
  • All time intervals can be partitioned into moments and extended (non-zero-length) intervals.
  • It provides a complete and precise ontology of time.

Event calculus​

• $T(f, t_1, t_2)$: Fluent $f$ is true for all time between time $t_1$ and $t_2$.
• $Happens(e, t_1, t_2)$: Event $e$ start at time $t_1$ and ends at time $t_2$.
• $Initiate(e, f, t)$: Event $e$ causes fluent $f$ to become true at time $t$.
• $Terminates(e, f, t)$: Event $e$ causes fluent $f$ to cease to be true at time $t$.
• $Initiated(f, t_1, t_2)$: Fluent $f$ becomes true at some point between $t_1$ and $t_2$.
• $Terminated(f, t_1, t_2)$: Fluent $f$ ceases to be true at some point between $t_1$ and $t_2$.
• $t_1 < t_2$: Time point $t_1$ occurs before time point $t_2$.
• Happens(PutBoxOnTable, 10, 12)
• Initiate(PutBoxOnTable, On(Box, Table), 12)
  • Initiated(On(box, table), 10, 12)
• T(On(Box, Table), 12, 20)
• Terminates(RemoveBoxFromTable, On(Box, Table), 20)
  • Terminated(On(box, table), 18, 22)

Successor-state axiom​

후속상태공리

• Define how the world changes after an action occurs.
  • what changes when an action happens
  • what stays the same.
• Without successor-state axioms, we face the frame problem:
  • after every action, we would need to explicitly list all facts that did not change.
• $Move(A, B, X)$: moving block A from the top of block B to position X.
  • Preconditions:
    • $On(A, B)$: A is on top of B
    • $Clear(A)$: nothing is on top of A
    • $Clear(X)$: nothing is on position X
  • Effects:
    • $On(A, X)$: A is now on position X
    • $Clear(B)$: B is now clear
    • $Clear(X)$: X is no longer clear (X is now occupied by A)

Semantic networks​

• Visually represent a knowledge base.
• Support efficient inference.
• Allow properties of an object ot be inferred from its category membership.
• Representing individual objects, categories of objects, and relations among objects.
• Categories are the primary buildling blokcs of large-scale knowledge representation schemes.

Taxonomy hierarchy​

• A hierarchical structure of categories
• Each lower category is a more specific kind of its parent
• Organized from general → specific

University Ontology​

Knowledge graph​

• represents information and its relationships using a graph structure.
• Nodes: entities or concepts (e.g. people, places, things).
• Edges: relationships between nodes (e.g. "is a", "part of", "located in").

Types of Knowledge Graphs​

• General Knowledge Graphs
• Domain-Specific Knowledge Graphs
• Semantic Knowledge Graphs
• Social Knowledge Graphs
• Temporal Knowledge Graphs
• Special Knowledge Graphs
• Statistical Knowledge Graphs
• Probabilistic Knowledge Graphs
• Textual Knowledge Graphs
• Multi-modal Knowledge Graphs

General Knowledge Graphs​

• Comprehensive information representation
• Entity-Relationship Structure
• Linked Data
• Semantic Enrichment
• Capabilities & Use Cases
  • Querying and Analysis
  • Data Integration
  • ML and AI applications

Examples​

• DBPedia: RDF, resource descritions framework
• Wikidata
• YAGO
• Google Knowledge Graph
• Microsoft Academic Graph
• IBM Watson Knowledge Studio

Reasoning for categories​

• Infer the presence of certain objects from perceptual input
• Infer category membership from perceived properties
• Use category information to make predictions
• It enables an agent to identify objects from observed properties and to predict further characteristics using category knowledge.

Reasoning using Semantic networks​

• Semantic networks are:
  • systems designed specifically for organizing categories reasoning with categories.
  • Provide graphical representations of a knowledge base
• Using a semanctic network, reasoning can be performed based on:
  • relationships between objects
  • category membership
  • inheritance between categories
  • properties associated with categories
  • Allows an object to inherit general knowledge from its category.
• The inheritance algorithm:
  • Starts from the object itself
  • Follows links upwards through the category hierarchy
  • Stops as soon as it finds a value for the property
  • This suppors efficient reasoning, default values, and exception handling.

RDF​

Resource Description Framework (RDF)

• Triple Structure: subject -> predicate -> object
• Subject: represents the resource being described or identified by a URI.
• Predicate (or Property): desribes the relationship between the subject and the object. also represented by a URI.
• Object: represents the value or target of the relationship. It can be a URI or a literal (a string, number, or date).

Uncertain Domain​

• Agent may need to handle uncertainty
• Environment is partially observable
  • Fully observable: An agent knows where it is.
  • The drone never knows its exact position, only an estimated one.
  • The true user intent is not directly observable, only noisy speech data.
  • It cannot see the whole environment or detect humans perfectly.
  • The true health state (disease present or not) is hidden.
• Environment is non-deterministic
  • AI Trading Agent
    • even if the agent takes the same action, the outcome can vary dramatically.
    • from market prices changes unpredictably due to external events (news, other traders, economic data).
    • network latency, competing traders' behavior are stochasic and independent, random fluctuations can affect the outcome.
    • buy action could lead to profit, loss, or no change depending on uncontrollable external factors.
  • AI Helpdesk Chatbot
    • even when the chatbot executes the same action, it sends queries to multiple backend systems, the result may differ each time.
    • network latency or failures, backend load, concurrent requests, and external dependencies can lead to different response times or outcomes.
    • same command doesn't guarantee the same outcome.
• Autonomous Driving
  • Partial Observability
    • Sensors cannot detect everything, blind spots, weather effects, occluded vehicles.
  • Non-Determinism
    • Even if the car signals a turn and starts moving, other drivers might brake suddenly, pedestrians might cross unexpectedly, or traffic lights might malfunction.
    • depending on random external events.
• Medical Diagnosis & Treatment Assistant
  • Partial Observability
    • The patient's internal health state is not directly visible.
    • tests can be inaccurate or incomplete: false positives/negatives, missing data
  • Non-Determinism
    • The same treatment can have different effects on different patients due to genetics, lifestyle, or random biological responses.
    • A drug may succeed, fail, or cause side effects.

Bayes' Theorem​

$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$

• $P(A|B)$: Posterior probability, the probability of event A given taht B has occurred.
• $P(B|A)$: Likelihood, the probability of event B occurring given that A is true.
• $P(A)$: Prior probability, the initial probability of A being true before considering B.
• $P(B)$: Evidence, the total probability of B occurring.
• examples
  • 1% of people have a certain disease (prior probability). $P(Disease) = 0.01$
  • the test for the disease is 99% accurate (likelihood).
    • $P(PositiveTest|Disease) = 0.99$
    • $P(NegativeTest|NoDisease) = 0.99$
    • so $P(PositiveTest|NoDisease) = 0.01$
  • $P(PositiveTest) = P(PositiveTest|Disease) \cdot P(Disease) + P(PositiveTest|NoDisease) \cdot P(NoDisease)$
    • $= 0.99 \cdot 0.01 + 0.01 \cdot 0.99 = 0.0198$
  • $P(Disease|PositiveTest) = \frac{P(PositiveTest|Disease) \cdot P(Disease)}{P(PositiveTest)}$
    • $= \frac{0.99 \cdot 0.01}{0.0198} \approx 0.5$
• the conditional probability $P(effect|cause)$ quantifies the relationship in the causal direction from cause to effect.
• but $P(cause|effect)$ is often what we really want to know, describing the relationship in the diagnostic direction from effect to cause.
  • In medical dignosis, the doctor knows $P(symptoms|disease)$ from medical studies, and want to derive a $P(disease|symptoms)$ for a particular patient.
  • $P(disease|symptoms) = \frac{P(symptoms|disease) \cdot P(disease)}{P(symptoms)}$

General Form of Bayes' Rule​

$P(Y|X) = \alpha \cdot P(X|Y) \cdot P(Y)$

• $\alpha$ is the normalization constant needed to make the entries in $P(Y|X)$ sum to 1 for each value of X.
• conditional independency
  • two variables X and Y are conditionally independent given a third variable Z if the value of X provides no information about Y once Z is known.
  • $P(X, Y|Z) = P(X|Z) \cdot P(Y|Z)$

Constructing Bayesian Network​

• constructing a Bayesian network in which resulting joint probability distributions are a good representation of the agent's knowledge.
• 1. $P(x_1, ..., x_n) = \prod_{i=1}^{n} P(x_i | \text{parents}(x_i))$
• 2. rewrite the entries in the joint probability distribution in terms of conditional probabilities using the product rule.
  • $P(x_1 \land ... \land x_n) = P(x_n | x_{n-1} \land ... \land x_{1}) \cdot P(x_{n-1} \land ... \land x_{1})$
• 3. repeat step 2 until all variables are included.
  • $P(x_1, ..., x_n) = P(x_n | x_{n-1} \land ... \land x_{1}) \cdot P(x_{n-1} | x_{n-2} \land ... \land x_{1}) \cdots P(x_2 | x_1) \cdot P(x_1)$

Knowledge Representation​

• The agent's knowledge can at best provide only a degree of belief in the relevant logical sentences.
• A probabilistic agent may have a numerical degree of belief between 0 and 1.

Bayesian Network​

• a directed graph
• each node repressents a random variable and edge with an arrow from X to Y represents that X is a parent of Y.
• each node is associated with a probability distribution
• if a node Y has parents X, the Y node has a conditional probability distribution with respect to its parents X, i.e. $P(Y| \text{parents}(Y))$
• if a node has no any parents, it has an unconditional probability distribution.

Burglary Example​

• a new burglar alarm installed at home.
• it is reliable at detecting a burglary, but also responds on occasion to minor earthquakes
• you have two neighbors, John and Mary who promised to call you at work when they hear the alarm.
• given the evidence of who has or has not called, estimate the probability of a burglary.
• Knowledge representation as the probability of each event that can occur in this case.

$P(\text{event}_{j}) = \frac{\text{number of ccurrences of event }_j}{\text{total number of experiments}}$

• calulate the full joint probability distribution for all relevant variables.
  • specifying probabilities for all possible events one by one is unnatural and tedious.

$P(B, E, A, J, M) = \prod_{i}^{5} P(X_i | \text{parents}(X_i)) = P(B) \cdot P(E) \cdot P(A|B,E) \cdot P(J|A) \cdot P(M|A)$

$P(M, J, A, E, B) = P(B) \cdot P(E) \cdot P(A|B,E) \cdot P(J|A) \cdot P(M|A)$

Probabilistic reasnoing​

• to explain how to use network models to reason under uncertainty.
• Exact inference: calculate the exact posterior probabilities.
• Approximate inference: Stochastic approximation techniques such as likelihood weighting and Markov Chain Monte Carlo
  • can give reasonable estimates of the true posterior probabilities in a network
  • can cope with much larger networks than exact inference algorithms.
• Static worlds: Each random variable has a single fixed value.
• Dynamic worlds: view the world as a series of snapshots, or time slices.
  • Each of snapshots contains a set of random variables, some observed and some hidden.
  • The values of these variables can change over time.
  • With the assumption of state sequences are Markov, the future is independent of the past given the present.

Inference in Bayesian Networks​

• Computing the posterior probability distribution of a set of query variables, given some observed events, called some assignment of values to a set of evidence variables.
• $X$: query variable(s)
  • is it raining?
• $E$: the set of evidence variables with observed values $E_{1}, ..., E_{m}$
  • weather report says it is cloudy.
  • weather report says there is high humidity.
• $e$: a particular observed event.
  • $E_{1} = \text{cloudy}$
  • $E_{2} = \text{high humidity}$
• $Y$: the non-evidence, non-query variables.
  • the other variables in the network.
• $X = \{X\} \cup E \cup Y$
  • the complete set of variables in the network.
• $P(X|e)$: the posterior probability distribution of the query variable(s) given the evidence.
• $P(X|e) = \alpha \sum_{y} P(X, e, y)$

Exact inference in Bayesian Networks​

• One exact inference method is called by inference by enumeration.
• Observed some event $A = true$ and $B = true$, want to compute the posterior probability distribution $P(C|A, B)$.
  • Use the full conditional probability table
  • Use the Bayesian Network
• It calculates all the required probability components in each branch in the evaluation tree, and this results in repetitive calculations.
• To avoid this, we can use variable elimination algorithm and clustering algorithms.
• Calculation of probability distribution for a query variable is complexity exponential.
• Enumeration method can become intractable in large, multiple connected networks. -> use approximate inference methods.

For any Bayesian network with given nodes, $X = \{X_1, X_2, ..., X_n\}$, the joint probability distribution is given by: $P(X) = P(X_1 \land X_2 \land \ldots \land X_n) = \prod_{i=1}^{n} P(X_i | \text{parents}(X_i))$

Using the Bayesian network, we can compute the conditional probability.

$P(B | event) = \alpha \sum_{e}\sum_{a} P(B, E, A, j, m)$

• $i=1, P(X_1 | \text{parents}(X_1)) = P(B)$
• $i=2, P(X_2 | \text{parents}(X_2)) = P(E)$
• $i=3, P(X_3 | \text{parents}(X_3)) = P(A|B,E)$
• $i=4, P(X_4 | \text{parents}(X_4)) = P(j|A)$
• $i=5, P(X_5 | \text{parents}(X_5)) = P(m|A)$
• $P(B, E, A, j, m) = P(B) \cdot P(E) \cdot P(A|B,E) \cdot P(j|A) \cdot P(m|A)$

Berglary example calculation:

Knowledge representation​

• Intelligent agents need knowledge about the world in order to reach good decisions.
• Declarative knowledge is represented in a form of sentences in a knowledge representation language and stored in a knowledge base.
• Knowledge base is used by an inference engine to infer a new sentence which will be used for the agent to decide what action to take next.
• Formal languages are defined by its grammar and semantic rules
  • grammar: defines the syntax of legal sentences
  • semantic rules: defines the meaning.
• Common knowledge representation formalisms:
  • Propositional logic
  • First-order logic
  • Fuzzy logic
  • Semantic networks
  • Ontologies

Propositional logic​

• a declarative language in which can handle propositions that are known true, known false, or completely (unknown true or false)
• a BNK (Backus-Naur Form) grammer of sentences in propositional logic.
  • $\neg$ = NOT
  • $\land$ = AND
  • $\lor$ = OR
  • $\implies$ = IMPLIES
  • $\iff$ = IF AND ONLY IF
• Negation: a sentence using $\neg$ is called negation
• Literal: either an atomic sentence or a negated atomic sentence
• Conjunction: two sentences connected by $\land$. Eac hof them is called conjunct
• Disjunction: two sentences connected by $\lor$. Each of them is called disjunct
• Implication: two sentences connected by $\implies$. $P \implies Q$. P is called premise or antecedent and Q is the conclusion or consequent.
  • An implication is if-then statement.

Truth tables

FOL, First-order logic​

• a declarative language
• Syntax of FOL builds on that of propositional logic
• terms to represent objects, universal quantifier, and existential quantifier
• a model in FOL must provide the information required to determine the truth value of every atomic sentence in the language.
• $\forall x P(x)$ means for all x, P(x) is true
• $\exists x P(x)$ means there exists an x such that P(x) is true

Logical equivalence​

$\forall x \neg P(x) \equiv \neg \exists x P(x)$

• For all x, not P(x) is logically equivalent to "it is not the case that there exists an x such that P(x) is true."

Reasoning​

Deductive reasoning​

• a process of reasoning from one or more statements (premises) to reach a logical conclusion.
• first premise, second premise, therefore conclusion.

Inductive reasoning​

• the process of resoning from specific observations to borader generalizations and theories.
• also described as a method where one's experiences and observations are synthesized to cmoe up with a general truth.
• premises and then conclusion

Inference​

• steps in reasoning
• moves from premises to logical consequences
• In AI Context, inference is to derive new logical sentences (as the conclusion) from existing logical sentences (as premises).
• researchers develop automated inference systems to emulate human inference.

Inference Problem​

$KB \models \gamma$

• KB, Knowledge Base, is a set of propositions that represent what is known about the world.
• $\gamma$, Query sentence, is the target conclusion which needs to be confirmed based on the given KB.
• where $\models$ denotes the relation of logical entailment between KB and the sentence $\gamma$, reading as "KB entails $\gamma$" or "if KB is true, then $\gamma$ must also be true".
• $\alpha \models \beta \iff M(\alpha) \subseteq M(\beta)$
  • $M(\alpha)$ is the set of all models that satisfy $\alpha$.
  • $M(\beta)$ is the set of all models that satisfy $\beta$.
  • The statement $\alpha \models \beta$ means that in every model where $\alpha$ is true, $\beta$ is also true. In other words, if $\alpha$ holds, then $\beta$ must also hold.
• Model Checking: enumerates all possible models and checks if the entailment holds in each model.
  • Knowledge base will be used to draw inferences.
  • Query sentence, $\gamma$, is needed to be checked whether it is entailed by the KB.
  • Symbols, a list of all symbols (or atomic propositions) used in the problem context.
  • Models, assignments of truth and false values to those identified symbols.
• Model Checking Procedure
  1. Identify the propositional symbols involved in the KB sentences and query sentence
  2. Enumerate all possible models by assigning truth values to the identified symbols.
  3. Evaluate the KB sentence in each model and fined the models in which KB is true.
  4. Evaluate the query sentence in the models from step 3 and check if query sentence is true in these models.
  5. Conclude that the KB entails the query sentence $\gamma$ if and only if the query sentence is true in all models where the KB is true.

Inference Problem Example​

• Obersvation P: "It is raining"
• Query sentence Q: "The ground is wet"
• Knowledge: $P \implies Q$ (If it is raining, then the ground is wet)
• Knowledge Base KB: $P \land (P \implies Q)$
• Inference Problem: $KB \models Q$ from KB=T, get Q=T
• Proof:
  1. From the 4 possible models, only Model 1 makes KB true.
  2. M(KB) = model 1
  3. Model 1 also makes Q true.
  4. M(Q) = model 1
  5. $M(KB) \subseteq M(Q)$, therefore $KB \models Q$

Inference by theorem proving​

to apply rules of inference directly to the sentences in the KB to construct a proof of the desired sentence without consulting models.

• Proof: a chain of consequences that leads to the desired goal.
• KB will be used to draw inferences.
• Desired sentence is needed to be checked whether it is entailed by the KB.
• The rules of inference are the approved logical equivalences and rules.

Modus Ponens Rule​

$\frac{\alpha \implies \beta, \alpha}{\therefore \beta}$

• whenever any sentences of the form $\alpha \implies \beta$ and $\alpha$ are given, then the sentence $\beta$ can be inferred.

Add-Elimination Rule​

$\frac{\alpha \land \beta}{\therefore \alpha}$

• from a conjunction, one of the conjuncts can be inferred.

Terms to contradiction and resolution​

CNF
┌────────────────────────────────────────────────┐
│            (P ∨ Q)         ∧    (¬Q ∨ R)       │
│   ┌──────────────────────┐   ┌───────────────┐ │
│   │  Clause 1            │   │  Clause 2     │ │
│   │  (P ∨ Q)             │   │  (¬Q ∨ R)     │ │
│   │  ┌───────┬───────┐   │   │  ┌──────┬─────┐ │
│   │  │  P    │   Q   │   │   │  │ ¬Q   │  R  │ │
│   │  └───────┴───────┘   │   │  └──────┴─────┘ │
│   └──────────────────────┘   └───────────────┘ │
└────────────────────────────────────────────────┘

• Literal: an atomic sentence or its negation
• Complementary literals: a literal and its negation are complementary literals
• Clause: an expression formed from a collection of finite literals
  • In most $l_1 \lor l_2 \lor ... \lor l_n$ cases, a clause is a disjunction of finite literals.
  • written as the symbol $l_i$.
• Conjunctive Normal Form: a sentence expressed as a conjunction of clauses.
• Satisfiability: a sentence is satisfiable if it is true in, or satisfied by, some models.

Propositional satisfiability (SAT) problem​

• to determine the satisfiability of sentences in propositional logic.
• if there exists a model that satisfies a given logical sentence, then the sentence is satisfiable.
• Satisfiability can be checked by enumerating the possible models until one is found that satisfies the sentence, or by resolving complementary literals until an empty clause is derived.
• many problems in CS are really SAT problems.

Resolution rule​

Unit resolution rule​

$\frac{(l_1 \lor l_2 \lor ... \lor l_{i-1} \lor l_i \lor l_{i+1} \lor ... \lor l_k,\space m)}{l_1 \lor ... \lor l_{i-1} \lor l_{i+1} \lor ... \lor l_k}$

• where $l$ is a literal and $l_i$ and $m$ are complementary literals.
• Unit resolution rule takes a clause which is a disjunction of literals, and a literal and produces a new clause as the resolvent.

Full resolution rule​

$\frac{(l_1 \lor l_2 \lor ... \lor l_{i-1} \lor l_i \lor l_{i+1} \lor ... \lor l_k,\space m_1 \lor m_2 \lor ... \lor m_{j-1} \lor m_j \lor m_{j+1} \lor ... \lor m_n)}{(l_1 \lor ... \lor l_{i-1} \lor l_{i+1} \lor ... \lor l_k \lor m_1 \lor ... \lor m_{j-1} \lor m_{j+1} \lor ... \lor m_n)}$

• where $l$ is a literal and $l_i$ and $m_j$ are complementary literals.
• Full resolution rule takes two clauses which are disjuctions of literals and produces a new clause containing all the literals of the two original clauses except for the two complementary literals.

Inference via proof by contradiction through resolution​

$\alpha \models \beta$

• to prove that $\alpha \models \beta$, we can show that the sentence $\alpha \land \neg \beta$ is unsatisfiable.
• by deriving an empty clause $()$ from $\alpha \land \neg \beta$ using the resolution rule.
• In order to derive an empty clause, we use resolution which is a process to resolve complementary literals until to find an empty clause.
  1. R1: P (observation)
  2. R2: P $\implies$ Q (knowledge, raining implies ground is wet)
  3. $KB = P \land (P \implies Q)$
  4. Query sentence: Q
  5. Inference problem: $KB \models Q$, i.e. from $KB=T$, get $Q=T$
  6. Proof:
  • Let $(P \land (P \implies Q)) \land \neg Q$ valid
  • Convert $(P \land (P \implies Q)) \land \neg Q$ to CNF
  • Apply implication elimination rule, one has $(P \land (\neg P \lor Q)) \land \neg Q$
    • $C_1: P$
    • $C_2: \neg P \lor Q$
    • $C_3: \neg Q$
  • Apply unit resolution rule to $C_1$ and $C_2$, resolve $P$ and $\neg P$, one has $C_4: Q$
  • Apply unit resolution rule to $C_3$ and $C_4$, resolve $Q$ and $\neg Q$, one has $C_5: ()$

Inference in FOL​

• convert the first-order inference to propositional inference using the ruls for quantifiers.
  • universal instantiation (UI)
  • existential instantiation (EI)
• do inference in propositional logic using the methods about inference in propositional logic.
• this approach to first-order logic inference via propositionalization is complete, means any entailed sentences can be proved.
  • in most cases, this approach works
  • in some cases, it is slow and only useful when the domain is small.
• get rid of quantifiers by instantiating them with specific constants or variables.

Universal instantiation (UI)​

$\frac{\forall v \space \alpha}{\text{Subst}(\{v/g\},\alpha)}$

• to convert sentences with universal quantifiers to sentences without universal quantifiers.
• it can infer any sentence obtained by substituting a ground term for the universally quantified variable.
• $Subst(\{\theta, \alpha\})$ denotes the result of applying the subsitution $\theta$ to the sentence $\alpha$ and $g$ is a ground term or a constant symbol.
• universal instantiation can be applied many times to produce may different consequences.
• $\forall x Loves(x, Mary)$
  • $Loves(John, Mary)$
  • $Loves(Sue, Mary)$
  • $Loves(Bill, Mary)$
  • ...

Existential instantiation (EI)​

• to convert sentences with existential quantifiers to sentences without existential quantifiers.
• the quantified variable can be replaced by a single new constant symbol.
• for any sentence $\alpha$, variable $v$, and constant symbol $k$ not appear elsewhere in the knowldge base, the following rule is sound: $\frac{\exists v \space \alpha}{\text{Subst}(\{v/k\},\alpha)}$
• $\text{Subst}\{\theta, \alpha\}$ denotes the result of applying the subsitiution $\theta={v/k}$ in the sentence $\alpha$ and $k$ is ground term or a new constant symbol.
• Existential instantiation can be applied only once, and then the existentially quantified sentence can be discarded.
• $\exists x Loves(x, Mary)$
  • $Loves(K, Mary)$
  • where $K$ is a new constant symbol not appear elsewhere in the knowledge base

CNF, Conjunctive Normal Form​

Generative AI​

• Gen AI refers to a category of AI models designed to generte new content, synt99hetic data that resembles a given dataset.
• Gen AI models create new content, including text, images, audio, and video.

Historcal context of Gen AI​

• 1980s: The development of statistical approaches to AI emerged, focusing on probabilistic models
• 1990s: Hidden Markov Models (HMMs) became popular in speech recognition and sequence generation tasks, making a shift towards using statistical methods in generative processes.
• 1990s-2000s: The resurgence of Neural Networks, with the introduction of deep learning techniques. However, hardware and data limitations hampered progress.
• 2010s: The advent of deep learning algorithms, especially convolutional neural networks (CNNs) and recurrent neural networks (RNNs), transformed the landscape of AI.
• 2013: VAEs were introduced, providing a probabilistic approach to data generation, allowing for smooth latent space interpolation and structure.
• 2014: GANs, a novel framework where two neural networks (a generator and a discriminator) are trained simultaneously, allowing for the generation of highly realistic images and other data types.
• 2015-2020: Generative models began to find applications beyond image synthesis, including text generation, music composition, and even video generation. OpenAI's GPT-2 showcased the potential of transformer-based models for generating coherent text.
• 2020s: The introduction of larger and more capable models like OpenAI's GPT-3 and subsequent iterations revolutionized natural language processing.
  • DALL-E and Stable Diffusion pushed the boundaries of image generation, allowing users to create images from textual descriptions. This sparked creative exploration and practical applications in marketing, art, and design.
• Present: The integration of multiple data modalities (text, image, audio) led to the development of models like CLIP and GPT-4, which can understand and generate content across different formats, enhancing the versatility of generative AI.

Variational Autoencoders, VAEs​

• VAEs are from the probabilistic approach to build a generative AI model
• VAE learns a latent distribution instead of a fixed latent presentation, allowing for the generation of new samples.
• Latent space
  • sample from a Gaussian distribution
  • $\mu$ and $\sigma$ are learned during training
  • $z$ is a new sample from the latent space
• $q_\phi(z|x)$ is the encoder that maps input data $x$ to a distribution over the latent space $z$
• $p_\theta(x|z)$ is the decoder that maps a latent variable $z$ back to the data space $x$
• During training, the model optimizes the reconstruction loss and a regularization term (KL divergence) to ensure the learned latent distribution is close to a prior distribution (usually a standard normal distribution).
• Latent Representation
  • Dimensionality Reduction: latent space is typically lower-dimensional than the input space
  • Smoothness: In a well-structured latent space, similar inputs will be represented by nearby points.
  • Generative Capabilities: Once trained, can sample from the latent space to generate new data that resembles the training set.
  • Regularization: The VAE incorporates a regularization term in its loss function (KL divergence), which encourages the lerned latent distribution to be close to a standard normal distribution.
• Decoder
  • The decoder takes the sampled latent representation $z$ and reconstructs the original input data.
  • The goal is to make the reconstructed data as close as possible to the original input.

VAE Examples​

Face Generation Example​

• Trains a VAE on face photos.
• Latent space learns meaningful features (e.g. hair color, glasses, smile)
• By sampling and interpolating in latent space, can generate new faces or smoothly morph one face into another.

Anomaly Detection Example​

• Train a VAE on normal sensor data.
• When fed unusual data, reconstruction error will be high.
• Use this for fault detection in machines, fraud detction, etc.

Autoencoder​

• Encoder
  • Input Layer: takes in the original data
  • Hidden Layer: These layers progrssively reduce the dimensionality of the input through operations like linear transformations and non-linear activations. (e.g., ReLU-Rectified Linear Unit)
  • Ouput Layer: Produces the final latent represntation. Sometimes Sigmoid or Tanh are used depending on the nature of the input data.
  • Learns to capture meaningful patterns in the data by minimizaing reconstruction loss, which mesures the difference between the original input and the reconstructed output produced by the decoder.
• Decoder
  • typically mirrors the structure of the encoder but in reverse.
  • During trainng, Mean squared Error (MSE) for continuous data or Binary Cross-Entropy (BCE) for binary data are commonly used to quantify the reconstruction loss.

Image Reconstuction Example​

• input: 28x28 pixel
• encoder: compresses it to just 16 numbers (latent vector)
• decoder: expands those 16 numbers back into a 28x28 image
• result: the reconstructed digit looks similar to the original but not in the training set.

Denoising Images​

• input: a noisy photo of a cat
• encoder: learns to ignore the noise and compress meaningful features.
• decoder: rebuilds the image without the noise.
• output: a clearer cat image.

Loss function​

• Reconstruction loss: Ensure output similar to input
• KL divergence loss: Push the learned distribution to be close to a standard normal distribution. (can sample new data)

Generative Adversarial Network, GAN​

• Generator: Learns to generate fake (generated) data that resembles data distribution.
• Discriminator: Learns to distinguish between real data and data generated by the Generator.
• Steps
  1. Generator creates fake data samples fro mrandom input (noise).
  2. Discriminator evaludates these samples together with real data samples.
  3. Discriminator outputs probabilities indicatcing whether each sample is real or fake.
  4. Based on the prediction of the Discriminator, the Generator and Discriminator are updated using specific loss functions.
• Applications
  • Labels to Street Scenes
  • Labels to Facade
  • BW to Color
  • Aerial to Map
  • Day to Nihght
  • Edges to Photo
  • Text-to-Image Synthesis

Autoregressive Models​

• a class of generative models where the current value of a time series is expressed as a linear function of its own past values plus some noise.
• foundational in generative AI and widely used in generative AI, particularly for tasks like text generation, speech synthesis.
• Examples
  • GPT series: state-of-the-art autoregressive language models used for text generation.
  • WaveNet: an autoregressive model for generating high-quality audio by predicting each sample conditioned on previous samples.

Training Autoregressive Models​

• Pretraining
  • the model sees sequences of tokens and learns to guess the next token.
  • objective: minimize cross-entropy loss between its guess and the true next token.
  • this teaches grammar, facts, reasoning patterns, and style from raw text.
• Supervised fine-tuning (optional)
  • smaller curated datasets (questions to answer, instructions to respond) teach it to follow directions.
• Reinforcement learning from Human Feedback (optional)
  • Humans rank multiple model outputs; a reward model is trained on those rankings; GPT is then optimized to produce higher-reward responses (safer, more helpful, less toxic)
• Text to Tokens via a tokenizer (e.g. BPE, Byte Pair Encoding)
• Each token becomes a vector (Embedding)
• Positional encodings inject order information.
• Transformer layer
  • self-attention: each token looks at all previous token (causal mask) and decides which ones matter, computing weighted combinations.
  • Multiple heads let it attend to different patterns (syntax, long-range links, etc.).
  • feed-forward network: a nonlinear MLP refines each token's representation.
  • residual connections & layer norm stabilize tranining.

Interfence​

• a prompt (the context)
• GPT computes probabiliites for the next token.
• A decoding stragety samples a token
  • Decoding knobs
    • Greedy: take the top token
    • Top-K
    • Nucleus (Top-p) sampling (limit to likely options)
    • Temperature scales randomness, controls how random the next token choice is
      • lower = more determistic, higher = more creative
• append the token and repeat autoregressive generation.

NLP​

Tokenization​

The process of dividing a text into a sequence of words.

• Different models uses different tokenization methods.

Corpus​

a large and structured collection of text

• a corpus typically consists of at least a million words of text
• at least tens of thousands of distinct vocabulary words.

Text classification​

• the process of categorizing text into organized groups.
• text classifiers can automatically analyze text and then assign a set of predefined tags or categories based on its content.
• machine learning approach
  • Features
    • BoW
    • TF-IDF
  • Features + classifier
    • Logistic regression
    • SVM
    • Naive Bayes
• Deep learning approach
  • Neural models: CNNs (capture local n-grams)
  • RNNs, LSTMs (sequence-aware)
  • Transformers (e.g. BERT)
    • Contextual embedding
• Modern enhancements
  • Embedding + classifier: Pretrained embeddings (Word2Vec) + classifier
  • Fine-tuned transformers: BERT fine-tuned

Bag of Words, BoW​

• it represents a text as a bag of its words
• we can understand the meaning of a document from its content (words) their multiplicity (frequency, number of occurrences)
• mainly used as a tool of feature extraction.
• limitations
  • ignores syntax and the context
  • disregarding grammar
  • discards word order - words are independent of each other
  • considers only the meanings of the words in the sentence

# examples

Example1 = "He likes to watch movies. Mary likes movies too."
Example2 = "Mary also likes to watch football games."

# Vocabulary
Vocab = {"He", "likes", "to", "watch", "movies", "Mary", "also", "football", "games"}

# BoW representation
BoW1 = {He: 1, likes: 2, to: 1, watch: 1, movies: 2, Mary: 1, also: 0, football: 0, games: 0}
BoW2 = {He: 0, likes: 1, to: 1, watch: 1, movies: 0, Mary: 1, also: 1, football: 1, games: 1}

[[1,2,1,1,2,1,0,0,0], [0,1,1,1,0,1,1,1,1]] 

TF-IDF​

Term Frequency - Inverse Document Frequency

• Model based on the statistics of word counts.
• idea is that key terms and important ideas are likely to repeat.
• includes a scoring function that measure the relevance of a document to a query.
  • the function takes a document with a corpus and a query as input and returns a numeric score.
  • the doucments that have the highest scores are considered as the most relevant documents.
• Term Frequency
  • $TF(q_i, d_j, D)$
• Inverse Document Frequency
  • $IDF(q_i, D) = \log\frac{N}{DF(q_i, D)}$
    • $DF(q_i, D)$: number of documents in the corpus $D$ that contain the term $q_i$
• $N = |D|$: total number of documents in the corpus $D$
• TF-IDF score
  • $TFIDF(q_i, d_j, D) = TF(q_i, d_j) \cdot IDF(q_i, D)$

Examples of TF-IDF​

• Document 1: "John likes to watch movies."
• Document 2: "Mary likes movies too."
• Document 3: "John also likes football."

Naive Bayes​

• naive refers to a very strong simplifying assumption about the features
• Conditional independence assumption
  • Given class $Y$, all the features $X = {X_1, X_2, ..., X_n}$ are assumed mutually independent.
• $P(X | Y) = P(X_1, ..., X_n | Y) = \prod_{i=1}^{n} P(X_i | Y)$
• Bayes rule
  • $P(Y | X) = \frac{P(X | Y) P(Y)}{P(X)} \propto P(Y) P(X | Y)$
  • $P(Y | X_1, ..., X_n) \propto P(Y) \prod_{i=1}^{n} P(X_i | Y)$
• Sentiment Analysis
  • $p(C_k | x_1, ..., x_n) = \frac{1}{Z} p(C_k) \prod_{i=1}^{n} p(x_i | C_k)$
    • $Z = p(x) = \sum_{k} p(C_k) p(x | C_k)$
      • scaling factor for normalization of $p(C_k | x)$
  • maximum a posteriori (MAP) decision rule
    • $\hat{y} = \argmax\limits_{k \in 1, ..., K}p(C_k) \prod_{i=1}^{n} p(x_i | C_k)$

Examples of Naive Bayes​

$P(Class | w_{1:N}) = \alpha \cdot P(Class) \cdot \prod_{j} P(w_j | Class)$

• Analyze the sentiment
  • my grandson loved it
  • $x_1 = \text{my}$, $x_2 = \text{grandson}$, $x_3 = \text{loved}$, $x_4 = \text{it}$
  • $C = {positive, negative}$
  • $\hat{y} = \argmax\limits_{k \in \{positive, negative\}} p(C_k) \cdot p(x_1 | C_k) \cdot p(x_2 | C_k) \cdot p(x_3 | C_k) \cdot p(x_4 | C_k)$
    • positive case
      • $p(positive) = 0.49$
      • $p(my | positive) = 0.30$
      • $p(grandson | positive) = 0.01$
      • $p(loved | positive) = 0.32$
      • $p(it | positive) = 0.30$
      • $p(positive | x) \propto p(positive) \cdot p(my | positive) \cdot p(grandson | positive) \cdot p(loved | positive) \cdot p(it | positive) = 0.49 \times 0.30 \times 0.01 \times 0.32 \times 0.30 = 0.00014256$
    • nagative case
      • $p(negative) = 0.51$
      • $p(my | negative) = 0.20$
      • $p(grandson | negative) = 0.02$
      • $p(loved | negative) = 0.08$
      • $p(it | negative) = 0.4$
      • $p(negative | x) \propto p(negative) \cdot p(my | negative) \cdot p(grandson | negative) \cdot p(loved | negative) \cdot p(it | negative) = 0.51 \times 0.20 \times 0.02 \times 0.08 \times 0.4 = 0.00006528$
    • $Z = p(x) = \sum_{k} p(C_k) p(x | C_k)$
      • $= p(positive) \cdot p(my, grandson, loved, it | positive) + p(negative) \cdot p(my, grandson, loved, it | negative)$
      • $= 0.00014256 + 0.00006528 = 0.00020784$
      • the probability of $x$, obtained by adding up its probabilities under each class.
    • $p(positive | x) = \frac{p(positive) \cdot p(my, grandson, loved, it | positive)}{Z} = \frac{0.00014256}{0.00020784} \approx 0.6867$
    • $p(negative | x) = \frac{p(negative) \cdot p(my, grandson, loved, it | negative)}{Z} = \frac{0.00006528}{0.00020784} \approx 0.3133$
  • Decision
    • $\hat{y} = \argmax\limits_{k \in \{positive, negative\}} \{k = positive : 0.6867, k = negative : 0.3133\}$
    • The sentiment is positive.
• Spam detection
  • Probabilities learned from data:
    • $P(\text{Spam}) = 0.4$, $P(\text{Ham}) = 0.6$
    • $P(\text{free}|\text{Spam}) = 0.8$, $P(\text{free}|\text{Ham}) = 0.1$
    • $P(\text{win}|\text{Spam}) = 0.7$, $P(\text{win}|\text{Ham}) = 0.05$
  • New document: "free win"
    • Spam score: $0.4 \times 0.8 \times 0.7 = 0.224$
    • Ham score: $0.6 \times 0.1 \times 0.05 = 0.003$
      → Classified as Spam.