We propose in the paper a new solution to the so-called Logical Omniscience Problem of epistemic logic. Almost all attempts in the literature to solve this problem consist in weakening the standard epistemic systems: weaker systems are considered where the agents do not possess the full reasoning capacities of ideal reasoners. We shall argue that this solution is not satisfactory: in this way omniscience can be avoided, but many intuitions about the concepts of knowledge and belief get lost. We shall show that axioms for epistemic logics must have the following form: if the agent knows all premises of a valid inference rule, and if she thinks hard enough, then she will know the conclusion. To formalize such an idea, we propose to \dynamize' epistemic logic, that is, to introduce a dynamic component into the language. We develop a logic based on this idea and show that it is suitable for formalizing the notion of actual, or explicit knowledge.

In many scenarios it is desirable to augment existing data with information acquired from an external source. For example, information from the Web can be used to fill missing values in a database or to correct errors. In many machine learning and data mining scenarios, acquiring additional feature values can lead to improved data quality and accuracy. However, there is often a cost associated with such information acquisition, and we typically need to operate under limited resources. In this thesis, I explore different aspects of Resource-bounded Information Acquisition and Learning. The process of acquiring information from an external source involves multiple steps, such as deciding what subset of information to obtain, locating the documents that contain the required information, acquiring relevant documents, extracting the specific piece of information, and combining it with existing information to make useful decisions. The problem of Resource-bounded Information Acquisition (RBIA) involves saving resources at each stage of the information acquisition process. I explore four special cases of the RBIA problem, propose general principles for efficiently acquiring external information in real-world domains, and demonstrate their effectiveness using extensive experiments. For example, in some of these domains I show how interdependency between fields or records in the data can also be exploited to achieve cost reduction. Finally, I propose a general framework for RBIA, that takes into account the state of the database at each point of time, dynamically adapts to the results of all the steps in the acquisition process so far, as well as the properties of each step, and carries them out striving to acquire most information with least amount resources.

