3-Control.html

Pei Wang, 07/18/2013 09:34 am

Download (7.5 kB)

 
1
<!DOCTYPE html public "-//w3c//dtd html 4.0 transitional//en">
2
<html>
3
<head>
4
  <meta http-equiv="content-type" content="text/html; charset=iso-8859-1">
5
  <title>NARS Tutorial 3</title>
6
</head>
7

    
8
<body>
9
<h3 align="center"><a href="http://www.mindmakers.org/documents/13">NARS Tutorial</a></h3>
10

    
11
<h1 align="center">NARS: Memory and Control</h1>
12

    
13
<p></p>
14

    
15
<h2>1. Resource problem</h2>
16
In a reasoning system, the logic part defines <i>possibility</i>, and the control part
17
realize certain possibility by <i>selecting premises and rules</i> for each inference
18
step, so as to organize the steps into inference processes to serve given
19
purposes. 
20

    
21
<p>Extreme situations: </p>
22
<ul>
23
  <li>When there is perfect control knowledge, the inference process directly
24
    goes to the desired conclusion, so the strategy is optimal, too. </li>
25
  <li>When there is sufficient resources, <a
26
    href="http://en.wikipedia.org/wiki/Brute-force_search">exhaustive
27
    search</a> is optimal. Example: IL-1. </li>
28
  <li>When there is no control knowledge, no strategy is better than exhaustive
29
    search. </li>
30
</ul>
31
The normal situation is none of the above: there are insufficient resources and
32
some imperfect control knowledge. 
33

    
34
<p>The common practice is <a
35
href="http://en.wikipedia.org/wiki/Heuristic#Computer_science">heuristic
36
research</a>, but a general-purpose system cannot depend on a given heuristic
37
function. </p>
38

    
39
<p>For an adaptive system, control information comes from experience. Under
40
AIKR, the design objective is to use experience to the extent allowed by
41
available resources. </p>
42

    
43
<p>AIKR means tasks can be unanticipated in content, arrival time, and
44
response-time requirement, so the solving process cannot follow an existing
45
algorithm specified in advance for a problem type. </p>
46

    
47
<p><a
48
href="http://www.cis.temple.edu/~pwang/Publication/CaseByCase.pdf">Case-by-case
49
problem solving</a>: directly reasoning on problem instance, using available
50
knowledge and resources at the moment. This approach provides flexibility and
51
creativity, but lacks predictability and repeatability. It cannot be analyzed
52
in terms of <a
53
href="http://en.wikipedia.org/wiki/Computability">computability</a> and <a
54
href="http://en.wikipedia.org/wiki/Computational_complexity">computational
55
complexity</a>. </p>
56

    
57
<p>Controlled concurrency: to process many tasks by time-sharing, though each
58
with a different speed, and to a different depth. </p>
59

    
60

    
61
<h2>2. Data structure</h2>
62

    
63
NAL-1 can handle two types of tasks, corresponding to the types of sentence in
64
Narsese: <i>judgment</i> and <i>question</i>. To process the former means to get its <i>implications</i>, and the latter, its <i>answers</i>.
65
<p>
66
For a given task, its processing is mostly determined by the beliefs
67
(knowledge of the system) interacting with it. Intuitively speaking, <i>tasks</i> are active, while <i>beliefs</i> are passive. Both are Narsese sentences.
68

    
69
<p>NARS inference processes consists of "<a
70
href="http://en.wikipedia.org/wiki/Forward_chaining">forward steps</a>" for judgment tasks, "<a href="http://en.wikipedia.org/wiki/Backward_chaining">backward steps</a>" for question tasks, and "local steps" for the pre-processing of both types of task. </p>
71
<p>
72
A bag is a <i>probabilistic priority-queue</i>. Its basic operations are (1)
73
<i>put in</i>, (2) <i>take out</i>, and (3) <i>access by key</i>. The take-out operation is probabilistic, according to the priority distribution of the items in the bag. Each operation takes a small constant time to finish. Bag supports the usage of insufficient time and space using relative and
74
absolute forgetting. </p>
75
<p>
76
Since NAL is a term logic, and its inference rules typically require shared
77
term in premises, tasks and beliefs can be indexed and clustered by their
78
subject and predicate. In NARS, each <i>concept</i> is named by a term, and refers to the tasks and beliefs with the term in it. A concept becomes an independent unit of storage and processing. </p>
79

    
80
<p>Roughly speaking, the system's memory contains a bag of concepts; a concept contains a bag of tasks and a bag of beliefs. A summary for the architecture and working cycle is <a href="http://open-nars.googlecode.com/files/architecture.pdf">here</a>.
81

    
82
<h2>3. Inference process</h2>
83

    
84
NARS repeats the following working cycle: 
85
<ol>
86
  <li>Select a concept from the memory, </li>
