User:Mdebellis/sandbox: Difference between revisions

Content deleted Content added

Inline

Revision as of 02:49, 7 December 2013

This is the user sandbox of Mdebellis. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

A frame language is a metalanguage. It applies the frame concept to the structuring of language properties. Frame languages are usually software languages.

Description

Frame languages primarily focus on the recognition and description of objects and classes, with relations and interactions considered as "secondary".

In general, "frame" in this context means "something that can be/(has to be) fulfilled"^{[citation needed]}. In such sense, for example: Object-oriented programming languages are frame languages, but also every grammar is a frame language^{[citation needed]}. In specific contexts, the authors of computer languages use the term "frame" arbitrarily and frequently intuitively, and in a metaphoric sense.

In the field of Artificial Intelligence, a frame is a data structure introduced by Marvin Minsky in the 1970s that can be used for knowledge representation. Minsky frames are intended to help an Artificial Intelligence system recognize specific instances of patterns. Frames usually contain properties called attributes or slots. Slots may contain default values (subject to override by detecting a different value for an attribute), refer to other frames (component relationships) or contain methods for recognizing pattern instances. Frames are thus a machine-usable formalization of concepts or schemata. In contrast, the object-oriented paradigm partitions an information domain into abstraction hierarchies (classes and subclasses) rather than partitioning into component hierarchies, and is used to implement any kind of information processing. Frame Technology is loosely based on Minsky Frames, its purpose being software synthesis rather than pattern analysis.

Like many other knowledge representation systems and languages, frames are an attempt to resemble the way human beings are storing knowledge. It seems like we are storing our knowledge in rather large chunks, and that different chunks are highly interconnected. In frame-based knowledge representations knowledge describing a particular concept is organized as a frame. The frame usually contains a name and a set of slots.

The slots describe the frame with attribute-value pairs <slotname value> or alternatively a triple containing framename, slotname and value in some order. In many frame systems the slots are complex structures that have facets describing the properties of the slot. The value of a slot may be a primitive such as a text string or an integer, or it may be another frame. Most systems allow multiple values for slots and some systems support procedural attachments. These attachments can be used to compute the slot value, or they can be triggers used to make consistency checking or updates of other slots. The triggers can be trigged by updates on slots.

Inference and reasoning

In most frame-based knowledge representations, inheritance is the central inference mechanism. The frames are organized as a hierarchy with some general concept as the root frame. Many systems support multiple inheritance. In these systems the tree structure can look more like a directed graph with possible cycles.

Reasoning in frame-systems is based on frame matching, inheritance and spreading activation.

Implementations

Frame Representation Language (FRL), 1977, Roberts/Goldstein.
Two examples of frame- or frame based- languages are OIL and F-logic.
An editor for frame-based ontologies is Protégé.
The Knowledge Machine (KM) is a knowledge representation language and reasoning engine. The knowledge is represented as frames, but KM is also influenced by logic. This combination makes KM very expressive and provides it with a clear, formal semantics.
KL-ONE is a well known knowledge representation system in the tradition of semantic networks and frames. The system is an attempt to overcome semantic indistinctness in semantic network representations and builds upon the idea of Structured inheritance networks.

References

Marvin Minsky, A Framework for Representing Knowledge, MIT-AI Laboratory Memo 306, June, 1974.
Marvin Minsky, A Framework for Representing Knowledge, in: Patrick Henry Winston (ed.), The Psychology of Computer Vision. McGraw-Hill, New York (U.S.A.), 1975.
Daniel G. Bobrow, Terry Winograd, An Overview of KRL, A Knowledge Representation Language, Stanford Artificial Intelligence Laboratory Memo AIM 293, 1976.
R. Bruce Roberts and Ira P. Goldstein, The FRL Primer, 1977
R. Bruce Roberts and Ira P. Goldstein, The FRL Manual, 1977
R. Brachman, J. Schmolze. An overview of the KL-ONE Knowledge Representation System. Cognitive science 9, 171-216, 1985
Fikes, R. E., and T. Kehler. (1985). The role of frame-based representation in knowledge representation and reasoning. Communications of the ACM 28(9):904-920.
Peter Clark & Bruce Porter: KM - The Knowledge Machine 2.0: Users Manual, http://www.cs.utexas.edu/users/mfkb/RKF/km.html.
Peter D. Karp, The Design Space of Frame Knowledge Representation Systems, Technical Note 520. Artificial Intelligence Center, SRI International, 1992

External links

@@ Line 1: / Line 1: @@
 {{User sandbox}}
 <!-- EDIT BELOW THIS LINE -->
