230 research outputs found
« Problème ethnique », par le professeur Yaron Tsur. Traduction commentée par Yann Scioldo-Zürcher Levi
No full textThis article is a translation from Hebrew into French of the paper, famous among Israeli historians, “Ethnic Problem” by Professor Yaron Tsur. Looking at the first Jewish ethnic riots that took place in 1959 in the city of Haïfa, the author details both the chronology that led to the Eastern migrants imposing themselves in the political landscape of the State, but also the social-political processes that that had, until then, forced them to live on the margins of Israeli society. This annotated translation is aimed at readers interested in Israeli Area Studies, but also for those who interest in the way populations are “structured” by one State created in the second half of the twentieth centur
Recommended from our members
Capitalism vs Socialism Debate
No full textWatch Yaron Brook - Chairman of the Board, Ayn Rand Institute - and Bhaskar Sunkara - Author of “The Socialist Manifesto: The Case for Radical Politics in an Era of Extreme Inequality”- debating about the merits and prospects of Capitalism and Socialism.Salem Cente
Recommended from our members
Universal Noise Models in Machine Learning
No full textWe examine the problem of universal noise models in machine learning
Recommended from our members
Scalability and Performance of Intractable Optimization Problems in Machine Learning
No full textIn this thesis, we study the scalability and performance of combinatorial optimization problems in machine learning. Paradigms such as feature selection, text summarization, and sparse recovery are all examples of machine learning techniques, where an algorithm is given a large set of inputs and must efficiently select an optimal subset to optimize a certain objective. These optimization problems are key components in machine learning algorithms that take in examples and construct a hypothesis about the structure in the underlying data.
For machine learning to advance, algorithms need to process and learn from large amounts of data. However, algorithms for machine learning problems, such as clustering, sparse recovery, and maximum likelihood estimation, require solving combinatorial optimization problems, which are often provably computationally intractable and practically infeasible at large, and even moderate scale. In this thesis, we study and advance the computation frontier of machine learning paradigms with a focus on problems with submodular structure. We study two possible approaches, parallelization and heuristics, that are used to deal with computationally intensive problems.
In our first line of work, we study the theoretical and empirical possibilities of parallelization. More specifically, we propose parallel algorithms with strong theoretical and empirical performance for machine learning problems. We show various applications of these algorithms in statistical subset selection problems, natural language processing, and online markets.
In our second line of work, we study theoretical guarantees of heuristics used for computationally intractable machine learning problems. Specifically, we provide a novel theoretical framework to understand empirical performance of machine learning techniques. Using our proposed framework, we are able to efficiently show that learning heuristics that are used in practice and guaranteed to only be within ~63% of optimal are actually within 95% of optimal, thus suggesting a 50% improvement over existing theoretical guarantees
Recommended from our members
From Social Data to Neural Networks: Robust Decision-Making in Machine Learning
No full textIn this thesis we develop algorithms to control and understand the behavior of a system despite erroneous, noisy or otherwise problematic input. In our first line of work, we focus on the decision-making for social data pipeline that usually consists of three steps: (1) collect and label relevant data, (2) learn a surrogate model representing the real world as accurately as possible, and (3) perform optimization/decision-making on the surrogate model. We begin by tackling the first problem, showing how to aggregate labels and reduce uncertainty in crowdsourcing platforms. The data collected from crowdsourcing is often noisy and hence may yield models that are biased or erroneous. We present a graphical model to aggregate the different labelers' decisions and estimate their uncertainty. This allows us to utilize reviewers more efficiently and improve the quality of our data. Subsequently, we focus on the next two steps of the pipeline and use information dissemination in social networks as a case study, ultimately aiming to design robust algorithms for that problem. We propose a new hyperparametric model that utilizes information about the nodes of the social graph and allows us to approximately maximize the number of nodes that are will be influenced under the worst possible choice of the hyperparameter (on expectation). This accounts for errors introduced during learning the model from data of past cascades, i.e. observations of how does diffusion propagate among the nodes of the network.
In the second part of the thesis, we focus on neural networks that have been in the frontline of the machine learning revolution we have been observing over the last few years. We investigate the connections between robustness and interpretability for genomic datasets and finally, try to shed some light upon the generalization behavior of neural networks by studying the implicit bias of Stochastic Gradient Descent (SGD), i.e. the underlying reason why we are able to recover generalizable solutions in modern overparametrized networks, by claiming that neural networks trained with SGD learn functions of increasing complexity as training progresses. That is, they learn meaningful correlations with the data and retain them throughout the training process, even after overfitting to the noise in the dataset
Recommended from our members
Exponentially Faster Submodular Maximization in Practice via Low Adaptivity Algorithms
No full textAcross machine learning, social network analysis, and algorithms, many fundamental objectives we care to optimize are submodular, such as influence, innovation diffusion, clustering, mutual information, feature selection, and data summarization. Whereas typical applications across these domains include problem instances defined on massive data sets, maximizing a submodular function subject to a cardinality constraint is NP-hard, and current state-of-the-art serial algorithms achieve an optimal approximation only after a number of queries that is linearly increasing in the size of the data.
Recently, there has been a great deal of research on parallel algorithms whose theoretical runtime on an idealized parallel machine is exponentially faster than algorithms used for submodular maximization over the past 40 years. However, it is computationally infeasible to use these algorithms in practice even on small data sets because the non-asymptotic number of iterations and queries they require depend on large constants and high-degree polynomials in terms of the precision and confidence of their approximations.
This dissertation describes a new parallel algorithm called Fast Adaptive Sequencing Technique (Fast) for maximizing a monotone submodular function under a cardinality constraint k. The design principles behind the Fast algorithm are a significant departure from those of recent theoretically fast algorithms. These design principles yield theoretic guarantees that are competitive with recent theoretically fast algorithms, but practical performance that is orders of magnitude faster than state-of-the-art algorithms used in practice. Specifically, Fast obtains an approximation that is arbitrarily close to the optimal 1 − 1/e guarantee in an asymptotic parallel runtime (adaptivity) that is O(log(n) log^2(log k)) using O(n log log(k)) total queries. In terms of practical parallel runtimes, we show that Fast is orders of magnitude faster than any known algorithm for submodular maximization, including hyper-optimized parallel versions of state-of-the-art serial algorithms, by running experiments on large data sets
Recommended from our members
Incentives, Computation, and Networks: Limitations and Possibilities of Algorithmic Mechanism Design
No full textIn the past decade, a theory of manipulation-robust algorithms has been emerging to address the challenges that frequently occur in strategic environments such as the internet. The theory, known as algorithmic mechanism design, builds on the foundations of classical mechanism design from microeconomics and is based on the idea of incentive compatible protocols. Such protocols achieve system-wide objectives through careful design that ensures it is in every agent's best interest to comply with the protocol. As it turns out, however, implementing incentive compatible protocols as advocated in classical mechanism design theory often necessitates solving intractable problems. To address this, algorithmic mechanism design focuses on designing computationally-feasible incentive compatible approximation algorithms. In the first part of this thesis we show the limitations of algorithmic mechanism design. We introduce a novel class of problems which are approximable in the absence of strategic constraints, and have an optimal incentive compatible solution when no computational constraints are enforced; we show that for this class of problems there is no algorithm with a reasonable approximation ratio that is both computationally feasible and incentive compatible. This settles the central open question in algorithmic mechanism design which, since its inception, has been focused on trying to show the hardness of polynomial time incentive compatibility. In the second part of this thesis we show the possibilities of algorithmic mechanism design. We introduce a novel class of problems where the bottleneck for implementation is the constraint on payments. We show that for a broad class of these problems, there are incentive compatible mechanisms with desirable approximation guarantees that do not require overpayments. By resulting to approximations, this result circumvents well known impossibility results from classical mechanism design theory that deem incentive compatibility to be infeasible under a budget
How to win friends and influence people, truthfully: influence maximization mechanisms for social networks
No full textThroughout the past decade there has been extensive re-search on algorithmic and data mining techniques for solving the problem of influence maximization in social networks: if one can incentivize a subset of individuals to become early adopters of a new technology, which subset should be se-lected so that the word-of-mouth effect in the social network is maximized? Despite the progress in modeling and tech-niques, the incomplete information aspect of the problem has been largely overlooked. While data can often provide the network structure and influence patterns may be ob-servable, the inherent cost individuals have to become early adopters is difficult to extract. In this paper we introduce mechanisms that elicit individ-uals ’ costs while providing desirable approximation guaran-tees in some of the most well-studied models of social net-work influence. We follow the mechanism design framework which advocates for allocation and payment schemes that incentivize individuals to report their true information. We also performed experiments using the Mechanical Turk plat-form and social network data to provide evidence of the framework’s effectiveness in practice
- …