87
  <li>Select a task from the concept, </li>
88
  <li>Select a belief from the concept, </li>
89
  <li>Use the task and the belief as premises for the applicable rules to
90
    derive new tasks, </li>
91
  <li>Return the used items with adjusted priority, </li>
92
  <li>Add the derived tasks and input tasks obtained in this cycle into the
93
    corresponding concepts. Report an answer to an input question if it is the
94
    best that the system has found. </li>
95
</ol>
96

    
97
The priority of an item (task, belief, or concept) is determined at its
98
creation time, then adjusted each time the item is accessed, mainly depending on the following factors: </p>
99
<ul>
100
  <li>its intrinsic quality (which remains stable over time), </li>
101
  <li>its performance record (which accumulates over time), </li>
102
  <li>its contextual relevance (which changes constantly). </li>
103
</ul>
104

    
105
<p>Generally speaking, the system constantly reorganizes its knowledge for question answering. The major criteria in organizing knowledge include: </p>
106
<ul>
107
  <li>Correctness with respect to experience, </li>
108
  <li>Concreteness of prediction, </li>
109
  <li>Compactness in content. </li>
110
</ul>
111

    
112
<p>The processes of "axiomatization" and "deaxiomatization" coexist. </p>
113

    
114

    
115
<h2>[4. Related ideas]</h2>
116
The control mechanism of NARS is related to many AI and computer science ideas,
117
including <a
118
href="http://en.wikipedia.org/wiki/Heuristics#Computer_science">heuristic
119
algorithm</a>, <a href="http://en.wikipedia.org/wiki/Time-sharing">time
120
sharing</a>, <a href="http://en.wikipedia.org/wiki/Anytime_algorithm">anytime
121
algorithm</a>, <a href="http://en.wikipedia.org/wiki/Genetic_algorithm">genetic
122
algorithm</a>, <a
123
href="http://en.wikipedia.org/wiki/Spreading_activation">spreading
124
activation</a>, and <a href="http://cogsci.indiana.edu/parallel.html">parallel
125
terraced scan</a>. 
126

    
127
<p>Related psychological phenomena include <a
128
href="http://en.wikipedia.org/wiki/Attention">attention</a>, <a
129
href="http://en.wikipedia.org/wiki/Recollection">recall</a>, <a
130
href="http://en.wikipedia.org/wiki/Forgetting">forgetting</a>, <a
131
href="http://en.wikipedia.org/wiki/Priming_%28psychology%29">priming</a>, <a
132
href="http://en.wikipedia.org/wiki/Association_%28psychology%29">association</a>,
133
<a
134
href="http://en.wikipedia.org/wiki/Intuition_%28psychology%29">intuition</a>,
135
as well as <a href="http://en.wikipedia.org/wiki/Creativity">inspiration and
136
creativity</a>. </p>
137

    
138
<p>Also related are <a
139
href="http://en.wikipedia.org/wiki/Operations_research">operation research</a>
140
and <a href="http://en.wikipedia.org/wiki/Resource_allocation">resource
141
allocation</a>. </p>
142

    
143
<h2>5. Implementation and demonstration</h2>
144
There are <a href="http://www.cis.temple.edu/~wangp/demos.html">demonstrations
145
and examples</a> of NARS online. 
146

    
147
<p>NARS is implemented in Java, with an <a
148
href="http://code.google.com/p/open-nars/">open source version</a>. </p>
149

    
150
<p>NAL is also coded in Prolog. </p>
151

    
152
<p>There are <a href="http://code.google.com/p/open-nars/source/browse/trunk/nars-dist/Examples/">working examples</a> showing the expressing and reasoning capability of NARS.
153

    
154
<p></p>
155
<hr>
156

    
157
<h2>Reference</h2>
158
<ul>
159
  <li><i><a href="NAL-Wang.pdf">Non-Axiomatic Logic: A Model of Intelligent Reasoning</a></i>, Ch. 5</li>
160
  <li><i><a href="http://code.google.com/p/open-nars/wiki/MultiStepExamples">Examples of Reasoning Process</a></i>
161
  </li>
162
</ul>
163

    
164
</body>
165
</html>