12-08-2011, 02:56 PM
[attachment=15261]
Operationally Speaking, AI is:
Applied Cognitive Science
Computational models of human reasoning
Problem solving
Scientific thinking
Models of non-introspective mental processes
Language comprehension, language learning
Human memory organization (STM, LTM)
HISTORY
In the 1940s and 50s, a handful of scientists from a variety of fields (mathematics, psychology, engineering, economics and political science) began to discuss the possibility of creating an artificial brain. The field of artificial intelligence research was founded as an academic discipline in 1956.
Cont......
Cont......
In 1950 Alan Turing published a landmark paper in which he speculated about the possibility of creating machines with true intelligence
If a machine could carry on a conversation (over a teletype) that was indistinguishable from a conversation with a human being, then the machine could be called "intelligent."
Cont......
This simplified version of the problem allowed Turing to argue convincingly that a "thinking machine"
When access to digital computers became possible in the middle fifties, a few scientists instinctively recognized that a machine that could manipulate numbers could also manipulate symbols and that the manipulation of symbols could well be the essence of human thought. This was a new approach to creating thinking machines.
Cont......
In 1955, Allen Newell and (future Nobel Laureate) Herbert Simon created the "Logic Theorist" (with help from J. C. Shaw). The program would eventually prove 38 of the first 52 theorems in Russell and Whitehead's Principia Mathematica, and find new and more elegant proofs for some
Cont......
Simon said that they had "solved the venerable mind/body problem, explaining how a system composed of matter can have the properties of mind."(This was an early statement of the philosophical position John Searle would later call "Strong AI": that machines can contain minds just as human bodies do.)
Cont......
The years after the Dartmouth conference were an era of discovery, of sprinting across new ground. The programs that were developed during this time were, to most people, simply "astonishing":computers were solving algebra word problems, proving theorems in geometry and learning to speak English
Cont......
Few at the time would have believed that such "intelligent" behavior by machines was possible at allResearchers expressed an intense optimism in private and in print, predicting that a fully intelligent machine would be built in less than 20 yearsGovernment agencies like ARPA poured money into the new field
Cont......
The agencies which funded AI research (such as the British government, DARPA and NRC) became frustrated with the lack of progress and eventually cut off almost all funding for undirected research into AI. The pattern began as early as 1966 when the ALPAC report appeared criticizing machine translation efforts. After spending 20 million dollars, the NRC ended all support.
Cont......
In 1973, the Lighthill report on the state of AI research in England criticized the utter failure of AI to achieve its "grandiose objectives" and led to the dismantling of AI research in that country.(The report specifically mentioned the combinatorial explosion problem as a reason for AI's failings.)
Cont......
In the 1980s a form of AI program called "expert systems" was adopted by corporations around the world and knowledge became the focus of mainstream AI research. In those same years, the Japanese government aggressively funded AI with its fifth generation computer project.
Cont......
In 1981, the Japanese Ministry of International Trade and Industry set aside $850 million dollars for the Fifth generation computer project. Their objectives were to write programs and build machines that could carry on conversations, translate languages, interpret pictures, and reason like human beings.Much to the chagrin of scruffies, they chose Prolog as the primary computer language for the project
Cont......
The business community's fascination with AI rose and fell in the 80s in the classic pattern of an economic bubble. The collapse was in the perception of AI by government agencies and investors — the field continued to make advances despite the criticism. Rodney Brooks and Hans Moravec, researchers from the related field of robotics, argued for an entirely new approach to artificial intelligence.
Cont......
The field of AI, now more than a half a century old, finally achieved some of its oldest goals. It began to be used successfully throughout the technology industry, although somewhat behind the scenes.
On 11 May 1997, Deep Blue became the first computer chess-playing system to beat a reigning world chess champion, Garry Kasparov
AI-Based Problem Solving
BASIC SEARCH METHODS
State-Space <{S}, S0, {SGj}, {Oi}>
S0: Initial State
SG: Goal State(s) to be reached
Oi: Operators O: {S} => {S}
AI-Based Problem Solving (cont.)
State-Space Navigation
Forward Search: BFS, DFS, HS,…
Backward Search: BFS-1, Backchaining,…
Bi-Directional Search: BFS2,…
Goal Reduction: Island-S, MEA…
Transformation: {S} {S’}
Abstraction: {S} {SA} + MEA ({SA})…
Analogy: If Sim(P,P’) then Sol(P) Sol’(P’)
More on the State Space
Useful Functions:
Succ(si) = {sk | oj(si) = sk}
Reachable(si) = {U{sk} | Succ *(si)}
Succ-1(si) = {sk | oj(sk) = si)
Reachable-1(si) = {U{sk} | (Succ-1)*(si)}
s-Path(sa0, san) = (sa0, sa1,…, san)
…such that for all sa1 exists oj(sai) = sai+1
o-Path(sa0, san) = (oj0, oj1,…, ojn-1)
…such that for all sa1 exists oj(sai) = sai+1
More on the State Space (cont.)
Useful Concepts:
Solution = o-Path(s0, sG) [or s-Path]
Cost(Solution) = cost(oj) … often cost(oj) = 1
P is solvable if at least one o-Path(s0, sG) exists
Solutions may be constructed forward, backward or any which way
State spaces may be finite, infinite, implicit or explicit
Zero-Knowledge Search
Simple Depth-First Search
DFS(Scurr, Sgoal, S-queue)
IF Scurr = Sgoal, SUCCESS
ELSE Append(Succ(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE DFS(First(S-queue), Sgoal, Trail(S-queue))
Depth First Search
DFS (cont.)
Problems with DFS
Deep (possibly infinite) rat holes
depth-bounded DFS, D = max depth
Loops: Succ(Succ(..Succ(S))) = S
Keep s-Path and always check Scurr
Non-Optimality: Other paths may be less costly
No fix here for DFS
Worst-case time complexity (O(bmax(D,d))
DFS (cont.)
When is DFS useful?
Very-high solution density
Satisficing vs. optimizing
Memory-limited search: O(d) space
Solution at Known-depth (then D=d)
Zero Knowledge Search (cont.)
Simple Breadth-First Search
BFS(Scurr, Sgoal, S-queue)
IF Scurr = Sgoal, SUCCESS
ELSE Append(Succ(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE BFS(Last(S-queue), Sgoal,
All-But-Last(S-queue))
Breadth-First Search
Simple BFS cont.
Problems with BFS:
Loops: Succ(Succ(…Succ(S)))=S
Pseudo-loops: Revisiting old states off-path
Keep full visited prefix tree
Worst case time complexity O(bd)
Worst case space complexity O(bd)
When is BFS Useful?
Guarantee shortest path
Very sparse solution space
(better if some solution is close to SI)
Zero Knowledge Search (cont.)
Backwards Breadth-First Search
BFS(Scurr, Sinit, S-queue)
IF Scurr = Sinit, SUCCESS
ELSE Append(Succ-1(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE BFS(Last(S-queue), Sinit,
All-But-Last(S-queue))
Backwards Breadth-First Search
Backward-BFS (cont.)
Problems with Backward-BFS
All the ones for BFS
Succ(Scurr) must be invertible: Succ-1(Scurr)
When is Backward-BFS useful?
In general, same as BFS
If backward branching < forward branching
Bi-Directional Search
Algorithm:
Initialize Fboundary:= {Sinit}
Initialize Bboundary:= {Sgoal}
Initialize treef:= Sinit
Initialize treeb:= Sgoal
For every Sf in Fboundary
IF Succ(Sf) intersects Bboundary
THEN return APPEND(Path(treef), Path-1(treeb))
ELSE Replace Sf by Succ(Sf) & UPDATE (treef)
6. For every Sb in Bboundary
IF Succ(Sb) intersects Fboundary
THEN return APPEND(Path(treef), Path-1(treeb))
ELSE Replace Sb by Succ-1(Sb) & UPDATE (treeb)
7. Go to 5.
Note: where’s the bug?
Bi-Directional Breadth-First Search
Bi-Directional Search (cont.)
Problems with Bi-BFS
Loops: Succ(Succ(…Succ(S))) = S
Loops: Succ-1(Succ-1(… Succ-1(S)))) = S
Pseudo-loops: Revisiting old states off-path
Keep full visited prefix treef, trees
Succ(Scurr)must be invertible: Succ-1(Scurr)
When is Bi-BFS useful?
Space and time complexity:
O(bfd/2) + O(bbd/2) = O(bd/2) if bf = bb
Island-Driven BFS
Definition:
An island is a state known a-priori to be on the solution path between Sinit and Sgoal.
If there are k sequential islands:
BFS(Sinit, S-(goal)=
APPEND(BFS(Sinit, Sk1), BFS(Sk1, Sk2),…BFS(SIk, Sgoal))
Upper bound complexity: O(k*maxi=0:k[bdki,ki+1])
Complexity if islands are evenly spaced:
O((k+1)*bd/(k+1))
Island-Driven Search
APPLICATION AREA
FINANCE
Banks use artificial intelligence systems to organize operations, invest in stocks, and manage properties. In August 2001, robots beat humans in a simulated financial trading competition.
Financial institutions have long used artificial neural network systems to detect charges or claims outside of the norm, flagging these for human investigation.
MEDICAL FIELD
A medical clinic can use artificial intelligence systems to organize bed schedules, make a staff rotation, and provide medical information.
Artificial neural networks are used as clinical decision support systems for medical diagnosis, such as in Concept Processing technology in EMR software.
INDUSTRY`S
Robots have become common in many industries. They are often given jobs that are considered dangerous to humans. Robots have proven effective in jobs that are very repetitive which may lead to mistakes or accidents due to a lapse in concentration and other jobs which humans may find degrading. Japan is the leader in using and producing robots in the world. In 1999, 1,700,000 robots were in use worldwide.
Online and telephone customer service
Artificial intelligence is implemented in automated online assistants that can be seen as avatars on web pages.It can avail for enterprises to reduce their operating and training cost.A major underlying technology to such systems is natural language processing.
Cont.....
Similar techniques may be used in answering machines of call centres, such as speech recognition software to allow computers to handle first level of customer support, text mining and natural language processing to allow better customer handling, agent training by automatic mining of best practices from past interactions, support automation and many other technologies to improve agent productivity and customer satisfaction.
Transportation
Fuzzy logic controllers have been developed for automatic gearboxes in automobiles (the 2006 Audi TT, VW Toureg and VW Caravell feature the DSP transmission which utilizes Fuzzy logic, a number of Škoda variants (Škoda Fabia) also currently include a Fuzzy Logic based controller).
Telecommunications
Many telecommunications companies make use of heuristic search in the management of their workforces, for example BT Group has deployed heuristic search in a scheduling application that provides the work schedules of 20,000 engineers.
Music
The evolution of music has always been affected by technology. With AI, scientists are trying to make the computer emulate the activities of the skillful musician. Composition, performance, music theory, sound processing are some of the major areas on which research in Music and Artificial Intelligence are focusing.
News and publishing
The company Narrative Science makes computer generated news and reports commercially available, including summarizing team sporting events based on statistical data from the game. It also creates financial reports and real estate analyses.
Other
Applications are also being developed for gesture recognition (understanding of sign language by machines), individual voice recognition, global voice recognition (from a variety of people in a noisy room), facial expression recognition for interpretation of emotion and non verbal queues. Other applications are robot navigation, obstacle avoidance, and object recognition.
Cont.....
Various tools of artificial intelligence are also being widely deployed in homeland security, speech and text recognition, data mining, and e-mail spam filtering.
Operationally Speaking, AI is:
Applied Cognitive Science
Computational models of human reasoning
Problem solving
Scientific thinking
Models of non-introspective mental processes
Language comprehension, language learning
Human memory organization (STM, LTM)
HISTORY
In the 1940s and 50s, a handful of scientists from a variety of fields (mathematics, psychology, engineering, economics and political science) began to discuss the possibility of creating an artificial brain. The field of artificial intelligence research was founded as an academic discipline in 1956.
Cont......
Cont......
In 1950 Alan Turing published a landmark paper in which he speculated about the possibility of creating machines with true intelligence
If a machine could carry on a conversation (over a teletype) that was indistinguishable from a conversation with a human being, then the machine could be called "intelligent."
Cont......
This simplified version of the problem allowed Turing to argue convincingly that a "thinking machine"
When access to digital computers became possible in the middle fifties, a few scientists instinctively recognized that a machine that could manipulate numbers could also manipulate symbols and that the manipulation of symbols could well be the essence of human thought. This was a new approach to creating thinking machines.
Cont......
In 1955, Allen Newell and (future Nobel Laureate) Herbert Simon created the "Logic Theorist" (with help from J. C. Shaw). The program would eventually prove 38 of the first 52 theorems in Russell and Whitehead's Principia Mathematica, and find new and more elegant proofs for some
Cont......
Simon said that they had "solved the venerable mind/body problem, explaining how a system composed of matter can have the properties of mind."(This was an early statement of the philosophical position John Searle would later call "Strong AI": that machines can contain minds just as human bodies do.)
Cont......
The years after the Dartmouth conference were an era of discovery, of sprinting across new ground. The programs that were developed during this time were, to most people, simply "astonishing":computers were solving algebra word problems, proving theorems in geometry and learning to speak English
Cont......
Few at the time would have believed that such "intelligent" behavior by machines was possible at allResearchers expressed an intense optimism in private and in print, predicting that a fully intelligent machine would be built in less than 20 yearsGovernment agencies like ARPA poured money into the new field
Cont......
The agencies which funded AI research (such as the British government, DARPA and NRC) became frustrated with the lack of progress and eventually cut off almost all funding for undirected research into AI. The pattern began as early as 1966 when the ALPAC report appeared criticizing machine translation efforts. After spending 20 million dollars, the NRC ended all support.
Cont......
In 1973, the Lighthill report on the state of AI research in England criticized the utter failure of AI to achieve its "grandiose objectives" and led to the dismantling of AI research in that country.(The report specifically mentioned the combinatorial explosion problem as a reason for AI's failings.)
Cont......
In the 1980s a form of AI program called "expert systems" was adopted by corporations around the world and knowledge became the focus of mainstream AI research. In those same years, the Japanese government aggressively funded AI with its fifth generation computer project.
Cont......
In 1981, the Japanese Ministry of International Trade and Industry set aside $850 million dollars for the Fifth generation computer project. Their objectives were to write programs and build machines that could carry on conversations, translate languages, interpret pictures, and reason like human beings.Much to the chagrin of scruffies, they chose Prolog as the primary computer language for the project
Cont......
The business community's fascination with AI rose and fell in the 80s in the classic pattern of an economic bubble. The collapse was in the perception of AI by government agencies and investors — the field continued to make advances despite the criticism. Rodney Brooks and Hans Moravec, researchers from the related field of robotics, argued for an entirely new approach to artificial intelligence.
Cont......
The field of AI, now more than a half a century old, finally achieved some of its oldest goals. It began to be used successfully throughout the technology industry, although somewhat behind the scenes.
On 11 May 1997, Deep Blue became the first computer chess-playing system to beat a reigning world chess champion, Garry Kasparov
AI-Based Problem Solving
BASIC SEARCH METHODS
State-Space <{S}, S0, {SGj}, {Oi}>
S0: Initial State
SG: Goal State(s) to be reached
Oi: Operators O: {S} => {S}
AI-Based Problem Solving (cont.)
State-Space Navigation
Forward Search: BFS, DFS, HS,…
Backward Search: BFS-1, Backchaining,…
Bi-Directional Search: BFS2,…
Goal Reduction: Island-S, MEA…
Transformation: {S} {S’}
Abstraction: {S} {SA} + MEA ({SA})…
Analogy: If Sim(P,P’) then Sol(P) Sol’(P’)
More on the State Space
Useful Functions:
Succ(si) = {sk | oj(si) = sk}
Reachable(si) = {U{sk} | Succ *(si)}
Succ-1(si) = {sk | oj(sk) = si)
Reachable-1(si) = {U{sk} | (Succ-1)*(si)}
s-Path(sa0, san) = (sa0, sa1,…, san)
…such that for all sa1 exists oj(sai) = sai+1
o-Path(sa0, san) = (oj0, oj1,…, ojn-1)
…such that for all sa1 exists oj(sai) = sai+1
More on the State Space (cont.)
Useful Concepts:
Solution = o-Path(s0, sG) [or s-Path]
Cost(Solution) = cost(oj) … often cost(oj) = 1
P is solvable if at least one o-Path(s0, sG) exists
Solutions may be constructed forward, backward or any which way
State spaces may be finite, infinite, implicit or explicit
Zero-Knowledge Search
Simple Depth-First Search
DFS(Scurr, Sgoal, S-queue)
IF Scurr = Sgoal, SUCCESS
ELSE Append(Succ(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE DFS(First(S-queue), Sgoal, Trail(S-queue))
Depth First Search
DFS (cont.)
Problems with DFS
Deep (possibly infinite) rat holes
depth-bounded DFS, D = max depth
Loops: Succ(Succ(..Succ(S))) = S
Keep s-Path and always check Scurr
Non-Optimality: Other paths may be less costly
No fix here for DFS
Worst-case time complexity (O(bmax(D,d))
DFS (cont.)
When is DFS useful?
Very-high solution density
Satisficing vs. optimizing
Memory-limited search: O(d) space
Solution at Known-depth (then D=d)
Zero Knowledge Search (cont.)
Simple Breadth-First Search
BFS(Scurr, Sgoal, S-queue)
IF Scurr = Sgoal, SUCCESS
ELSE Append(Succ(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE BFS(Last(S-queue), Sgoal,
All-But-Last(S-queue))
Breadth-First Search
Simple BFS cont.
Problems with BFS:
Loops: Succ(Succ(…Succ(S)))=S
Pseudo-loops: Revisiting old states off-path
Keep full visited prefix tree
Worst case time complexity O(bd)
Worst case space complexity O(bd)
When is BFS Useful?
Guarantee shortest path
Very sparse solution space
(better if some solution is close to SI)
Zero Knowledge Search (cont.)
Backwards Breadth-First Search
BFS(Scurr, Sinit, S-queue)
IF Scurr = Sinit, SUCCESS
ELSE Append(Succ-1(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE BFS(Last(S-queue), Sinit,
All-But-Last(S-queue))
Backwards Breadth-First Search
Backward-BFS (cont.)
Problems with Backward-BFS
All the ones for BFS
Succ(Scurr) must be invertible: Succ-1(Scurr)
When is Backward-BFS useful?
In general, same as BFS
If backward branching < forward branching
Bi-Directional Search
Algorithm:
Initialize Fboundary:= {Sinit}
Initialize Bboundary:= {Sgoal}
Initialize treef:= Sinit
Initialize treeb:= Sgoal
For every Sf in Fboundary
IF Succ(Sf) intersects Bboundary
THEN return APPEND(Path(treef), Path-1(treeb))
ELSE Replace Sf by Succ(Sf) & UPDATE (treef)
6. For every Sb in Bboundary
IF Succ(Sb) intersects Fboundary
THEN return APPEND(Path(treef), Path-1(treeb))
ELSE Replace Sb by Succ-1(Sb) & UPDATE (treeb)
7. Go to 5.
Note: where’s the bug?
Bi-Directional Breadth-First Search
Bi-Directional Search (cont.)
Problems with Bi-BFS
Loops: Succ(Succ(…Succ(S))) = S
Loops: Succ-1(Succ-1(… Succ-1(S)))) = S
Pseudo-loops: Revisiting old states off-path
Keep full visited prefix treef, trees
Succ(Scurr)must be invertible: Succ-1(Scurr)
When is Bi-BFS useful?
Space and time complexity:
O(bfd/2) + O(bbd/2) = O(bd/2) if bf = bb
Island-Driven BFS
Definition:
An island is a state known a-priori to be on the solution path between Sinit and Sgoal.
If there are k sequential islands:
BFS(Sinit, S-(goal)=
APPEND(BFS(Sinit, Sk1), BFS(Sk1, Sk2),…BFS(SIk, Sgoal))
Upper bound complexity: O(k*maxi=0:k[bdki,ki+1])
Complexity if islands are evenly spaced:
O((k+1)*bd/(k+1))
Island-Driven Search
APPLICATION AREA
FINANCE
Banks use artificial intelligence systems to organize operations, invest in stocks, and manage properties. In August 2001, robots beat humans in a simulated financial trading competition.
Financial institutions have long used artificial neural network systems to detect charges or claims outside of the norm, flagging these for human investigation.
MEDICAL FIELD
A medical clinic can use artificial intelligence systems to organize bed schedules, make a staff rotation, and provide medical information.
Artificial neural networks are used as clinical decision support systems for medical diagnosis, such as in Concept Processing technology in EMR software.
INDUSTRY`S
Robots have become common in many industries. They are often given jobs that are considered dangerous to humans. Robots have proven effective in jobs that are very repetitive which may lead to mistakes or accidents due to a lapse in concentration and other jobs which humans may find degrading. Japan is the leader in using and producing robots in the world. In 1999, 1,700,000 robots were in use worldwide.
Online and telephone customer service
Artificial intelligence is implemented in automated online assistants that can be seen as avatars on web pages.It can avail for enterprises to reduce their operating and training cost.A major underlying technology to such systems is natural language processing.
Cont.....
Similar techniques may be used in answering machines of call centres, such as speech recognition software to allow computers to handle first level of customer support, text mining and natural language processing to allow better customer handling, agent training by automatic mining of best practices from past interactions, support automation and many other technologies to improve agent productivity and customer satisfaction.
Transportation
Fuzzy logic controllers have been developed for automatic gearboxes in automobiles (the 2006 Audi TT, VW Toureg and VW Caravell feature the DSP transmission which utilizes Fuzzy logic, a number of Škoda variants (Škoda Fabia) also currently include a Fuzzy Logic based controller).
Telecommunications
Many telecommunications companies make use of heuristic search in the management of their workforces, for example BT Group has deployed heuristic search in a scheduling application that provides the work schedules of 20,000 engineers.
Music
The evolution of music has always been affected by technology. With AI, scientists are trying to make the computer emulate the activities of the skillful musician. Composition, performance, music theory, sound processing are some of the major areas on which research in Music and Artificial Intelligence are focusing.
News and publishing
The company Narrative Science makes computer generated news and reports commercially available, including summarizing team sporting events based on statistical data from the game. It also creates financial reports and real estate analyses.
Other
Applications are also being developed for gesture recognition (understanding of sign language by machines), individual voice recognition, global voice recognition (from a variety of people in a noisy room), facial expression recognition for interpretation of emotion and non verbal queues. Other applications are robot navigation, obstacle avoidance, and object recognition.
Cont.....
Various tools of artificial intelligence are also being widely deployed in homeland security, speech and text recognition, data mining, and e-mail spam filtering.
