Amorphous membrane blending

Christof Teuscher
EPFL, 2004
Thèse EPFL

Résumé

The von Neumann architecture was first expressed in 1945 and has largely dominated in many variants and refinements computer science for more than half a century. Alternative architectures always occupied a marginal place only, despite a growing need for new concepts and paradigms in computer science. Biologically-inspired engineering applies biological concepts to the design of novel computing machines and algorithms. This can lead to the creation of new machines, endowed with properties usually associated with the living world: adaptation, evolution, growth and development, fault-tolerance, self-replication or cloning, reproduction, etc. Most of these approaches are based on well established theories such as artificial neural networks, evolutionary algorithms, and cellular automata. The work presented in this thesis takes an alternative path and proposes concepts for novel and unconventional biologically-inspired machines. The approach is mainly motivated by the insight that tomorrow's computational substrates and environments might be very different from what we know today. Some of tomorrow's computers might be embedded in the paint that covers your desk or printed on a sheet of paper by means of a special ink. Most of such pervasive computing concepts have some common elements: (1) the computer's basic elements are very simple, identical, and available in a huge number, (2) the interactions between the elements are purely local, (3) the elements as well as the interconnections are unreliable, and (4) there is no global control mechanism available. This thesis is mainly based on the unification of the following three domains of research: (1) amorphous computing, (2) membrane systems, and (3) blending. An amorphous computer is a massive parallel machine made up of myriads of simple, unreliable, and identical elements, distributed randomly on a surface and interconnected locally by unreliable connections. Membrane systems are theoretical models inspired by biochemistry-based on regions bounded by membranes. The hierarchical membrane structures contain artificial chemistries, consisting in objects and reactions, which allow to do computations. Blending is a framework of cognitive science which tries to explain how we deal with mental concepts and how creative thinking emerges. First, an introduction of traditional bio-inspired machines and hardware is provided. This part also includes the presentation of a first implementation of a membrane system on reconfigurable hardware and a description of the cellular automata machine entitled BioWall, with its applications. Random boolean networks as well as several theoretical considerations and practical results are then used to introduce irregular computational structures. The C-Blending approach represents an novel computational blending method intended for membrane systems and artificial chemistries. In order to implement membrane systems on amorphous computers, the Circuit Amorphous Computer as well as special membrane systems, termed aP and aB membrane systems, are proposed. The ultimate concept proposed and studied consists in a unification of membrane systems, amorphous computers, and computational C-Blending. The unification of the three concepts results in several interesting properties. The cellular structures allow to create dynamical hierarchies and growing systems whereas the artificial chemistries represent an ideal mean to compute on the potentially imperfect and irregular hardware of an amorphous computer. Finally, the computational blending proposed describes an inventive method to create, organize, and adapt membrane systems. The characteristics and limits of the concepts proposed are analyzed and validated using various examples and toy applications. The thesis concludes with the definition of the Circuit Amorphous Computer and the Amorphon architecture, which might constitute the minimal element of tomorrow's computing machines.

Official source

https://infoscience.epfl.ch/record/33400?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Christof Teuscher
EPFL, 2004
Thèse EPFL

Résumé

Official source

https://infoscience.epfl.ch/record/33400?ln=fr

À propos de ce résultat

Concepts associés (44)

Une thèse (du nom grec thesis, se traduisant par « action de poser ») est une affirmation ou prise de position d'un locuteur, à l'égard du sujet ou du thème qu'il évoque. Au sens philosophique

Un ordinateur est un système de traitement de l'information programmable tel que défini par Alan Turing et qui fonctionne par la lecture séquentielle d'un ensemble d'instructions, organisées en progr

alt=Salle informatique de la bibliothèque d'Art et d'Archéologie de Genève|vignette|Salle informatique de la bibliothèque d'Art et d'Archéologie de Genève (2017). L'informatique est un domaine d'acti

Afficher plus

Concepts associés

Chargement

Publications associées (12)

Publications associées

Chargement

Signaling and Reciprocity

Wojciech Galuba

