IA mid

Greedy Algorithm

Greedy Algorithm

an approach for solving a problem by selecting the best option available at the moment. It doesn't worry whether the current best result will bring the overall optimal result

False

True or False

Greedy algorithm reverses the earlier decision even if the choice is wrong. It works in a top-down approach.

Greedy Choice Property, Optimal Substructure

We can determine if the algorithm can be used with any problem if the problem has the following properties

Greedy Choice Property

If an optimal solution to the problem can be found by choosing the best choice at each step without reconsidering the previous steps once chosen, the problem can be solved using a greedy approach. This property is called

Optimal Substructure

If the optimal overall solution to the problem corresponds to the optimal solution to its subproblems, then the problem can be solved using a greedy approach. This property is called

True

True or False
Advantages of Greedy Approach are
The algorithm is easier to describe.

This algorithm can perform better than other algorithms

False

True or False
The greedy algorithm always produce the optimal solution.

A* Algorithm

Its a computer algorithm that is widely used in pathfinding and graph traversal. The algorithm efficiently plots a walkable path between multiple nodes, or points, on the graph.

Dijkstra’s algorithm

One algorithm for finding the shortest path from a starting node to a target node in a weighted graph. The algorithm creates a tree of shortest paths from the starting vertex, the source, to all other points in the graph.

Breadth-first search

is an important graph search algorithm that is used to solve many problems including finding the shortest path in a graph and solving puzzle games.

Dijkstra’s algorithm, Breadth-first search

A* is an extension of _____ with characteristics of _________

Candidate Set

solution to the problem that has been created from the dataset.

Selection Function

a function that decides whether the element can be added as a solution or not.

Feasibility Function

checks whether the elements selected in the selection function & candidate set are feasible or not

Objective Function

assigns value to the solution

Solution Function

used to intimate the reaching of complete function.

Candidate Set, Selection Function, Feasibility Function, Objective Function, Solution Function

5 Components of Greedy Algorithm

Knowledge representation and reasoning

It is responsible for representing information about the real world so that a computer can understand and can utilize this knowledge to solve complex real-world problems. It also enables an intelligent machine to learn from that knowledge and experiences so, that it can behave intelligently like a human.

Knowledge

is a familiarity, awareness, or understanding of someone or, something, such as facts, information, descriptions, or skills, which is acquired through experience or, education by perceiving, discovering or, learning.

Declarative Knowledge

It is the type of knowledge that is, by its very nature, expressed in declarative sentences or indicative propositions. It includes concepts, facts, and objects.

Procedural Knowledge

is the knowledge exercised in the performance of some task. It can be directly applied to any task. It includes rules, strategies, procedures, agendas, etc. It depends on the task on which it can be applied.

Meta-knowledge

is knowledge about preselected knowledge. Examples are methods of planning, modeling,

Heuristic knowledge

is representing knowledge of some experts in a filed or subject. It is rules of thumb based on previous experiences, awareness of approaches, and which are good to work but not guaranteed.

Structural knowledge

is knowledge of how the ideas within a domain are integrated and interrelated. It describes relationships between various concepts such as kind of, part of, and grouping of something.

Perception, Learning, Knowledge Representation and Reasoning, Planning, Execution

Components of an Agent helps in decision making and displaying intelligent behaviors

Representation

The concept of representation is as philosophically vexing as that of knowledge. Representation is a relationship between two domains, where the first is meant to “stand for” or replace the second.

Knowledge representation

Is the field of study concerned with using formal symbols to represent a collection of propositions believed by some putative agent. As we will see, however, we do not want to insist that these symbols represent all the propositions the agent believes

Objects

All the facts about objects in our world domain

Events

are the actions that occur in our world

Performance

It describes behavior that involves knowledge about how to do things

Meta-knowledge

It is knowledge about what we know.

Facts

Facts are the truths about the real world and what we represent

Knowledge-Base

Is a group of Sentences (Here, sentences are used as a technical term and not identical with the English language).

Simple relational knowledge, Inheritable knowledge, Inferential knowledge, Procedural knowledge

Four Approaches to knowledge representation

Representational Accuracy, Inferential Adequacy, Inferential Efficiency, Acquisitional efficiency

Requirements for knowledge Representation system

Representational Accuracy

The KR system should have the ability to represent all kinds of required knowledge.

Inferential Adequacy

The KR system should have the ability to manipulate the representational structures to produce new knowledge corresponding to the existing structures.

Inferential Efficiency

The ability to direct the inferential knowledge mechanism in the most productive directions by storing appropriate guides.

Acquisitional efficiency

The ability to acquire new knowledge easily using automatic methods.

Simple relational knowledge

