Ai

AI

  • Acting humanly: Turing test
  • Acting rationally: rational agent, do the right thing -> which is expected to maximise goal.
  • Interpreters vs. Compilers
    • Interpreters
      • Translates program one statement at a time.
      • Take less amount of time to analyse the source code. However, the overall execution time is comparatively slower than compilers.
      • No intermediate object code is generated, hence are memory efficient.
    • Compilers
      • Scans the entire program and translates it as a whole into machine code.
      • Take a large amount of time to analyse the source code. However, the overall execution time is comparatively faster than interpreters.
      • Generates intermediate object code which further requires linking, hence requires more memory.

Formulating Search Problems

  • Search for stored data
    • Sequential search,
    • Binary search
  • Search for web documents
    • Page rank
  • Search for paths or routes
    • depth first search,
    • breadth first search,
    • branch and bound,
    • A*,
    • Monte Carlo tree search.
  • Search for solutions
    • evolutionary algorithms,
    • metaheuristics,
    • simulated annealing,
    • ant colony optimisation, etc.
  • Pac-man
    • Find paths
    • Eat-All-Dots
  • A set of states (state space)
  • A set of actions (transitions, costs)
  • A start state and a goal test

  • A solution is a sequence of actions (a plan) which transforms the start state to a goal state

  • State Space Graphs vs. Search Trees (repeated structure)

Uninformed (blind) algorithms

  • BFS and DFS
  • BFS
    • FIFO
    • shallowest node first
  • DFS
    • LIFO
    • deepest node first
  • 2.2.1

    Informed algorithms

  • Search heuristics
    • a function -> how close a state is to a goal.
    • Greedy search
    • A*: g(n) + h(n)
      • Video games
      • Pathing / routing problems
      • Resource planning problems
      • Robot motion planning
      • Language analysis
      • Machine translation
      • Speech recognition
  • Best-first search: ‘minimum’ cost nodes are expanded first

Optimisation problems

  • Systematic search
  • Constructive search
  • (Stochastic) local search
  • Continuous and Discrete
  • Heuristic optimisation
    • most valuable
    • can be add at min cost
  • random search
    • evaluate solution (s)
    • s’ = random solution
    • if evaluation(s’) is better than evaluation(s)
    • s = s’
  • Greedy
  • Local Search and Metaheuristics
  • bit-flip, Neighbours
    • random mutation
    • best solution
    • 3.1
  • Simulated Annealing
    • Start with a random solution s
    • Choose some “nearby” (a neighbour) solution s’
    • If the new solution is better (i.e. f(s’) ≤ f(s)) , take it as the current solution (= accept it)
    • If it is worse, accept it with a probability that depends on the deterioration f(s)-f(s’) and a global parameter T (the temperature)

Evolutionary Algorithms

  • Evolution by Natural Selection
  • Alter each gene independently with a probability Pm (mutation rate)
  • crossover
  • 2 -Swap Mutation
  • Permutation Representation: Create second part by inserting values from other parent:
    • Iin the order they appear there
    • Ibeginning after crossover point
    • Iskipping values already in child
    • Wrapping around at the end
  • Supervised
    • Binary/Multiclass Classification
    • Regression
    • Ranking
  • Unsupervised
    • Clustering
    • Dimensionality reduction
  • Reinforcement
  • overfitting

Decision Trees

  • ID3
    • Start with the whole training set S as the root node.
    • Iterate through the very unused attribute of the set S and calculate Entropy (H) and Information Gain (IG) of this attribute.
    • Select the attribute which has the largest Information Gain
    • Split the set S by the selected attribute to produce a subset of the data.
    • Continue to recur on each subset, considering only attributes never selected before.
  • IG(S, A) = H(S) - sum(p(t)H(t))
    • H(S) = -sum(plog(p))
    • based on each kind of feature to get the H(t)
    • p(t) is the frequency of this feature appears

    The nearest neighbour algorithm

  • Euclidean distance
  • A positive integer K is specified, along with a new sample
  • We select the K entries in our dataset which are closest to the new sample, according to a given distance metric
  • We find the most common classification of these entries
  • This is the classification we give to the new sample
  • KNN is a type of instance-based learning or non-generalizing learning: it does not attempt to construct a general internal model, but simply stores instances of the training data.
  • 4.3.

5.1 Unsupervised learning

  • clustering - K-Means
    • Randomly select k points in the dataset. These serve as initial cluster centroids for the observations.
    • Assign each observation to the cluster whose centroid is closest.
    • Iterate until the cluster assignments stop changing:
      • For each of the k clusters, compute the cluster centroid.
      • Assign each observation to the cluster whose centroid is closest.
  • Hierarchical Clustering
  • Agglomerative
    • Each example starts as a single-element cluster (leaf)
    • At each step, the two clusters that are the most similar are combined into a new bigger cluster (nodes)
    • Iterate until all points are member a single big cluster (root).
  • Divisive
    • Start with a single cluster (root) with all examples
    • At each step, the most heterogenous cluster is divided into two
    • Iterate, until all examples are in their own cluster
  • Single Linkage
  • Average Linkage
    • distance between one cluster and another cluster is considered to be equal to the average distance from any member of one cluster to any member of the other cluster.
  • Complete Linkage
    • Max distance
  • Delta Rule
Written on December 7, 2020