Complex networks exist for a number of purposes. The neural, metabolic and food networks ensure our survival, while the social, economic, transportation and communication networks allow us to prosper. Independently of the purposes and particularities of the physical embodiment of the networks, one of their fundamental functions is the delivery of information from one part of the network to another. Gossip and diseases diffuse in the social networks, electrochemical signals propagate in the neural networks and data packets travel in the Internet. Engineering networks for robust information flows is a challenging task. First, the mechanism through which the network forms and changes its topology needs to be defined. Second, within a given topology, the information must be routed to the appropriate recipients. Third, both the network formation and the routing mechanisms need to be robust against a wide spectrum of failures and adversaries. Fourth, the network formation, routing and failure recovery must operate under the resource constraints, either intrinsic or extrinsic to the network. Finally, the autonomously operating parts of the network must be incentivized to contribute their resources to facilitate the information flows. This thesis tackles the above challenges within the context of several types of networks: 1) peer-to-peer overlays – computers interconnected over the Internet to form an overlay in which participants provide various services to one another, 2) mobile ad-hoc networks – mobile nodes distributed in physical space communicating wirelessly with the goal of delivering data from one part of the network to another, 3) file-sharing networks – networks whose participants interconnect over the Internet to exchange files, 4) social networks – humans disseminating and consuming information through the network of social relationships. The thesis makes several contributions. Firstly, we propose a general algorithm, which given a set of nodes embedded in an arbitrary metric space, interconnects them into a network that efficiently routes information. We apply the algorithm to the peer-to-peer overlays and experimentally demonstrate its high performance, scalability as well as resilience to continuous peer arrivals and departures. We then shift our focus to the problem of the reliability of routing in the peer-to-peer overlays. Each overlay peer has limited resources and when they are exhausted this ultimately leads to delayed or lost overlay messages. All the solutions addressing this problem rely on message redundancy, which significantly increases the resource costs of fault-tolerance. We propose a bandwidth-efficient single-path Forward Feedback Protocol (FFP) for overlay message routing in which successfully delivered messages are followed by a feedback signal to reinforce the routing paths. Internet testbed evaluation shows that FFP uses 2-5 times less network bandwidth than the existing protocols relying on message redundancy, while achieving comparable fault-tolerance levels under a variety of failure scenarios. While the Forward Feedback Protocol is robust to message loss and delays, it is vulnerable to malicious message injection. We address this and other security problems by proposing Castor, a variant of FFP for mobile ad-hoc networks (MANETs). In Castor, we use the same general mechanism as in FFP; each time a message is routed, the routing path is either enforced or weakened by the feedback signal depending on whether the routing succeeded or not. However, unlike FFP, Castor employs cryptographic mechanisms for ensuring the integrity and authenticity of the messages. We compare Castor to four other MANET routing protocols. Despite Castor's simplicity, it achieves up to 40% higher packet delivery rates than the other protocols and recovers at least twice as fast as the other protocols in a wide range of attacks and failure scenarios. Both of our protocols, FFP and Castor, rely on simple signaling to improve the routing robustness in peer-to-peer and mobile ad-hoc networks. Given the success of the signaling mechanism in shaping the information flows in these two types of networks, we examine if signaling plays a similar crucial role in the on-line social networks. We characterize the propagation of URLs in the social network of Twitter. The data analysis uncovers several statistical regularities in the user activity, the social graph, the structure of the URL cascades as well as the communication and signaling dynamics. Based on these results, we propose a propagation model that accurately predicts which users are likely to mention which URLs. We outline a number of applications where the social network information flow modelling would be crucial: content ranking and filtering, viral marketing and spam detection. Finally, we consider the problem of freeriding in peer-to-peer file-sharing applications, when users can download data from others, but never reciprocate by uploading. To address the problem, we propose a variant of the BitTorrent system in which two peers are only allowed to connect if their owners know one another in the real world. When the users know which other users their BitTorrent client connects to, they are more likely to cooperate. The social network becomes the content distribution network and the freeriding problem is solved by leveraging the social norms and reciprocity to stabilize cooperation rather than relying on technological means. Our extensive simulation shows that the social network topology is an efficient and scalable content distribution medium, while at the same time provides robustness to freeriding.

EPFL2011

Chargement