It is the simplest way of storing facts which uses the relational method, and each fact about a set of objects is set out systematically in columns

Inheritable knowledge

In this approach, all data must be stored in a hierarchy of classes. This approach contains inheritable knowledge which shows a relationship between instance and class, and it is called instance relation.

Inferential knowledge

This approach represents knowledge in the form of formal logic. This approach can be used to derive more facts.

Procedural knowledge

This approach uses small programs and codes that describe how to do specific things, and how to proceed. In this approach, one important rule is used which is the If-Then rule.

Logical Representation, Semantic Network Representation, Frame Representation, Production Rules 

There are four ways of knowledge representation

Logical Representation

is a language with some concrete rules that deal with propositions and have no ambiguity in representation.

Propositional Logics, Predicate logics

Logical representation can be categorized into mainly two logics

Syntax

are the rules which decide how we can construct legal sentences in the logic

Semantics

are the rules by which we can interpret the sentence in the logic

Semantic Network Representation

In this knowledge representation, we can represent our knowledge through graphical networks. This network consists of nodes representing objects and arcs which describe the relationship between those objects

Frame

is a record-like structure that consists of a collection of attributes and its values to describe an entity in the world

Facets

The various aspects of a slot are known as

Production Rule

It consists of (condition, action) pairs, which mean, "If condition then action."

Production Rule

IF (at bus stop AND bus arrives) THEN action (get into the bus)

Semantic Network Representation

The set of production rules, Working Memory, The recognize-act-cycle

Three parts of Production rules

Frame Representation

Heuristic

is a function which is used in Informed Search, and it finds the most promising path

Informed search algorithm

This algorithm contains an array of
knowledge such as how far we are from the goal, path
cost, how to reach to goal node, etc.

Greedy algorithm

this algorithm always selects the path which appears best at that moment

A* Algorithm

is the most commonly known form of best-first search. It uses heuristic function h(n), and cost to reach the node n from the start state g(n).

Knowledge-Based Agent

are those agents who have the capability of maintaining an internal state of knowledge, reason over that knowledge, update their knowledge after observations and take actions. These agents can represent the world with some formal representation and act intelligently.

Declarative approach

Approach where we Initialize with an empty knowledge base and telling the agent all the sentences with which we want to start with.

procedural approach

In the this approach, we directly encode desired behavior as a program code. Which means we just need to write a program that already encodes the desired behavior or agent.

Declarative approach, Procedural approach

Approaches to designing a knowledge-based agent

Activity Selection Problem

Best Time to Buy and Sell Stock

Job Sequence Problem

Fractional Knapsack Problem

Minimum Number of Coins

Minimum Platform Problem

Minimum Platform Problem

Connect 'n' Ropes with Minimal Cost

Merge Overlapping Intervals

Two City Scheduling

Top 10 Greedy Algorithm Problems
seperate via enter

Intelligent agents

are computer programs
or systems that can perform tasks
autonomously, make decisions, and
interact with users or their environment.

Chatbots and Virtual Assistants, Sentiment Analysis, Language Translation, Speech Recognition, Information Retrieval, Text Summarization

Intelligent Agents Applications in NLP

Tokenization

is the process of breaking down a text into individual words or tokens. This is the fundamental step in most NLP tasks. Tokens can be words, punctuation marks, or even sub word units in some languages.

Stop Words

are common words like "and," "the," "in," etc., that are often removed from text data because they don't carry significant information for many NLP tasks

POS tagging

assigns grammatical categories (such as noun, verb, adjective) to each word in a sentence.

NER

is the process of identifying and classifying named entities in text, such as names of people, places, organizations, dates, and more. It's crucial for information extraction and content categorization.

Named Entity Recognition

NER

Part-of-Speech

POS

Text Classification

involves categorizing text documents into predefined categories or labels. Common applications include spam detection, sentiment analysis, and topic categorization

Language Models

are pre-trained neural networks that have learned to predict the next word in a sentence based on context. Examples include GPT (Generative Pre-trained Transformer) models, which have been highly influential in NLP.

Tokenization, Stop Words, Part-of-Speech Tagging, Named Entity Recognition, Syntax and Grammar, Text Classification, Machine Learning and Deep Learning, Language Models

Basic Concepts of NLP

Data Collection and Preprocessing, Pattern Discovery, Recommendation Systems, Anomaly Detection, Predictive Analytics

Role of Intelligent Agents
in Data Mining

Data, Data Pre-Processing, Data Exploration, Data Mining Tasks

Basic Concepts of Data Mining

Classification, Clustering, Association Rule Mining, Regression, Anomaly Detection, Text Mining, Time Series Analysis

Data Mining Tasks

Backward Chaining

is the basis for “logic programming,” e.g., Prolog