A prediction market is a special type of market which offers trades for securities associated with future states that are observable at a certain time in the future. Recently, prediction markets have shown the promise of being an abstract framework for designing distributed, scalable and self-incentivized machine learning systems which could then apply to large scale problems. However, existing designs of prediction markets are far from achieving such machine learning goal, due to (1) the limited belief modelling power and also (2) an inadequate understanding of the market dynamics. This work is thus motivated by improving and extending current prediction market design in both aspects. This research is focused on potential based prediction markets, that is, prediction markets that are administered by potential (or cost function) based market makers (PMM). To improve the market’s modelling power, we first propose the partially-observable potential based market maker (PoPMM), which generalizes the standard PMM such that it allows securities to be defined and evaluated on future states that are only partially-observable, while also maintaining the key properties of the standard PMM. Next, we complete and extend the theory of generalized exponential families (GEFs), and use GEFs to free the belief models encoded in the PMM/PoPMM from always being in exponential families. To have a better understanding of the market dynamics and its link to model learning, we discuss the market equilibrium and convergence in two main settings: convergence driven by traders, and convergence driven by the market maker. In the former case, we show that a market-wise objective will emerge from the traders’ personal objectives and will be optimized through traders’ selfish behaviours in trading. We then draw intimate links between the convergence result to popular algorithms in convex optimization and machine learning. In the latter case, we augment the PMM with an extra belief model and a bid-ask spread, and model the market dynamics as an optimal control problem. This convergence result requires no specific models on traders, and is suitable for understanding the markets involving less controllable traders.

Em Aprendizado de Máquina - AM não existe um único algoritmo que é sempre melhor para todos os domínios de aplicação. Na prática, diversas pesquisas mostram que Redes Neurais Artificiais - RNAs têm um 'bias' indutivo apropriado para diversos domínios. Em razão disso, RNAs têm sido aplicadas na resolução de vários problemas com desempenho satisfatório. Sistemas de AM simbólico possuem um 'bias' indutivo menos flexível do que as RNAs. Enquanto que as RNAs são capazes de aprender qualquer função, sistemas de AM simbólico geralmente aprendem conceitos que podem ser descritos na forma de hiperplanos. Por outro lado, sistemas de AM simbólico representam o conceito induzido por meio de estruturas simbólicas, as quais são geralmente compreensíveis pelos seres humanos. Assim, sistemas de AM simbólico são preferíveis quando é essencial a compreensibilidade do conceito induzido. RNAs carecem da capacidade de explicar suas decisões, uma vez que o conhecimento é codificado na forma de valores de seus pesos e 'thresholds'. Essa codificação é difícil de ser interpretada por seres humanos. Em diversos domínios de aplicação, tal como aprovação de crédito e diagnóstico médico, prover uma explicação sobre a classificação dada a um determinado caso é de crucial importância. De um modo similar, diversos usuários de sistemas de AM simbólico desejam validar o conhecimento induzido, com o objetivo de assegurar que a generalização feita pelo algoritmo é correta. Para que RNAs sejam aplicadas em um maior número de domínios, diversos pesquisadores têm proposto métodos para extrair conhecimento compreensível de RNAs. As principais contribuições desta tese são dois métodos que extraem conhecimento simbólico de RNAs. Os métodos propostos possuem diversas vantagens sobre outros métodos propostos previamente, tal como ser aplicáveis a qualquer arquitetura ou algoritmo de aprendizado de RNAs supervisionadas. O primeiro método proposto utiliza sistemas de AM simbólico para extrair conhecimento de RNAs, e o segundo método proposto estende o primeiro, combinado o conhecimento induzido por diversos sistemas de AM simbólico por meio de um Algoritmo Genético - AG. Os métodos propostos são analisados experimentalmente em diversos domínios de aplicação. Ambos os métodos são capazes de extrair conhecimento simbólico com alta fidelidade em relação à RNA treinada. Os métodos propostos são comparados com o método TREPAN, apresentando resultados promissores. TREPAN é um método bastante conhecido para extrair conhecimento de RNAs. / In Machine Learning - ML there is not a single algorithm that is the best for all application domains. In practice, several research works have shown that Artificial Neural Networks - ANNs have an appropriate inductive bias for several domains. Thus, ANNs have been applied to a number of data sets with high predictive accuracy. Symbolic ML algorithms have a less flexible inductive bias than ANNs. While ANNs can learn any input-output mapping, i.e., ANNs have the universal approximation property, symbolic ML algorithms frequently learn concepts describing them using hyperplanes. On the other hand, symbolic algorithms are needed when a good understating of the decision process is essential, since symbolic ML algorithms express the knowledge induced using symbolic structures that can be interpreted and understood by humans. ANNs lack the capability of explaining their decisions since the knowledge is encoded as real-valued weights and biases of the network. This encoding is difficult to be interpreted by humans. In several application domains, such as credit approval and medical diagnosis, providing an explanation related to the classification given to a certain case is of crucial importance. In a similar way, several users of ML algorithms desire to validate the knowledge induced, in order to assure that the generalization made by the algorithm is correct. In order to apply ANNs to a larger number of application domains, several researches have proposed methods to extract comprehensible knowledge from ANNs. The primary contribution of this thesis consists of two methods that extract symbolic knowledge, expressed as decision rules, from ANNs. The proposed methods have several advantages over previous methods, such as being applicable to any architecture and supervised learning algorithm of ANNs. The first method uses standard symbolic ML algorithm to extract knowledge from ANNs, and the second method extends the first method by combining the knowledge induced by several symbolic ML algorithms through the application of a Genetic Algorithm - GA. The proposed methods are experimentally analyzed in a number of application domains. Results show that both methods are capable to extract symbolic knowledge having high fidelity with trained ANNs. The proposed methods are compared with TREPAN, showing promising results. TREPAN is a well known method to extract knowledge from ANNs.

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Bioengineering, Biomedical Engineering, 2009. / Includes bibliographical references.

