Notes
Mark Chen |
25 Feb 2021
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
1.1 What is AI
There are different kinds of definition on ‘what is an artificial intelligence’, which are shown below:
| Humanly | Rationally | |
|---|---|---|
| Thinking | Thinking Humanly | Thinking Rationally |
| Acting | Acting Humanly | Acting Rationally |
The column ‘humanly’ measures the success in terms of fidelity to human performance, in other word, how alike the AI is comparing to a real human being. The column ‘rationally’ measures the success in terms of ideal performance, called rationality. The definition of ‘rationality’ of a system is that the system is doing the ‘right thing’.
Rationality: Maximizing the expected revenue.
1.1.1 Acting Humanly: The Turing Test Approach
Term Definition
The Turing Test is designed to provide a satisfactory operational definition of intelligence.
A compouter passes the test if a human interrogator (Someone who ask question to program and real people), after posing some written questions, cannot tell whether the written responses come from a person or from a computer. A program that can pass the Turing Test should have these components:
- Natural Language Processing: The ability to Communicate
- Knowledge Representation: Store what it knows or hears
- Automated Reasoning: Use Stored information to Answer Questions and to draw new conclusions
- Machine Learning: Adapt to new circumstances and to detect and Extrapolate patterns
The Turing Test does not allow the interrogator to have a physical contact with the program itself since it is unnecessary. However, a Total Turing Test allow the interrogator to contact the robot with limited ways.
To pass the Total Turing Test, a robot need these additional components:
- Computer Vision to perceive objects
- Robotics to manipulate objects and move about
At the beginning, we try to mimic the human brain. However, it is not necessary to make the ‘Artificial Intelligence’ really look like human being. Though, we can learn the human brain and get some useful characteristics that is necessary to produce the intelligence. Two important characteristics: Memory and Stimulation
Like the aircraft, the AI only extract the characteristic from human being’s thinking process but not have to really ‘look like’ human beings.
1.1.2 Thinking Humanly: The Cognitive Modeling Approach
In order to let the computer program to ‘think like human’, we first have to know the actual working of human minds. And here is the use of Cognitive Science in Artificial Intelligence.
The Cognitive Science brings together computer models from AI and experimental techniques from psychology to construct precise and testable theories of the human mind.
1.1.3 Thinking Rationally: The ‘Laws of Thought’ Approach
The Greek philosopher Aristotle was the first people who try to provide a law of thought. His syllogisms (三段论) provided patterns for argument structures that always yield correct premises.
However, there are two main obstacles to this approach.
- It is not easy to take informal knowledge and state it in the formal terms required by logical notation, particularly when the knowledge is not 100% certain
- There is a big difference from solving a problem ‘in principle’ and ‘in practice’.
These two main points are the obstacle apply to any attempt to build up a computational reasoning systems.
1.1.4 Acting Rationally: The Rational Agent Approach
A rational agent is one that acts so as to achieve the best outcome, or, when there exists uncertainty, the best expected outcome.
Making Correct Inference is only a Part of being a rational agent. Since in some situations, there is no provably correct things to do*, but something still has to be done.
The goal of building up a Rational Agent is much more approachable that building up Laws of Thought since the standard of Rationality is perfectly defined by Mathematic and it is very General.
Perfect Rationality, which implies that the program will always do the correct thing is not possible in all situations. It will be easier for the program to achieve a Limited Rationality, which only aquire acting appropriately when there is not enough time to do all the computations one might like.
1.2 The Foundations of Artificial Intelligence
1.2.1 Philosophy
- Can formal rules be used to draw valid conclusions?
- How does the mid arise from a physical brain?
- Where does knowledge come from?
- How does knowledge lead to Actions?
These question has been thought by people since 384 B.C.. Aristotle provide an informal system of Syllogisms, which in principle will generate conclusions mechanically if the correct initial conditions are given. Many years later, on Vienna Circle, a theory called Logical Positivism is build up and it claimed that all knowledge can be characterized by the logical theories connected.
Conformation theory attempt to analyze the acquisition of knowledge from experience. Carnap defined an Explicit Computational Procedure for extracting knowledge from elementary experiences
After that, people begin to concern that the Actions are justified by a logial connection between the goals and the knowledge of the action’s outcome. Though this is quite true and very useful for us to build up an Artificial Intelligence, it doesn’t say what to do when several actions will achieve the goal or when no action will achieve it completely.
1.2.2 Mathematics
- What are formal rules to draw valid conclusions?
- What can be computed?
- How do we reason with uncertain information?
Though the fundation of artificial intelligence is defined by the philosophy, it uses the theorems in Mathematics to make it to be an formal science. It is based on three main areas of mathematics: Logic, Computation, and Probability.
The logic is developed also by the Aristotle, but the First Order Logic that we use till now is invented in 18 century. In 1931, the Godel’s Incompleteness Theorem(哥德尔不完备性定理) showed that in any formal theory as strong as Peano Arithmatic（皮亚诺公理系统）, there are True Statements that are UNDECIDABLE in the sense that they have no prove within the theory.
About Computable Problem, Alan Turing first imagine a kind of mechane called ‘Turing Mechane’, which can compute any computable given function’s solution, then he has shown that there were some functions that no Turing machine can compute. For example, no machine can tell in general whether a given program will return an answer or it will run forever.
Comparing to Computable, the Tractability is in fact more important. A problem is called Intractable if the time complexity to solve it is Exponential, the problems that is intractable is also called the NP Problem. If one problem can only be solved by a time complexity of $O(2^n)$, then we say this problem is ‘NP - Complete’
Besides logic and computation, another important part of mathematics used in AI is the Probability. As the Thomas Bayes proposed a rule for updating probabilities in the light of new evidence, which is a fundamental basis when the AI system nowadays are doing Uncertain Reasoning.
1.2.3 Economics
- How should we make decisions so as to maximizing payoff?
- How should we do this when others may not go along?
- How should we do this when the payoff may be far in the future?
Economics can be thought of as consisting of individual agents maximizing their own economic well-being The economists use the theory of ‘utility’ to help AI make dicision, which means that the AI will chose the step that will most benefit itself.
Decision Theory, which combines probability theory with utility theory with utility theory, provides the formal and complete framework for decisions. The Division Theory is useful when it is in a ‘large’ situation, that is, the action of an individual will not affect the whole environment’s status.
When the AI is used in a ‘small’ situation, another theory called Game Theory should be used since the AI will change the whole environment with its own decisions. A game is where the action of a player can significantly affect the utility of another. It has been proven that for some specific games, it is better for AI to adopt policies that are (at least looks like) Randomized.
Operation Search is used to make decision when finding the solution of a particular problem needs a complex management decisions.
After that, people find a class of sequential decision problems called Markov Decision Process.
Like we have said before, in many situations, it is either impossible nor inefficient for AI to choose the ‘Best’ solution, we only need it to making decisions that are ‘good enough’.
1.2.4 Neuroscience
- How do brains process information?
Neuroscience is the study of the nervous system, particularly the brain. People can use mathematical models to the study of nervous system. People uses the mathematical modeling tool to study the neuron science. People conclude that a collection of simple cells can lead to thought, action and consciouness
1.2.5 Psychology
- How do humans and animals think and act?
Cognitive Psychology, which views the brain as an information - processing device.
Craik specified three key steps of a knowledge - based agent:
- The stimulus must be translated into an internal representation
- The representation is manipulated by cognitive process to derive new internal representations.
- These are in turn retranslated into action.
1.2.6 Computer Engineering
- How can we build an efficient computer?
1.2.7 Control Theory and Cybernetics
- How can artifacts operate under their own control
People concern behavior as arising from a regulatory mechanism trying to minimize ‘error’, the difference between current state and goal state. People begin to use the homeostatic devices containing appropriate feedback loops to achieve stable adaptive behavior.
Tools of logical inference and computation allowed AI researchers to consider problems such as language, vision, and planning that fell completely outside the control theorist’s preview.
1.2.8 Linguistics
- How does language relate to thought?
Born with ‘AI’, an interesting hybrid field called computational linguistics or Natural Language Processing (NLP). Then people soon find out that the understanding of language requires an understanding of the subject matter and context, not only just understanding the structure of sentences.