+A '''frame language''' is a [[metalanguage]]. It applies the [[frame (artificial intelligence)|frame]] concept to the structuring of language properties. Frame languages are usually [[programming language|software languages]].
-{{Multiple issues|
-{{cleanup-rewrite|date=February 2010}}
-{{unreferenced|date=December 2009}}
-}}
-An '''Inference Engine''' is a tool from [[Artificial Intelligence]]. The first inference engines were components of [[expert systems]]. The typical expert system consisted of a [[knowledge base]] and an inference engine. The knowledge base stored facts about the world. The inference engine applied logical rules to the knowledge base and deduced new knowledge. This process would iterate as each new fact in the knowledge base could trigger additional rules in the inference engine. Inference engines work primarily in one of two modes: [[forward chaining]] and [[backward chaining]]. Forward chaining starts with the known facts and asserts new facts. Backward chaining takes goals to prove and works backward determining what must be true to assert the goals.<ref name="Hayes-Roth 1983">{{cite book|last=Hayes-Roth|first=Frederick|title=Building Expert Systems|year=1983|publisher=Addison-Wesley|isbn=0-201-10686-8|coauthors=Donald Waterman, Douglas Lenat}}</ref>
-==Architecture==
+==Description==
+Frame languages primarily focus on ''the recognition and description of [[object-oriented programming|objects]] and classes'', with relations and interactions considered as "secondary".
-The logic that an inference engine uses is typically represented as IF-THEN rules. The general format of such rules is IF <nowiki><logical expression></nowiki> THEN <nowiki><logical expression></nowiki>. Prior to the development of expert systems and inference engines artificial intelligence researchers focused on more powerful [[Theorem-prover|theorem prover]] environments that offered much fuller implementations of [[First Order Logic]]. For example, general statements that included [[universal quantification]] (for all X some statement is true) and [[existential quantification]] (there exists some X such that some statement is true). What researchers discovered is that the power of these theorem proving environments was also their drawback. It was far too easy to create logical expressions that could take an indeterminate or even infinite time to terminate. For example, it is common in universal quantification to make statements over an infinite set such as the set of all natural numbers. Such statements are perfectly reasonable and even required in mathematical proofs but when included in an automated theorem prover executing on a computer are likely to cause the computer to crash or fall into an infinite non-terminating loop. Focusing on IF-THEN statements (what logicians call [[Modus ponens|Modus Ponens]]) still gave developers a very powerful general mechanism to represent logic but one that could be used efficiently with computational resources. What is more there is some psychological research that indicates humans also tend to favor IF-THEN representations when storing complex knowledge.<ref>{{cite book|last=Feigenbaum|first=Edward|title=The Handbook of Artificial Intelligence, Volume I|publisher=Addison-Wesley|isbn=0201118114|page=195|url=https://archive.org/stream/handbookofartific01barr#page/156/mode/2up|coauthors=Avron Barr|date=September 1, 1986}}</ref>
+In general, "[[Frame_(artificial_intelligence)|frame]]" in this context means "something that can be/(has to be) fulfilled"{{fact|date=September 2013}}. In such sense, for example: [[Object-oriented programming language]]s are frame languages, but also every [[grammar]] is a frame language{{fact|date=September 2013}}. In specific contexts, the authors of computer languages use the term "frame" arbitrarily and frequently intuitively, and in a [[metaphoric]] sense.
-A simple example of Modus Ponens often used in introductory logic books is "If you are human then you are mortal". This can be represented in [[pseudocode]] as:
+In the field of [[Artificial Intelligence]], a frame is a [[data structure]] introduced by [[Marvin Minsky]] in the 1970s that can be used for [[knowledge representation]]. Minsky frames are intended to help an [[Artificial Intelligence]] system recognize specific instances of patterns. Frames usually contain properties called ''attributes'' or ''slots''. Slots may contain ''default values'' (subject to override by detecting a different value for an attribute), refer to other frames (''component relationships'') or contain ''methods'' for recognizing pattern instances. Frames are thus a machine-usable formalization of [[concept]]s or [[schema (psychology)|schemata]]. In contrast, the [[object-oriented]] paradigm partitions an information domain into abstraction hierarchies ([[class (computer science)|classes]] and subclasses) rather than partitioning into component hierarchies, and is used to implement any kind of information processing. [[Frame Technology (software engineering)|Frame Technology]] is loosely based on Minsky Frames, its purpose being software ''synthesis'' rather than pattern ''analysis''.
-Rule1: Human(x) => Mortal(x)
+Like many other knowledge representation systems and languages, frames are an attempt to resemble the way human beings are storing knowledge. It seems like we are storing our knowledge in rather large chunks, and that different chunks are highly interconnected. In frame-based knowledge representations knowledge describing a particular concept is organized as a frame. The frame usually contains a name and a set of slots.
-A trivial example of how this rule would be used in an inference engine is as follows. In forward chaining, the inference engine would find any facts in the knowledge base that matched Human(x) and for each fact it found would add the new information Mortal(x) to the knowledge base. So if it found an object called Socrates that was Human it would deduce that Socrates was Mortal. In Backward Chaining the system would be given a goal, e.g. answer the question is Socrates Mortal? It would search through the knowledge base and determine if Socrates was Human and if so would assert he is also Mortal. However, in backward chaining a common technique was to integrate the inference engine with a user interface. In that way rather than simply being automated the system could now be interactive. In this trivial example if the system was given the goal to answer the question if Socrates was Mortal and it didn't yet know if he was human it would generate a window to ask the user the question "Is Socrates Human?" and would then use that information accordingly.
+The slots describe the frame with [[attribute-value pair]]s <slotname value> or alternatively a triple containing framename, slotname and value in some order. In many frame systems the slots are complex structures that have facets describing the properties of the slot. The value of a slot may be a primitive such as a text string or an integer, or it may be another frame. Most systems allow multiple values for slots and some systems support procedural attachments. These attachments can be used to compute the slot value, or they can be triggers used to make consistency checking or updates of other slots. The triggers can be trigged by updates on slots.
-This innovation of integrating the inference engine with a user interface led to the second early advancement of expert systems: explanation capabilities. The explicit representation of knowledge as rules rather than code made it possible to generate explanations to users. Both explanations in real time and after the fact. So if the system asked the user "Is Socrates Human?" the user may wonder why she was being asked that question and the system would use the chain of rules to explain why it was currently trying to assertain that bit of knowledge: i.e., it needs to determine if Socrates is Mortal and to do that needs to determine if he is Human. At first these explanations were not much different than the standard debugging information that developers deal with when debugging any system. However, an active area of research was utilizing natural language technology to ask, understand, and generate questions and explanations using natural languages rather than computer formalisms.<ref>{{cite journal|last=Barzilayt|first=Regina|coauthors=Daryl McCullough*, Owen Rambow* Jonathan DeCristofaro$, Tanya Korelsky*, Benoit Lavoie*|title=A NEW APPROACH TO EXPERT SYSTEM EXPLANATIONS|journal=USAF Rome Laboratory Report|url=http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA457707}}</ref>
+==Inference and reasoning==
-An inference engine cycles through three sequential steps: ''match rules'', ''select rules'', and ''execute rules''. The execution of the rules will often result in new facts or goals being added to the knowledge base which will trigger the cycle to repeat. This cycle continues until no new rules can be matched.
+{{Expand section|date=October 2011}}
+In most frame-based [[knowledge representation]]s, [[inheritance]] is the central [[inference]] mechanism. The frames are organized as a [[hierarchy]] with some general [[concept]] as the root frame. Many systems support [[multiple inheritance]]. In these systems the tree structure can look more like a [[directed graph]] with possible cycles.
+[[Reasoning]] in frame-systems is based on frame [[pattern matching|matching]], inheritance and [[spreading activation]].
-In the first step, match rules, the inference engine finds all of the rules that are triggered by the current contents of the knowledge base. In forward chaining the engine looks for rules where the antecedent (left hand side) matches some fact in the knowledge base. In backward chaining the engine looks for antecedents that can satisfy one of the current goals.
-In the second step select rules, the inference engine prioritizes the various rules that were matched to determine the order to execute them. In the final step, execute rules, the engine executes each matched rule in the order determined in step two and then iterates back to step one again. The cycle continues until no new rules are matched.<ref>{{cite web|last=Griffin|first=N.L.|title=A Rule-Based Inference Engine which is Optimal and VLSI Implementable|url=http://www.cs.uky.edu/~lewis/papers/inf-engine.pdf|work=http://www.cs.uky.edu|publisher=University of Kentucky|accessdate=6 December 2013}}</ref>
 ==Implementations==
-Early inference engines focused primarily on forward chaining. These systems were usually implemented in the [[Lisp (programming language)|Lisp]] programming language. Lisp was a frequent platform for early AI research due to it's strong capability to do symbolic manipulation. Also, as an interpreted language it offered productive development environments appropriate to [[debugging]] complex programs. A necessary consequence of these benefits was that Lisp programs tended to be slower and less robust than compiled languages of the time such as [[C (programming language)|C]]. A common approach in these early days was to take an expert system application and remove the inference engine used for that system and package it as a re-usable tool other researchers could use for the development of other expert systems. For example, [[MYCIN]] was an early expert system for medical diagnosis and EMYCIN was an inference engine extrapolated from MYCIN and made available for other researchers.<ref name="Hayes-Roth 1983">{{cite book|last=Hayes-Roth|first=Frederick|title=Building Expert Systems|year=1983|publisher=Addison-Wesley|isbn=0-201-10686-8|page=10|coauthors=Donald Waterman, Douglas Lenat}}</ref>
+*Frame Representation Language (FRL), 1977, Roberts/Goldstein.
-As expert systems moved from research prototypes to deployed systems there was more focus on issues such as speed and robustness. One of the first and most popular forward chaining engines was [[OPS5]] which used the [[Rete algorithm]] to optimize the efficiency of rule firing. Another very popular technology that was developed was the [[Prolog]] logic programming language. Prolog focused primarily on backward chaining and also featured various commercial versions and optimizations for efficiency and robustness.<ref>{{cite book|last=Sterling|first=Leon|title=The Art of Prolog|year=1986|publisher=MIT|location=Cambridge, MA|isbn=0-262-19250-0|coauthors=Ehud Shapiro}}</ref>
+*Two examples of frame- or frame based- languages are [[Ontology Inference Layer|OIL]] and [[F-logic]].
+*An [[ontology editor|editor]] for frame-based [[ontology (computer science)|ontologies]] is [[Protege (software)|Protégé]].
+*The [[Knowledge Machine]] (KM) is a knowledge representation language and reasoning engine. The knowledge is represented as frames, but KM is also influenced by logic. This combination makes KM very expressive and provides it with a clear, formal semantics.
+*[[KL-ONE]] is a well known knowledge representation system in the tradition of semantic networks and frames. The system is an attempt to overcome semantic indistinctness in semantic network representations and builds upon the idea of Structured inheritance networks.
+==References==
-As Expert Systems prompted significant interest from the business world various companies, many of them started or guided by prominant AI researchers created productized versions of inference engines. For example, [[IntelliCorp (software)|Intellicorp]] was initially guided by [[Edward Feigenbaum]]. These inference engine products were also often developed in Lisp at first. However, demands for more affordable and commercially viable platforms eventually made [[Personal Computer]] platforms very popular.
+* Marvin Minsky, [http://web.media.mit.edu/~minsky/papers/Frames/frames.html A Framework for Representing Knowledge], MIT-AI Laboratory Memo 306, June, 1974.
+* Marvin Minsky, ''A Framework for Representing Knowledge'', in: Patrick Henry Winston (ed.), The Psychology of [[Computer Vision]]. McGraw-Hill, New York (U.S.A.), 1975.
+* Daniel G. Bobrow, Terry Winograd, [ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/76/581/CS-TR-76-581.pdf An Overview of KRL, A Knowledge Representation Language],  Stanford Artificial Intelligence Laboratory Memo AIM 293, 1976.
+* R. Bruce Roberts and Ira P. Goldstein, [ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-408.pdf The FRL Primer], 1977
+* R. Bruce Roberts and Ira P. Goldstein, [ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-409.pdf The FRL Manual], 1977
+* R. Brachman, J. Schmolze. An overview of the KL-ONE Knowledge Representation System. Cognitive science 9, 171-216, 1985
+* Fikes, R. E., and T. Kehler. (1985). The role of frame-based representation in knowledge representation and reasoning. Communications of the ACM 28(9):904-920.
+* Peter Clark & Bruce Porter:  KM - The Knowledge Machine 2.0: Users Manual,  http://www.cs.utexas.edu/users/mfkb/RKF/km.html.
+* Peter D. Karp, [http://www.ai.sri.com/pub_list/236 The Design Space of Frame Knowledge Representation Systems], Technical Note 520. [[Artificial Intelligence Center]], [[SRI International]], 1992
 ==See also==
+*[[First-order logic]]
-*[[Action selection mechanism]]
-* [[Inductive inference]]
+*[[Semantic Networks]]
-*[[Expert system]]
+*[[Ontology language]]
+*[[Description logic]]
-==References==
-{{reflist}}
+==External links==
-{{Computable knowledge}}
+*http://hopl.murdoch.edu.au/showlanguage.prx?exp=6540&language=Frames
+*[http://www.cs.umbc.edu/771/papers/nebel.html Frame-Based Systems]
+*[http://www.ai.sri.com/~gfp/spec/paper/paper.html The Generic Frame Protocol]
+*[http://protege.stanford.edu/index.html The Protégé Ontology Editor]
+[[Category:Knowledge engineering]]
-{{DEFAULTSORT:Inference Engine}}
-[[Category:Expert systems]]
+[[Category:Knowledge representation]]
-[[Category:Decision theory]]
-[[Category:Inference]]