Der Begriff ``Agent'' hat sich als eine sehr nützliche Abstraktion erwiesen, um verschiedene Problembereiche auf eine intuitive und natürliche Art und Weise zu konzeptualisieren. Intelligente Agenten haben daher Anwendung gefunden in verschiedenen Teilbereichen der Informatik. Zur Modellierung werden intelligente Agenten meist als intentionale Systeme aufgefaßt und mit Hilfe von mentalistischen Begriffen wie Wissen, Glauben (oder Überzeugung), Wunsch, Pflicht, Intention usw. beschrieben. Unter diesen mentalen Begriffen gehören die epistemischen Begriffe (d.h., Wissen und Glauben) zu den wichtigsten und wurden auch am intensivsten untersucht. Zur Modellierung von Wissen und Glauben werden in der Regel modale epistemische Logiken verwendet. Solche Systeme sind aber nicht geeignet, um ressourcenbeschränkte Agenten zu beschreiben, weil sie zu starke Annahmen bezüglich der Rationalität von Agenten machen. Zum Beispiel wird angenommen, daß Agenten alle logischen Wahrheiten sowie alle Konsequenzen seines Wissens kennen. Dieses Problem ist bekannt als das Problem der logischen Allwissenheit (``logical omniscience problem''). Da alle Agenten grundsätzlich nur über begrenzte Ressourcen (wie z.B. Zeit, Information, Speicherplatz) verfügen, können sie nur eine begrenzte Menge von Informationen verarbeiten. Daher müssen alternative Modelle entwickelt werden, um Agenten realistisch modellieren zu können (siehe Kapitel 2). Daß modale epistemische Logik für die Formalisierung des ressourcenbeschränkten Schließens (``resource-bounded reasoning'') nicht geeignet ist, wird als ein offenes Problem der Agententheorien anerkannt. Es gibt bisher aber keine brauchbaren Alternativen zur Modallogik. Die meisten Ansätze zur Lösung des logischen Allwissenheitsproblems versuchen, Wissen und Glauben mit Hilfe schwacher Modallogiken zu beschreiben. Solche Versuche sind nicht befriedigend, da sie eine willkürliche Einschränkung der Rationalität der Agenten zur Folge haben (siehe Kapitel 3). Mein Ziel ist es, einen Rahmen für das ressourcenbeschränktes Schließen über Wissen und Glauben zu entwickeln. Damit soll eine solide Grundlage für Theorien intelligenter Agenten geschaffen werden. Als Nebenergebnis wird das logische Allwissenheitsproblem auf eine sehr intuitive Art und Weise gelöst: obwohl Agenten rational sind und alle logischen Schlußregeln anwenden können, sind sie nicht logisch allwissend, weil ihnen nicht genügend Ressourcen zu Verfügung stehen, um alle logischen Konsequenzen ihres Wissens zu ziehen. Im Kapitel 4 wird eine Reihe von Logiken vorgestellt, die den Begriff des expliziten Wissens formalisieren. Es wird eine Lösung des Problems der logischen Allwissenheit der epistemischen Logik vorgeschlagen, die die Rationalität der Agenten nicht willkürlich einschränkt. Der Grundgedanke dabei ist der folgende. Ein Agent kennt die logischen Konsequenzen seines Wissens nur dann, wenn er sie tatsächlich hergeleitet hat. Wenn ein Agent alle Prämissen einer gültigen Schlußregel kennt, kennt er nicht notwendigerweise die Konklusion: er kennt sie nur nach der Anwendung der Regel. Wenn er den Schluß nicht ziehen kann, z.B. weil er nicht die notwendigen Ressourcen dazu hat, wird sein Wissen nicht um diese herleitbare Information erweitert. Die Herleitung neuer Informationen wird als die Ausführung mentaler Handlungen aufgefaßt. Mit Hilfe einer Variante der dynamischen Logik können diese Handlungen beschrieben werden. Im Kapitel 5 werden Systeme für das ressourcenbeschränkte Schließen über Wissen und Glauben entwickelt, die auch quantitative Bedingungen über die Verfügbarkeit von Ressourcen modellieren können. Mit Hilfe dieser Logiken können Situationen beschrieben werden, wo Agenten innerhalb einer bestimmten Zeitspanne entscheiden müssen, welche Handlungen sie ausführen sollen. Der Ansatz besteht darin, epistemische Logik mit Komplexitätstheorie zu verbinden. Mit Hilfe einer Komplexitätsanalyse kann ein Agent feststellen, ob ein bestimmtes Problem innerhalb vorgegebener Zeit lösbar ist. Auf der Grundlage dieses Wissens kann er dann die für die Situation geeignete Entscheidung treffen. Damit ist es gelungen, eine direkte Verbindung zwischen dem Wissen eines Agenten und der Verfügbarkeit seiner Ressourcen herzustellen. / One of the principal goals of agent theories is to describe realistic, implementable agents, that is, those which have actually been constructed or are at least in principle implementable. That goal cannot be reached if the inherent resource-boundedness of agents is not treated correctly. Since the modal approach to epistemic logic is not suited to formalize resource-bounded reasoning, the issue of resource-boundedness remains one of the main foundational problems of any agent theory that is developed on the basis of modal epistemic logic. My work is an attempt to provide theories of agency with a more adequate epistemic foundation. It aims at developing theories of mental concepts that make much more realistic assumptions about agents than other theories. The guiding principle of my theory is that the capacities attributed to agents must be empirically verifiable, that is, it must be possible to construct artificial agents which satisfy the specifications determined by the theory. As a consequence, the unrealistic assumption that agents have unlimited reasoning capacities must be rejected. To achieve the goal of describing resource-bounded agents accurately, the cost of reasoning must be taken seriously. In the thesis I have developed a framework for modeling the relationship between knowledge, reasoning, and the availability of resources. I have argued that the correct form of an axiom for epistemic logic should be: if an agent knows all premises of a valid inference rule and if he performs the right reasoning, then he will know the conclusion as well. Because reasoning requires resources, it cannot be safely assumed that the agent can compute his knowledge if he does not have enough resources to perform the required reasoning. I have demonstrated that on the basis of that idea, the problems of traditional approaches can be avoided and rich epistemic logics can be developed which can account adequately for our intuitions about knowledge.