Em Aprendizado de Máquina - AM não existe um único algoritmo que é sempre melhor para todos os domínios de aplicação. Na prática, diversas pesquisas mostram que Redes Neurais Artificiais - RNAs têm um 'bias' indutivo apropriado para diversos domínios. Em razão disso, RNAs têm sido aplicadas na resolução de vários problemas com desempenho satisfatório. Sistemas de AM simbólico possuem um 'bias' indutivo menos flexível do que as RNAs. Enquanto que as RNAs são capazes de aprender qualquer função, sistemas de AM simbólico geralmente aprendem conceitos que podem ser descritos na forma de hiperplanos. Por outro lado, sistemas de AM simbólico representam o conceito induzido por meio de estruturas simbólicas, as quais são geralmente compreensíveis pelos seres humanos. Assim, sistemas de AM simbólico são preferíveis quando é essencial a compreensibilidade do conceito induzido. RNAs carecem da capacidade de explicar suas decisões, uma vez que o conhecimento é codificado na forma de valores de seus pesos e 'thresholds'. Essa codificação é difícil de ser interpretada por seres humanos. Em diversos domínios de aplicação, tal como aprovação de crédito e diagnóstico médico, prover uma explicação sobre a classificação dada a um determinado caso é de crucial importância. De um modo similar, diversos usuários de sistemas de AM simbólico desejam validar o conhecimento induzido, com o objetivo de assegurar que a generalização feita pelo algoritmo é correta. Para que RNAs sejam aplicadas em um maior número de domínios, diversos pesquisadores têm proposto métodos para extrair conhecimento compreensível de RNAs. As principais contribuições desta tese são dois métodos que extraem conhecimento simbólico de RNAs. Os métodos propostos possuem diversas vantagens sobre outros métodos propostos previamente, tal como ser aplicáveis a qualquer arquitetura ou algoritmo de aprendizado de RNAs supervisionadas. O primeiro método proposto utiliza sistemas de AM simbólico para extrair conhecimento de RNAs, e o segundo método proposto estende o primeiro, combinado o conhecimento induzido por diversos sistemas de AM simbólico por meio de um Algoritmo Genético - AG. Os métodos propostos são analisados experimentalmente em diversos domínios de aplicação. Ambos os métodos são capazes de extrair conhecimento simbólico com alta fidelidade em relação à RNA treinada. Os métodos propostos são comparados com o método TREPAN, apresentando resultados promissores. TREPAN é um método bastante conhecido para extrair conhecimento de RNAs. / In Machine Learning - ML there is not a single algorithm that is the best for all application domains. In practice, several research works have shown that Artificial Neural Networks - ANNs have an appropriate inductive bias for several domains. Thus, ANNs have been applied to a number of data sets with high predictive accuracy. Symbolic ML algorithms have a less flexible inductive bias than ANNs. While ANNs can learn any input-output mapping, i.e., ANNs have the universal approximation property, symbolic ML algorithms frequently learn concepts describing them using hyperplanes. On the other hand, symbolic algorithms are needed when a good understating of the decision process is essential, since symbolic ML algorithms express the knowledge induced using symbolic structures that can be interpreted and understood by humans. ANNs lack the capability of explaining their decisions since the knowledge is encoded as real-valued weights and biases of the network. This encoding is difficult to be interpreted by humans. In several application domains, such as credit approval and medical diagnosis, providing an explanation related to the classification given to a certain case is of crucial importance. In a similar way, several users of ML algorithms desire to validate the knowledge induced, in order to assure that the generalization made by the algorithm is correct. In order to apply ANNs to a larger number of application domains, several researches have proposed methods to extract comprehensible knowledge from ANNs. The primary contribution of this thesis consists of two methods that extract symbolic knowledge, expressed as decision rules, from ANNs. The proposed methods have several advantages over previous methods, such as being applicable to any architecture and supervised learning algorithm of ANNs. The first method uses standard symbolic ML algorithm to extract knowledge from ANNs, and the second method extends the first method by combining the knowledge induced by several symbolic ML algorithms through the application of a Genetic Algorithm - GA. The proposed methods are experimentally analyzed in a number of application domains. Results show that both methods are capable to extract symbolic knowledge having high fidelity with trained ANNs. The proposed methods are compared with TREPAN, showing promising results. TREPAN is a well known method to extract knowledge from ANNs.

