Exam.docx

Artificial Intelligence (AI) is a branch of computer science that aims to create systems capable of performing tasks that typically require human intelligence. These tasks include understanding natural language, recognizing patterns, learning from experience, reasoning, and making decisions. AI syst...

Artificial Intelligence (AI) is a branch of computer science that aims to create systems capable of performing tasks that typically require human intelligence. These tasks include understanding natural language, recognizing patterns, learning from experience, reasoning, and making decisions. AI systems are designed to mimic cognitive functions associated with human minds, such as learning from data, adapting to new situations, and solving problems. They rely on algorithms and computational models to process large amounts of data, identify patterns, and make predictions or decisions based on that information. There are various approaches to AI, including symbolic AI, which involves programming computers to manipulate symbols based on predefined rules, and machine learning, which enables systems to learn from data without being explicitly programmed. Deep learning, a subset of machine learning, utilizes artificial neural networks with many layers (hence "deep") to analyse` complex data and extract meaningful insights. Ethical Problems Bias and Discrimination: AI systems can perpetuate or even exacerbate biases present in their training data, leading to unfair treatment of certain groups. Privacy Violations: AI technologies can intrude on individuals’ privacy by collecting, storing, and analysing vast amounts of personal data without consent. Lack of Accountability: It can be unclear who is responsible for the actions of AI systems, especially when they cause harm or operate in unexpected ways. Dehumanization: Over-reliance on AI can lead to dehumanization in various sectors, such as customer service and caregiving, by replacing meaningful human contact. Approach to Limit Impact: Implementing rigorous ethical guidelines, promoting transparency in AI algorithms and data usage, and ensuring that AI systems are regularly audited for bias and compliance with privacy laws. Legal Problems Intellectual Property Issues: Determining the ownership of AI-generated content or inventions can be complex. Liability for Harm: Legal challenges arise in assigning liability when AI systems cause damage or harm, whether physically, financially, or emotionally. Compliance with International Laws: AI systems operating across borders must navigate varying international regulations, which can be problematic. Approach to Limit Impact: Crafting clear legal frameworks that define the rights and responsibilities associated with AI outputs, and establishing international agreements to manage cross-border AI interactions. Social Problems Job Displacement: AI can lead to the displacement of workers, especially in sectors like manufacturing and administrative jobs, potentially increasing unemployment rates. Erosion of Human Skills: Overdependence on AI can lead to a decline in certain human skills, particularly those related to decision-making and problem-solving. Social Manipulation: AI can be used to manipulate social and political scenarios, such as through deepfakes or algorithmically curated content that can influence public opinions and elections. Approach to Limit Impact: Developing policies that support workforce transition through retraining programs, maintaining balances in human-AI roles to preserve essential skills, and regulating the use of AI in sensitive areas such as media and political campaigns. Agents and Environments: In the context of artificial intelligence, an agent is anything that can perceive its environment through sensors and act upon that environment through actuators. An environment is everything outside the agent that can be sensed and affected by the agent's actions. Agents and environments interact continuously, with the agent receiving input from the environment through sensors and producing output through actuators. Rationality: Rationality in AI refers to the ability of an agent to select actions that maximize its expected performance measure, given its knowledge and beliefs about the world. A rational agent is one that makes decisions that are expected to lead to the best outcome, based on its understanding of the environment and its goals. PEAS: PEAS stands for Performance measure, Environment, Actuators, and Sensors. It is a framework used to define the design specifications of an intelligent agent. Performance measure: This specifies what the agent is trying to achieve or optimize. It defines the criteria for success. Environment: This describes the context in which the agent operates, including the objects, entities, and conditions that the agent can sense and affect. Actuators: These are the mechanisms through which the agent can take actions or manipulate the environment. Sensors: These are the mechanisms through which the agent can perceive or gather information about the environment. Environment Types: Environments in AI can be categorized into different types based on their characteristics: Fully observable vs. partially observable: In a fully observable environment, the agent's sensors provide complete information about the state of the environment. In a partially observable environment, some aspects of the environment may be hidden from the agent's sensors. Deterministic vs. stochastic: In a deterministic environment, the next state of the environment is completely determined by the current state and the actions taken by the agent. In a stochastic environment, there is some randomness or uncertainty in the transition between states. Episodic vs. sequential: In an episodic environment, the agent's actions only affect the immediate reward or outcome, and each episode is independent of previous episodes. In a sequential environment, the agent's actions have long-term consequences, and the current state depends on previous states and actions. Static vs. dynamic: In a static environment, the environment does not change while the agent is deliberating. In a dynamic environment, the environment can change while the agent is acting. Agent Types: Agents can also be classified into different types based on their design and behavior: Architecture: Simple reflex agents operate based on a set of condition-action rules without maintaining any internal state representation. Decision-making Process: They select actions solely based on the current percept from the environment and the rules provided. Learning Mechanisms: Typically, these agents do not learn but rely on pre-defined rules provided by programmers or designers. Adaptation Abilities: Limited adaptability as they can't learn from experience or dynamically adjust their behavior. Reflex Agents with State: Architecture: These agents maintain an internal state representation of the world to make more informed decisions. Decision-making Process: They consider both the current percept and the internal state when selecting actions, often using state-action rules or condition-action rules. Learning Mechanisms: While they may not necessarily learn, they can adapt by updating their internal state representation based on new information. Adaptation Abilities: They can adapt to changes in the environment by updating their internal models and adjusting their behavior accordingly. Model-Based Reflex Agent: Architecture: These agents maintain an internal state representation of the world and use it to make decisions. Decision-making Process: They select actions based on both the current percept and the internal state representation, enabling more sophisticated decision-making. Learning Mechanisms: They may incorporate learning algorithms to update their internal state representation based on experience. Adaptation Abilities: They can adapt to changes in the environment by updating their internal models and adjusting their behaviour accordingly. Goal-Based Agents: Architecture: Goal-based agents maintain internal goals or objectives and take actions to achieve those goals. Decision-making Process: They consider the current state of the environment, their internal goals, and a strategy for achieving those goals. Learning Mechanisms: These agents may incorporate learning algorithms to refine their goal representation or their strategies for achieving those goals. Adaptation Abilities: Highly adaptable as they can dynamically adjust their goals and strategies based on changing circumstances. Utility-Based Agents: Architecture: Utility-based agents evaluate actions based on their utility or desirability and select the action with the highest expected utility. Decision-making Process: They consider not only goals but also the potential consequences of their actions, weighing the trade-offs between different outcomes. Learning Mechanisms: They may incorporate learning algorithms to estimate the utilities of different actions based on past experiences or expert knowledge. Adaptation Abilities: Highly adaptable as they can dynamically adjust their behavior based on changes in the environment or in their utility functions. Learning Agent: Architecture: Learning agents interact with an environment, selecting actions to maximize cumulative rewards over time. Decision-making Process: They learn optimal strategies through trial and error, receiving feedback in the form of rewards or penalties from the environment. Learning Mechanisms: They employ learning algorithms such as Q-learning or deep Q-networks to update their policies based on rewards received. Adaptation Abilities: Highly adaptable as they continuously learn and update their strategies based on new experiences.   Tree Search Algorithms: A tree search algorithm defines a strategy for expanding nodes in a search space. These strategies are evaluated based on dimensions like completeness, time complexity, space complexity, and optimality. Here are some common tree search algorithms: Breadth-first search (BFS) Description: BFS explores all neighbor nodes at the present depth level before moving to the nodes at the next level. It systematically expands outward from the initial state until it finds the goal state. BFS uses a FIFO queue to store the frontier nodes. Guarantees the shortest path to the goal in terms of number of edges. Requires significant memory space to store the frontier nodes, especially for large search spaces. Uniform-cost search (UCS) Description: UCS expands the node with the lowest path cost (i.e., cumulative cost from the initial state) rather than just the shallowest node. UCS uses a priority queue ordered by the cumulative path cost to store the frontier nodes. Finds the optimal solution in terms of the least total cost. May expand many nodes with low costs before finding the optimal solution, leading to high time complexity. Depth-first search (DFS) DFS explores as far as possible along each branch before backtracking. DFS uses a LIFO stack to store the frontier nodes. Requires less memory compared to BFS as it only needs to store nodes along the current path. Not guaranteed to find the shortest path. Can get stuck in infinite loops if the search space contains cycles. Depth-limited search (DLS) Description: DLS is a variant of DFS that limits the maximum depth of exploration. DLS terminates the search when it reaches a specified depth limit. Prevents DFS from getting stuck in infinite loops in cyclic search spaces. May miss the solution if the depth limit is too shallow. Iterative deepening search (IDS) Description: IDS repeatedly performs DFS with increasing depth limits until the goal state is found. IDS systematically increases the depth limit with each iteration. Retains the memory efficiency of DFS while guaranteeing the completeness of BFS. Redundant exploration of nodes at lower levels can increase time complexity. Greedy search Description: Greedy search selects the node that appears to be the most promising at each step based on a heuristic evaluation function. Often memory-efficient and computationally fast, especially for small search spaces. Does not guarantee optimality or completeness. May get stuck in local optima or fail to find the optimal solution. A* search Description: A* search efficiently finds the shortest path by combining information about the cost to reach a node and an estimate of the cost to reach the goal state. Complete and optimal if the heuristic function is admissible and consistent. Highly effective in finding optimal solutions in many problem domains. May require significant memory and computation resources, especially in large search spaces with complex heuristic functions. Admissible heuristic Role of Heuristic Function: Estimates the cost or utility of reaching a goal state from a given state in a search problem. Guides the search process by biasing it towards states that appear more promising based on the heuristic evaluation. Use in Different Search Methods: Heuristic functions are commonly used in informed search algorithms such as A* search, where they guide the search towards the most promising paths based on the estimated cost to reach the goal. Relaxed Problem Admissible heuristics can be derived from the exact solution cost of a relaxed version of the problem, where certain constraints are relaxed. The optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real problem. Action Planning in AI involves finding sequences of actions to achieve goals. This is crucial for various AI applications such as autonomous agents, AI automation, and hybrid systems. Planning Domain Definition Language (PDDL) provides a human-readable format for defining planning problems. It includes descriptions of possible states, actions, initial states, and goals. PDDL is derived from First-Order Predicate Logic (FOL), specifically from the planning language of STRIPS. Operators in PDDL refer to actions with preconditions and effects. They are essential for defining the structure of planning problems and specifying how they can be solved through automated planning techniques. Operators consist of action descriptions, preconditions (positive literals), and effects (positive/negative literals). A restricted language for state description uses unary and binary predicates for efficient planning algorithms. Unary predicates represent properties, while binary predicates denote relationships between objects. Static planning involves forward and backward search in state space. Forward search starts from the current state and plans subsequent actions toward the goal state, considering all applicable actions. Backward search starts from the goal state and plans previous actions from the initial state, considering only relevant actions. Forward Search (FS) with Heuristics: In forward search, the planning process starts from the initial state and explores possible sequences of actions to reach the goal state. Heuristics are used to estimate the cost or distance from the current state to the goal state, guiding the search towards states that are closer to the goal. Some common heuristics used in forward search include: Relaxing Actions: This heuristic simplifies or ignores certain aspects of actions, such as their preconditions or delete effects, to reduce the complexity of the search space and speed up the planning process. State Abstractions: By considering only more general states instead of all specific states, heuristics can reduce the size of the state space, making the search more efficient. Goal Distance Heuristic: This heuristic estimates the distance from the current state to the goal state, guiding the search towards states that are closer to the goal. Pattern Database Heuristic: This heuristic involves storing patterns of states and their associated costs, allowing for efficient estimation of the remaining cost to reach the goal state. Backward Search (BS) with Heuristics: In backward search, the planning process starts from the goal state and explores possible sequences of actions backward to reach the initial state. Heuristics are used to estimate the cost or distance from the current state to the initial state, guiding the search towards states that are closer to the initial state. Some common heuristics used in backward search include: Inverse Actions: This heuristic estimates the cost of reaching the current state from the initial state by considering the actions in reverse order. Goal Distance Heuristic: Similar to forward search, this heuristic estimates the distance from the current state to the initial state, guiding the search towards states that are closer to the initial state. Relaxed Planning Graph Heuristic: This heuristic constructs a relaxed planning graph from the current state to estimate the remaining cost to reach the initial state. Planning graphs and incremental progression are used to address the main disadvantages of state-space search, such as the exponential size of the search tree and non-admissible heuristics. Various methods exist for handling the complexities of planning in dynamic environments. These include contingent planning, conditional planning, and continuous planning. Each approach has its advantages and trade-offs, depending on the level of uncertainty in future states and the need for real-time adaptation. Common challenges in planning include incomplete or incorrect information and the qualification problem, which involves listing all required preconditions and possible outcomes of actions. Solutions include contingent or sensorless planning, conditional planning, and continuous planning/replanning approaches. Execution monitoring and replanning are essential for handling deviations from the initial plan due to changes in the environment or unexpected events. Techniques like IPEM (Integrated Planning, Execution, and Monitoring) facilitate real-time adaptation to ensure plan success. Restricted language ⇒ efficient algorithm When working with a restricted language for describing states using unary and binary predicates, an efficient algorithm for planning or reasoning about these states can use the simplicity and structure of the language. To design such Algorithm, keep in mind this consideration: Exploit Predicate Structure, Symbolic Reasoning, Constraint Propagation technique, Incremental Updates and Heuristic Search Markov Decision Processes Who is Markov? Russian mathematician Andrey Markov (1856-1922) MDPs are defined by the following components: States(S): These are the possible conditions or configurations in which the agent can find itself. Each state provides the agent with complete information about the past relevant to future decisions. Actions(A): In each state, the agent can choose from a set of possible actions. The choice of action may depend on the state. Transition Function(P): This function defines the probability of moving from one state to another given an action. It's often denoted as 𝑃(𝑠′∣𝑠,𝑎) meaning the probability of moving to state 𝑠’ from state 𝑠 after taking action 𝑎. Reward Function(R): This function gives the immediate reward (or penalty) received after transitioning from one state to another via an action. It can be specific to the state and action (𝑅(𝑠,𝑎), or it can depend on the state transition (𝑅(𝑠,𝑎,𝑠′)). Start State: This is where the agent begins the decision process. There may also be a set of initial states with probabilities. Terminal State: These are special states where the process ends. The agent's task is often to reach one of these states while maximizing some cumulative measure of reward. Markov Property in MDPs In Markov Decision Processes (MDPs), the Markov property asserts that the probability of moving to the next state depends only on the current state and the action taken. This is expressed mathematically as 𝑃(𝑠𝑡+1∣𝑠𝑡,𝑎𝑡)P(st+1∣st,at). This simplification means that the decision process does not require memory of the entire state history, making computations more feasible and focusing only on the present state and decisions. Non-Markovian Processes Non-Markovian processes do not adhere to this simplification. Here, the future state depends on an entire history of states and actions, expressed as 𝑃(𝑠𝑡+1∣𝑠𝑡,𝑎𝑡,𝑠𝑡−1,𝑎𝑡−1,…,𝑠0)P(st+1∣st,at,st−1,at−1,…,s0). This requirement for historical data makes predicting future states more complex and computationally demanding. Practical Implementation of MDPs The design of state representations in MDPs ensures that all relevant information from the past is encapsulated in the current state, eliminating the need for any additional historical data. This makes each state self-sufficient for making predictions and decisions about future states. Rewards in MDPs Types of Rewards: Immediate Reward: Received right after taking an action, typically denoted as 𝑅(𝑠,𝑎)R(s,a). Future Reward: Anticipated rewards from future actions, crucial for planning and strategy in MDPs. Role in Decision-Making: Positive rewards encourage beneficial actions. Negative rewards discourage detrimental actions. Reward Functions The reward function 𝑅(𝑠,𝑎,𝑠′)R(s,a,s′) specifies the reward for transitioning from state 𝑠s to 𝑠′s′ due to action 𝑎a. Designing effective reward functions is critical as they significantly influence learning outcomes and the behavior of the agent. Additional Concepts in MDPs Living Reward/Cost: A constant reward or cost applied to each action, influencing the agent’s strategy. Stochastic Transition Function: Defines the probabilistic outcomes of actions, reflecting the variability and uncertainty of the environment. Sequence of Rewards: Important for evaluating the long-term impact of strategies. Discounting: A method to prioritize immediate rewards over distant ones, often necessary in infinite or indefinite decision processes to ensure finite utilities. Relationship Between Values: Defined by the Bellman equations, which relate the value of a state to the expected returns from that state, shaping the foundation for algorithms like value iteration and policy iteration. Solving an MDP To solve an MDP means to find an optimal policy that maximizes the cumulative reward. There are several methods for this: Using Heuristic Search: Implement heuristic-based strategies like greedy algorithms or Monte Carlo Tree Search (MCTS) to quickly approximate solutions to MDPs. These techniques prioritize promising actions based on immediate rewards and heuristic evaluations of future states, enabling more focused and efficient exploration of the solution space. Using Value Iteration: Value Iteration iteratively updates state values using the Bellman equation to maximize expected utility from each state. It continues until the state values converge, based on a predefined threshold, allowing the derivation of an optimal policy that maximizes long-term rewards. Using Policy Iteration: Start with an initial random policy and use the Bellman equation to evaluate state values. Improve the policy by selecting actions that maximize these values. Repeat until the policy converges to the optimal one, efficiently refining the policy through continuous assessment and adjustment. Introduction to Machine Learning (ML) Machine Learning (ML) allows computers to generate new knowledge from existing data without explicit programming. It excels in several tasks: Detection: Identifying hidden patterns or anomalies. Classification: Organizing data into categories based on common characteristics. Recognition: Identifying known patterns within new data. Identification: Distinguishing specific entities based on unique characteristics. Prediction: Forecasting future occurrences based on historical data. Types of Learning Supervised Learning: Models predict outcomes based on input-output pairs, learning a mapping function from given data. Unsupervised Learning: Models identify patterns in data without explicit feedback, often used for clustering or dimensionality reduction. Utility-based Learning: Models improve through feedback mechanisms (rewards and punishments), adapting to perform better over time. Supervised Learning Quality Bias and Variance: Trade-offs include choosing between models that may overfit (high variance) or underperform on unseen data (high bias). Decision Trees: A method where decisions are made through a series of questions, leading to a prediction at the leaves. They are particularly sensitive to data changes and can handle various data types including missing and multivalued attributes. Model Selection and Optimization Model Selection: Involves choosing the appropriate model based on the hypothesis space that fits the data well. Optimization: Refining the model to achieve the best performance, typically using a validation set to tune parameters and a test set to assess model performance. Cross-validation: Used when limited data is available; it involves dividing the data into subsets and rotating them as training and validation sets. Parametric vs. Nonparametric Models Parametric Models: Assume a fixed number of parameters, simplifying the model but potentially limiting its ability to capture complex patterns. Nonparametric Models: Do not specify parameter count, allowing for more flexibility but requiring more data to train effectively. Support Vector Machines (SVM) SVMs: Powerful nonparametric models that find the best margin that separates different classes in the training data, enhancing generalization to new data. Developing Machine Learning Systems System Development Lifecycle: Involves defining the problem, collecting data, choosing the right model, training, and evaluating the model, followed by deployment and ongoing monitoring. Features and Tools: Utilizes methods like ROC curves for performance measurement, confusion matrices for error analysis, and practices like data augmentation and feature engineering for enhancing model robustness. Knowledge-Based Learning This involves using existing knowledge to guide or enhance the learning process: Explanation-Based Learning (EBL): Focuses on generalizing from specific examples using predefined rules and expanding the understanding of these instances through logical explanations. Relevance-Based Learning (RBL): Uses prior knowledge to identify and focus on the most relevant features for prediction tasks. Knowledge-Based Inductive Learning (KBIL): Combines inductive logic programming techniques with existing knowledge to formulate new hypotheses and explanations, facilitating a deeper understanding of the data. Inductive Logic Programming (ILP) Inductive Logic Programming is a type of machine learning that uses logic programming techniques within a framework of inductive reasoning. ILP integrates the power of logic-based representations with statistical learning principles. The process generally involves: Top-down Inductive Learning: This method begins with the most general hypothesis and refines it by adding constraints that make it more specific, based on the examples provided. Inverse Deduction: ILP uses inverse deduction to hypothesize rules that could lead to the observed training examples, effectively working backward from the conclusions to hypothesize the premises that might lead to them. Relevance-based Learning (RBL) Relevance-based Learning focuses on identifying which features or aspects of the data are most relevant to solving a particular problem. It uses prior knowledge to constrain the learning process to consider only those attributes that are deemed relevant, which helps in reducing complexity and improving the efficiency of the learning algorithm. A Logical Formulation of Learning This approach to machine learning involves: Learning by Extension of the Goal Predicate: Here, the learner extends its understanding of a goal predicate by finding new examples that fit a generalized form of known examples. Systematic Exploration of Hypotheses: Through a process of confirming or disconfirming hypotheses, the system refines its understanding of the problem space. Supervised Learning Quality In supervised learning, the quality of a model is critically important and is assessed based on: Bias: This refers to errors that result from simplistic assumptions in the learning algorithm. High bias can cause an algorithm to miss relevant relations between features and target outputs (underfitting). Variance: This reflects the algorithm's sensitivity to small fluctuations in the training dataset. High variance can cause modeling of random noise in the training data (overfitting). Bias-Variance Tradeoff: Managing the tradeoff between bias and variance is crucial for developing models that generalize well to new, unseen data. Decision Trees Decision Trees are a popular and easy-to-interpret model used in supervised learning. They work by: Creating Branches: The algorithm splits the input data into subsets based on tests that yield the greatest information gain at each node. Each branch represents an outcome of the test, and each node on the tree represents a test on an attribute. Handling Various Data Types: Decision trees can manage missing data, continuous and multivalued input attributes, and continuous-valued output attributes effectively. Stability Issues: Decision trees can change significantly in response to small changes in the data, potentially leading to entirely different tree structures. Applicability of Decision Trees Decision trees are versatile and can be adapted for various scenarios, but they require careful tuning to manage issues like overfitting, especially when dealing with complex data structures or datasets with high variability. By addressing these points, we cover the critical aspects of these machine learning methodologies and their implications for building robust predictive models.