Der Begriff ``Agent'''' hat sich als eine sehr nützliche Abstraktion erwiesen, um verschiedene Problembereiche auf eine intuitive und natürliche Art und Weise zu konzeptualisieren. Intelligente Agenten haben daher Anwendung gefunden in verschiedenen Teilbereichen der Informatik. Zur Modellierung werden intelligente Agenten meist als intentionale Systeme aufgefaßt und mit Hilfe von mentalistischen Begriffen wie Wissen, Glauben (oder Überzeugung), Wunsch, Pflicht, Intention usw. beschrieben. Unter diesen mentalen Begriffen gehören die epistemischen Begriffe (d.h., Wissen und Glauben) zu den wichtigsten und wurden auch am intensivsten untersucht. Zur Modellierung von Wissen und Glauben werden in der Regel modale epistemische Logiken verwendet. Solche Systeme sind aber nicht geeignet, um ressourcenbeschränkte Agenten zu beschreiben, weil sie zu starke Annahmen bezüglich der Rationalität von Agenten machen. Zum Beispiel wird angenommen, daß Agenten alle logischen Wahrheiten sowie alle Konsequenzen seines Wissens kennen. Dieses Problem ist bekannt als das Problem der logischen Allwissenheit (``logical omniscience problem''''). Da alle Agenten grundsätzlich nur über begrenzte Ressourcen (wie z.B. Zeit, Information, Speicherplatz) verfügen, können sie nur eine begrenzte Menge von Informationen verarbeiten. Daher müssen alternative Modelle entwickelt werden, um Agenten realistisch modellieren zu können (siehe Kapitel 2). Daß modale epistemische Logik für die Formalisierung des ressourcenbeschränkten Schließens (``resource-bounded reasoning'''') nicht geeignet ist, wird als ein offenes Problem der Agententheorien anerkannt. Es gibt bisher aber keine brauchbaren Alternativen zur Modallogik. Die meisten Ansätze zur Lösung des logischen Allwissenheitsproblems versuchen, Wissen und Glauben mit Hilfe schwacher Modallogiken zu beschreiben. Solche Versuche sind nicht befriedigend, da sie eine willkürliche Einschränkung der Rationalität der Agenten zur Folge haben (siehe Kapitel 3). Mein Ziel ist es, einen Rahmen für das ressourcenbeschränktes Schließen über Wissen und Glauben zu entwickeln. Damit soll eine solide Grundlage für Theorien intelligenter Agenten geschaffen werden. Als Nebenergebnis wird das logische Allwissenheitsproblem auf eine sehr intuitive Art und Weise gelöst: obwohl Agenten rational sind und alle logischen Schlußregeln anwenden können, sind sie nicht logisch allwissend, weil ihnen nicht genügend Ressourcen zu Verfügung stehen, um alle logischen Konsequenzen ihres Wissens zu ziehen. Im Kapitel 4 wird eine Reihe von Logiken vorgestellt, die den Begriff des expliziten Wissens formalisieren. Es wird eine Lösung des Problems der logischen Allwissenheit der epistemischen Logik vorgeschlagen, die die Rationalität der Agenten nicht willkürlich einschränkt. Der Grundgedanke dabei ist der folgende. Ein Agent kennt die logischen Konsequenzen seines Wissens nur dann, wenn er sie tatsächlich hergeleitet hat. Wenn ein Agent alle Prämissen einer gültigen Schlußregel kennt, kennt er nicht notwendigerweise die Konklusion: er kennt sie nur nach der Anwendung der Regel. Wenn er den Schluß nicht ziehen kann, z.B. weil er nicht die notwendigen Ressourcen dazu hat, wird sein Wissen nicht um diese herleitbare Information erweitert. Die Herleitung neuer Informationen wird als die Ausführung mentaler Handlungen aufgefaßt. Mit Hilfe einer Variante der dynamischen Logik können diese Handlungen beschrieben werden. Im Kapitel 5 werden Systeme für das ressourcenbeschränkte Schließen über Wissen und Glauben entwickelt, die auch quantitative Bedingungen über die Verfügbarkeit von Ressourcen modellieren können. Mit Hilfe dieser Logiken können Situationen beschrieben werden, wo Agenten innerhalb einer bestimmten Zeitspanne entscheiden müssen, welche Handlungen sie ausführen sollen. Der Ansatz besteht darin, epistemische Logik mit Komplexitätstheorie zu verbinden. Mit Hilfe einer Komplexitätsanalyse kann ein Agent feststellen, ob ein bestimmtes Problem innerhalb vorgegebener Zeit lösbar ist. Auf der Grundlage dieses Wissens kann er dann die für die Situation geeignete Entscheidung treffen. Damit ist es gelungen, eine direkte Verbindung zwischen dem Wissen eines Agenten und der Verfügbarkeit seiner Ressourcen herzustellen. / One of the principal goals of agent theories is to describe realistic, implementable agents, that is, those which have actually been constructed or are at least in principle implementable. That goal cannot be reached if the inherent resource-boundedness of agents is not treated correctly. Since the modal approach to epistemic logic is not suited to formalize resource-bounded reasoning, the issue of resource-boundedness remains one of the main foundational problems of any agent theory that is developed on the basis of modal epistemic logic. My work is an attempt to provide theories of agency with a more adequate epistemic foundation. It aims at developing theories of mental concepts that make much more realistic assumptions about agents than other theories. The guiding principle of my theory is that the capacities attributed to agents must be empirically verifiable, that is, it must be possible to construct artificial agents which satisfy the specifications determined by the theory. As a consequence, the unrealistic assumption that agents have unlimited reasoning capacities must be rejected. To achieve the goal of describing resource-bounded agents accurately, the cost of reasoning must be taken seriously. In the thesis I have developed a framework for modeling the relationship between knowledge, reasoning, and the availability of resources. I have argued that the correct form of an axiom for epistemic logic should be: if an agent knows all premises of a valid inference rule and if he performs the right reasoning, then he will know the conclusion as well. Because reasoning requires resources, it cannot be safely assumed that the agent can compute his knowledge if he does not have enough resources to perform the required reasoning. I have demonstrated that on the basis of that idea, the problems of traditional approaches can be avoided and rich epistemic logics can be developed which can account adequately for our intuitions about knowledge.

The inadequacy of the usual possible world semantics of modal languages when the meaning of 'belief' is attached to the modal operator is discussed. Three other approaches are then investigated. In the case of Moore's autoepistemic logic it becomes possible to compare an agent's beliefs to 'reality', which cannot be done directly in the possible world semantics. Levesque's semantics makes explicit in the object language the notion of 'this is all the information the agent has', which plays an important role in nonmonotonic reasoning. Both of these approaches deal with ideal reasoners. The third approach, Konolige's deduction model, is based on a semantics capable of describing the beliefs of one or more resourcebounded agents. Finally, the AGM postulates for belief revision are discussed. / Computer Science / M.Sc. (Computer Science)

The inadequacy of the usual possible world semantics of modal languages when the meaning of 'belief' is attached to the modal operator is discussed. Three other approaches are then investigated. In the case of Moore's autoepistemic logic it becomes possible to compare an agent's beliefs to 'reality', which cannot be done directly in the possible world semantics. Levesque's semantics makes explicit in the object language the notion of 'this is all the information the agent has', which plays an important role in nonmonotonic reasoning. Both of these approaches deal with ideal reasoners. The third approach, Konolige's deduction model, is based on a semantics capable of describing the beliefs of one or more resourcebounded agents. Finally, the AGM postulates for belief revision are discussed. / Computer Science / M.Sc. (Computer Science)