Le raisonnement, la capacité de tirer des conclusions logiques à partir de connaissances existantes, est une caractéristique marquante de l’être humain. Avec la perception, ils constituent les deux thèmes majeurs de l’intelligence artificielle. Alors que l’apprentissage profond a repoussé les limites de la perception au-delà des performances humaines en vision par ordinateur et en traitement du langage naturel, les progrès dans les domaines du raisonnement sont loin derrière. L’une des raisons fondamentales est que les problèmes de raisonnement ont généralement des structures flexibles à la fois pour les connaissances (par exemple, les graphes de connaissances) et les requêtes (par exemple, les requêtes en plusieurs étapes), et de nombreux modèles existants ne fonctionnent bien que sur les structures vues pendant l’entraînement. Dans cette thèse, nous visons à repousser les limites des modèles de raisonnement en concevant des algorithmes qui généralisent à travers les structures de connaissances et de requêtes, ainsi que des systèmes qui accélèrent le développement sur des données structurées. Cette thèse est composée de trois parties. Dans la partie I, nous étudions des modèles qui peuvent généraliser de manière inductive à des graphes de connaissances invisibles, qui impliquent de nouveaux vocabulaires d’entités et de relations. Pour les nouvelles entités, nous proposons un nouveau cadre qui apprend les opérateurs neuronaux dans un algorithme de programmation dynamique calculant des représentations de chemin. Ce cadre peut être étendu à des graphes de connaissances à l’échelle d’un million en apprenant une fonction de priorité. Pour les relations, nous construisons un graphe de relations pour capturer les interactions entre les relations, convertissant ainsi les nouvelles relations en nouvelles entités. Cela nous permet de développer un modèle pré-entraîné unique pour des graphes de connaissances arbitraires. Dans la partie II, nous proposons deux solutions pour généraliser les requêtes en plusieurs étapes sur les graphes de connaissances et sur le texte respectivement. Pour les graphes de connaissances, nous montrons que les requêtes en plusieurs étapes peuvent être résolues par plusieurs appels de réseaux neuronaux graphes et d’opérations de logique floue. Cette conception permet la généralisation à de nouvelles entités, et peut être intégrée à notre modèle pré-entraîné pour prendre en charge des graphes de connaissances arbitraires. Pour le texte, nous concevons un nouvel algorithme pour apprendre des connaissances explicites sous forme de règles textuelles afin d’améliorer les grands modèles de langage sur les requêtes en plusieurs étapes. Dans la partie III, nous proposons deux systèmes pour faciliter le développement de l’apprentissage automatique sur des données structurées. Notre bibliothèque open source traite les données structurées comme des citoyens de première classe et supprime la barrière au développement d’algorithmes d’apprentissage automatique sur des données structurées, y compris des graphes, des molécules et des protéines. Notre système d’intégration de noeuds résout le goulot d’étranglement de la mémoire GPU des matrices d’intégration et s’adapte aux graphes avec des milliards de noeuds. / Reasoning, the ability to logically draw conclusions from existing knowledge, is a hallmark of human. Together with perception, they constitute the two major themes of artificial intelligence. While deep learning has pushed the limit of perception beyond human-level performance in computer vision and natural language processing, the progress in reasoning domains is way behind. One fundamental reason is that reasoning problems usually have flexible structures for both knowledge (e.g. knowledge graphs) and queries (e.g. multi-step queries), and many existing models only perform well on structures seen during training. In this thesis, we aim to push the boundary of reasoning models by devising algorithms that generalize across knowledge and query structures, as well as systems that accelerate development on structured data. This thesis is composed of three parts. In Part I, we study models that can inductively generalize to unseen knowledge graphs, which involve new entity and relation vocabularies. For new entities, we propose a novel framework that learns neural operators in a dynamic programming algorithm computing path representations. This framework can be further scaled to million-scale knowledge graphs by learning a priority function. For relations, we construct a relation graph to capture the interactions between relations, thereby converting new relations into new entities. This enables us to develop a single pre-trained model for arbitrary knowledge graphs. In Part II, we propose two solutions for generalizing across multi-step queries on knowledge graphs and text respectively. For knowledge graphs, we show multi-step queries can be solved by multiple calls of graph neural networks and fuzzy logic operations. This design enables generalization to new entities, and can be integrated with our pre-trained model to accommodate arbitrary knowledge graphs. For text, we devise a new algorithm to learn explicit knowledge as textual rules to improve large language models on multi-step queries. In Part III, we propose two systems to facilitate machine learning development on structured data. Our open-source library treats structured data as first-class citizens and removes the barrier for developing machine learning algorithms on structured data, including graphs, molecules and proteins. Our node embedding system solves the GPU memory bottleneck of embedding matrices and scales to graphs with billion nodes.