We are witnessing a rise in the popularity of using artificial neural networks in many fields of science and technology. Deep neural networks in particular have shown impressive classification performance on a number of challenging benchmarks, generally in well controlled settings. However it is equally important that these classifiers satisfy robustness guarantees when they are deployed in uncontrolled (noise-prone) and possibly hostile environments. In other words, small perturbations applied to the samples should not yield significant loss to the performance of the classifier. Unfortunately, deep neural network classifiers are shown to be intriguingly vulnerable to perturbations and it is relatively easy to design noise that can change the estimated label of the classifier. The study of this high-dimensional phenomenon is a challenging task, and requires the development of new algorithmic tools, as well as theoretical and experimental analysis in order to identify the key factors driving the robustness properties of deep networks. This is exactly the focus of this PhD thesis. First, we propose a computationally efficient yet accurate method to generate minimal perturbations that fool deep neural networks. It permits to reliably quantify the robustness of classifiers and compare different architectures. We further propose a systematic algorithm for computing universal (image-agnostic) and very small perturbation vectors that cause natural images to be misclassified with high probability. The vulnerability to universal perturbations is particularly important in security-critical applications of deep neural networks, and our algorithm shows that these systems are quite vulnerable to noise that is designed with only limited knowledge about test samples or classification architectures. Next, we study the geometry of the classifier's decision boundary in order to explain the adversarial vulnerability of deep networks. Specifically, we establish precise theoretical bounds on the robustness of classifiers in a novel semi-random noise regime that generalizes both the adversarial and the random perturbation regimes. We show in particular that the robustness of deep networks to universal perturbations is driven by a key property of the curvature of their decision boundaries. Finally, we build on the geometric insights derived in this thesis in order to improve the robustness properties of state-of-the-art image classifiers. We leverage a fundamental property in the curvature of the decision boundary of deep networks, and propose a method to detect small adversarial perturbations in images, and to recover the labels of perturbed images. To achieve inherently robust classifiers, we further propose an alternative to the common adversarial training strategy, where we directly minimize the curvature of the classifier. This leads to adversarial robustness that is on par with adversarial training. In summary, we demonstrate in this thesis a new geometric approach to the problem of the adversarial vulnerability of deep networks, and provide novel quantitative and qualitative results that precisely describe the behavior of classifiers in adversarial settings. Our results in this thesis contribute to the understanding of the fundamental properties of state-of-the-art image classifiers that eventually will bring important benefits in safety-critical applications such as in self-driving cars, autonomous robots, and medical imaging.

EPFL2019

Chargement

Machine Learning is a modern and actively developing field of computer science, devoted to extracting and estimating dependencies from empirical data. It combines such fields as statistics, optimization theory and artificial intelligence. In practical tasks, the general aim of Machine Learning is to construct algorithms able to generalize and predict in previously unseen situations based on some set of examples. Given some finite information, Machine Learning provides ways to exract knowledge, describe, explain and predict from data. Kernel Methods are one of the most successful branches of Machine Learning. They allow applying linear algorithms with well-founded properties such as generalization ability, to non-linear real-life problems. Support Vector Machine is a well-known example of a kernel method, which has found a wide range of applications in data analysis nowadays. In many practical applications, some additional prior knowledge is often available. This can be the knowledge about the data domain, invariant transformations, inner geometrical structures in data, some properties of the underlying process, etc. If used smartly, this information can provide significant improvement to any data processing algorithm. Thus, it is important to develop methods for incorporating prior knowledge into data-dependent models. The main objective of this thesis is to investigate approaches towards learning with kernel methods using prior knowledge. Invariant learning with kernel methods is considered in more details. In the first part of the thesis, kernels are developed which incorporate prior knowledge on invariant transformations. They apply when the desired transformation produce an object around every example, assuming that all points in the given object share the same class. Different types of objects, including hard geometrical objects and distributions are considered. These kernels were then applied for images classification with Support Vector Machines. Next, algorithms which specifically include prior knowledge are considered. An algorithm which linearly classifies distributions by their domain was developed. It is constructed such that it allows to apply kernels to solve non-linear tasks. Thus, it combines the discriminative power of support vector machines and the well-developed framework of generative models. It can be applied to a number of real-life tasks which include data represented as distributions. In the last part of the thesis, the use of unlabelled data as a source of prior knowledge is considered. The technique of modelling the unlabelled data with a graph is taken as a baseline from semi-supervised manifold learning. For classification problems, we use this apporach for building graph models of invariant manifolds. For regression problems, we use unlabelled data to take into account the inner geometry of the input space. To conclude, in this thesis we developed a number of approaches for incorporating some prior knowledge into kernel methods. We proposed invariant kernels for existing algorithms, developed new algorithms and adapted a technique taken from semi-supervised learning for invariant learning. In all these cases, links with related state-of-the-art approaches were investigated. Several illustrative experiments were carried out on real data on optical character recognition, face image classification, brain-computer interfaces, and a number of benchmark and synthetic datasets.

EPFL2006

Chargement

Signaling and Reciprocity

Wojciech Galuba

EPFL2011

EPFL2019

EPFL2006