1、Introduction to Artificial Intelligence: Applications in Computational Biology,Susan M. Bridges bridgescs.msstate.edu,Outline,What is AI? Search Expert systems Uncertainty Machine learning Data mining,Intelligent Systems and Computational Biology,First applications (DNA) in which great progress was
2、made were digital Signal processing algorithms Text processing techniques Many of the most interesting and difficult problems to be tackled are analog Protein structure Gene expression Metabolic networks,Definitions of AI (What is AI?),Rich, E. and K. Knight . 1991. Artificial Intelligence. New York
3、: McGraw-Hill. “Artificial intelligence (AI) is the study of how to make computers do things which at the moment, people do better.”,Another definition of AI,Winston, Patrick Henry. 1984. Artificial Intelligence. 1984. Addison-Wesley, Reading, MA. “Artificial Intelligence is the study of ideas that
4、enable computers to be intelligent. Intelligence includes: ability to reason, ability to acquire and apply knowledge, ability to perceive and manipulate things in the physical world, and others.”,Why Study AI?,Understand human human intelligence Develop “intelligent” machines Robotics Programs with
5、intelligent properties,Acting Rationally: Turing Test Approach,Interrogator,AI Tasks,Mundane tasks Perception Vision Speech Natural Language Understanding Generation Translation Common sense reasoning Robot control,Formal tasks Games Mathematics Geometry Logic Integral calculus Expert tasks Engineer
6、ing Scientific analysis Medical diagnosis Financial analysis,Intelligent Agents,Agent Perceives its environment using sensors Acts on environment using effectors Rational agent An agent that does the right thing Basis for action A measure of degree of success. Knowledge of what has been perceived so
7、 far. The actions that the agent can perform Autonomous Agent Learns from experience Makes independent decisions,Major Topics,Search Knowledge Representation Machine Learning,Problem-solving agent,A type of goal-based agent Find sequence of actions that lead to a desirable state Intelligent agents s
8、hould make a set of changes in the state of the environment that maximizes the performance measure Life is simpler if we can set a goal and aim to satisfy it.,Components of a problem,Initial state Set of possible actions actions can be described as operators an operator describes an action by specif
9、ying the state that can be reached by carrying out an action in a particular stateactions can be described in terms of a successor function S. Given a particular state x, S(x) returns the set of states reachable from x by any single action.,Operator a,State x,State y,State Space,The set of all state
10、s reachable from the initial state by any sequence of actions A path in the state space is a sequence of actions leading from one state to another The agent can apply a goal test to any single state to determine if it is a goal state. If one path is preferable to another, then we may need to compute
11、 path cost (g).,5,4,7,6,1,8,3,2,1,2,7,8,3,4,6,5,Initial State,Goal State,States Goal Test Operators Path Cost,Mathiston,Pheba,West Point,Maben,Starkville,Columbus,Ackerman,Sturgis,Artesia,Crawford,Brooksville,Louisville,Mayhew,Problem: Find route from Louisville to West Point,Louisville,A. The initi
12、al state,Louisville,Ackerman,Starkville,Brooksville,B. After expanding Louisville,C. After expanding Ackerman,Louisville,Ackerman,Starkville,Brooksville,Maben Sturgis Louisville,Some terms,New states are generated from old states by operators. This is called expanding the state. The choice of which
13、state to expand first is called the search strategy Result is called a search tree The set of nodes waiting to be expanded is called the fringe or frontier,Search Strategies,Requirements for a good search strategy causes motion is systematic State space can usually be represented as a tree or a grap
14、h Two important parameters of a tree branching factor (b) depth (d),Two Types of Searches,Uninformed or blind search systematically generate states test states to see if they are goal states Informed or heuristic search use knowledge about the problem domain explore search space more efficiently may
15、 sacrifice accuracy for speed,Breadth-first search,All nodes at each depth d are expanded before any nodes at depth d+1,Depth-first search,Always expands one of the nodes at the deepest level of the tree Parameter m is the maximum depth,What is a heuristic? (rule of thumb),A heuristic is a formalize
16、d rule for choosing those branches in a state space that are most likely to lead to an acceptable solution (Luger and Stubblefield, 1998). Used two ways some problems do not have exact solutions, so we just do the best we can (medical diagnosis) there may be an exact solution, but it may be very exp
17、ensive to find,Hill Climbing,Use an heuristic function (or objective or evaluation function) to decide which direction to move in the search space. Always move toward the state that appears to be best (basing all decisions on local information). Assume that we want to maximize the value of the funct
18、ion. Can also be used for minimization (called gradient descent),1 2 3 7 4 6 8 5,h=,Goal,Steepest Ascent Hill Climbing Using Manhattan Distance Heuristic,h=,h=,A* Search,Minimizing the total path cost Combines uniform-cost search and greedy search. Evaluation function: f(n) = g(n) + h(n) g(n): cost
19、of path from start to node n h(n): estimate of cost of path from n to goal f(n): estimated cost of the cheapest solution through n,Goal: Minimum length path. Is h(n) an admissible heuristic? f(n) = g(n) + h(n),K (18) L ( 3) M(2) N(9) O(5) P(2) Q(10) R(12)S (18) T(0) U (0),A(22),B (18) C (21) D (8),E
20、(12) F(7) G (9) H(6) I (13) J(14),d = 0,d = 1,d = 2,d = 3,d = 4,5,10,3,6,12,4,7,8,11,3 11 4 2 7 1 5 12 3 4,3 4 14 6 5,Numbers in parentheses are h(n) Numbers on edges are operator costs,Multiple Sequence Alignment,DNA and protein sequences Alignment of multiple sequences created by inserting gaps to
21、 shift characters to matching positionsATCG -ATCG-TGA -T-GAGAT GAT- Optimal alignment maximizes the number of matching positions,Multiple Sequence Alignment As State-Space Search (Eric Hansen, Rong Zhou),ATCG -ATCG-TGA -T-GAGAT GAT-,start,goal,Space Complexity: O (LN) Time Complexity: O (2NLN),Where
22、 L is the average length of sequences and N is the number of sequences,Nodes pruned by Anytime A*,An Illustration of Anytime A*,f = g + 2h,Goal,= expanded node,= stored but not expanded node,Total number of nodes stored = 8,Genetic Algorithms,Search procedure based on a simple model of evolution Use
23、s a “random” process to explore search space Has been applied in many domains,Terminology,Begin with a population of individuals. Each individual represents a solution to the problem we are trying to solve. A data structure describes the genetic structure of the individual. (Assume for initial discu
24、ssion that this is a string of 0s and 1s). In genetics, the strings are called chromosomes and the bits are called genes. The string associated with each individual is its genotype Selection is based on fitness of individuals,The Genetic Algorithm,Each evolving population of individuals is called a
25、generation. Given a population of individuals corresponding to one generation, the algorithm simulates natural selection and reproduction in order to obtain the next generation.,Three basic operations,Reproduction: Individuals from one generation are selected for the next generation Crossover: Genet
26、ic material from one individual is exchanged with genetic material from another individual Mutation: Genetic material is altered,General GA Procedure,Selection, crossover, and mutation operations,Initial population,Parent candidate pool,Father and Mother,Offspring,Crossover and mutate,Next generatio
27、n population,Converge?,Evaluate fitness,Evaluate fitnessand replace,Selectparents,no,yes,Example of General GA Procedure,Selection, crossover, and mutation operations,Generation n,1 1 0 1,1 0 1 1,0 1 0 0,1 0 0 1,Reproduction,Crossover,Mutation,Generation n+ 1,Two keys to the success of a GA,Data str
28、uctures for Genes Chromosomes PopulationFitness evaluation function,Knowledge Representation,Semantic networks Frame based systems Rule based expert systems Ontologies Neural networks,Anything,AbstractObjects,Events,Sets,Numbers,Representational Objects,Intervals,Places,Physical Objects,Processes,Ca
29、tegories,Sentences,Measurements,Moments,Times,Weights,Things,Stuff,Animals,Agents,Humans,Expert Systems,Rule based systems Garnered a great deal of attention in the 1980s Most famous examples are in medical domains Stimulated interest in “logic programming” Encode knowledge of people as sets of rule
30、s Still widely used Knowledge acquisition bottleneck,Representing Uncertainty,Fuzzy logic Bayesian reasoning,Uncertainty versus Vagueness,Certaintydegree of belief there is a 50% probability of rain today I am 30 % sure the patient is suffering from pneumonia Vaguenessthe degree to which an item bel
31、ongs to a category the man is tall move the wheel slightly to the left the patients lungs are highly congested,Fuzzy Sets Represent Vagueness,Lotfi Zadeh popularized the idea in the 60s Popular concept in Eastern philosophy Reasoning with fuzzy sets is called fuzzy logic Fuzzy logic is also called a
32、pproximate reasoning continuous logic,Fuzzy Set Definitions,Set membership can be expressed using a characteristic (or descrimination) function Classic (or crisp) sets If objects x are chosen from some universe XFuzzy sets - an element can be a partial member of a set (grade of membership),Examples
33、of Fuzzy Concepts from Natural Language,John is tall The weather is rainy Turn the volume up a little Dr. Bridges tests are long Add water until the dough is the right consistency There was very little change in the cost The water bill was somewhat high,Representing Fuzzy Sets,Enumeration of members
34、hip values of all elements with non-zero membership TALL = .125/5.5, .5/6, .875/6.5, 1/7, 1/7.5, 1/8 Represent membership with a function,Functional Representations Fuzzy Set Tall,0,1,4 5 6 7,Tall,Height in feet,Membership,Linguistic (or Fuzzy)Variable,Usually corresponds to a noun The values of a l
35、inguistic variable are fuzzy sets (which correspond to adjectives) Examples: Linguistic variable Fuzzy sets Height short medium tall Weight light average heavy Temperature cold cool typical warm hot Speed slow medium fast,Linguistic Variable Temperature,30 40 50 60 70 80 90 100,0,1,Cold Normal Hot,S
36、ome Fuzzy Set Operations,Set union A B A B(x)max(A(x),B(x) for all x X alternate syntax (join operator) A B(x)A(x)B(x) for all x XSet intersection A B AB(x)min(A(x),B(x) for all x X alternate syntax (meet operator) A B(x)A(x) B(x) for all x X,Fuzzy Reasoning,A fuzzy proposition is a statement that a
37、sserts a value for a linguistic (or fuzzy) variable Example: Joes height is medium Linguistic variable (noun) Joes height Fuzzy set (adjective) medium The fuzzy set “medium” is a value of the linguistic variable “Joes height” A fuzzy rule relates two or more fuzzy propositions Fuzzy inference techni
38、ques are used to draw conclusions using fuzzy rules,Example Fuzzy Rule,If speed is normal then braking.force is mediumSpeed Normal = (0/0, .1/20, .8/40, 1/60, .1/80, 0/100)braking.force Medium = (0/0, .5/1, 1/2, 1/3, .2/4, 0/5),J. Dickerson, D. Bedeant, Z.Cox, W. Qi, D. Ashlock, and E. Wurtele, Atla
39、nticSymposium on Computational Biology and Genome Information Systems & Technology (CBGIST 2000, 26-30.,Bayesian Reasoning,Bayesian networks: Represent knowledge as a network of random variables Many names and many variations Belief networks Probabilistic networks Causal networks Knowledge Maps Infl
40、uence Diagram (extension) Decision Network (extension),Belief Network,Burglary,Earthquake,Alarm,JohnCalls,MaryCalls,P(B) 0.001,P(E) 0.002,B E P(A|B,E)T T 0.95T F 0.94F T 0.29F F 0.01,A P(J|A) T 0.90 F 0.05,A P(M|A) T 0.70 F 0.01,Classification of Learning Systems,Supervised learning Give the system
41、a set of examples and an “answer” for each example. Train the system until it can give the correct response to these examples (or most of them). Unsupervised learning Give the system a set of examples and let it discover interesting patterns in the examples. Reinforcement learning Learn from rewards
42、 and penalties,Feature Vectors,Simple representation used by most learning systems. Represents each example as a vector or numbers Quantities Nominal data Ordinal data,Neural Networks,Computational models “loosely” based on the structure of the brain Characteristics of the brain Large number of simp
43、le processing units (neurons) Highly connected No central control Neurons are slow devices compared to digital computers Can perform complex tasks in a short period of time Neurons are failure-prone devices Handles fuzzy situations very well. Information accessed on the basis of content Learns from
44、experience,Neural Networks,Based on model of nervous system Large numbers of simple processing units Units are highly connected and connections are weighted. Highly parallel distributed control Emphasis on learning internal representations automatically,Neural Network Concepts,Cell or unit or neuron
45、 or node Autonomous processing unit that models a neuron Purpose Receives information from other cells Performs simple processing Sends results on to one or more cells Layers A collection of cells that perform a common function Types: Input layer Hidden layer Output layer,Layers of Neurons,I1,I2,I3,
46、H1,H2,O1,Input Layer,Hidden Layer,Output Layer,Properties,In general, there is no interconnection between cells in the same layer Connections are one or two way communications links between two cells Weights are the strength of the connections. A weight wij is a real number than indicates the influe
47、nce that cell ui has on cell uj,More about weights,Positive weights indicate reinforcement Negative weights indicate inhibition Weight of 0 indicates no influence or connection Weights may be initialized to one of these: 0 predefined values random values Weights are altered by experience,Multilayer
48、Feed-Forward Networks,Networks that are connected acyclic graphs Backpropagation Most popular training method for feed forward layered networks. Invented in 1969 by Bryson and Ho Ignored until 80s Supervised learning technique,Back Propagation,Initialize the network with random weights Show it an input instance Compute the output Determine how much the output differs from the goal. Feed small adjustments to the weights back through the network based on the error.,
