consider:looking-to-see   679

« earlier    

[1803.01422] DAGs with NO TEARS: Smooth Optimization for Structure Learning
Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint and are not well-suited to general purpose optimization packages for their solution. In this paper, we introduce a fundamentally different strategy: We formulate the structure learning problem as a smooth, constrained optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting nonconvex, constrained program involves smooth functions whose gradients are easy to compute and only involve elementary matrix operations. By using existing black-box optimization routines, our method uses global search to find an optimal DAG and can be implemented in about 50 lines of Python and outperforms existing methods without imposing any structural constraints.
graph-theory  combinatorics  algorithms  rather-interesting  computational-complexity  to-understand  to-write-about  nudge-targets  consider:looking-to-see  representation 
18 days ago by Vaguery
[1801.00663] A Sharp Estimate for Probability Distributions
We consider absolutely continuous probability distributions f(x)dx on ℝ≥0. A result of Feldheim and Feldheim shows, among other things, that if the distribution is not compactly supported, then there exist z>0 such that most events in {X+Y≥2z} are comprised of a 'small' term satisfying min(X,Y)≤z and a 'large' term satisfying max(X,Y)≥z (as opposed to two 'large' terms that are both larger than z)
limsupz→∞ ℙ(min(X,Y)≤z|X+Y≥2z)=1.
The result fails if the distribution is compactly supported. We prove
supz>0 ℙ(min(X,Y)≤z|X+Y≥2z)≥124+8log2(med(X)‖f‖L∞),
where med(X) denotes the median. Interestingly, the logarithm is necessary and the result is sharp up to constants; we also discuss some open problems.
probability-theory  statistics  rather-interesting  nudge-targets  consider:looking-to-see 
24 days ago by Vaguery
A hybrid placement strategy for the three-dimensional strip packing problem - ScienceDirect
This paper presents a hybrid placement strategy for the three-dimensional strip packing problem which involves packing a set of cuboids (‘boxes’) into a three-dimensional bin (parallelepiped) of fixed width and height but unconstrained length (the ‘container’). The goal is to pack all of the boxes into the container, minimising its resulting length. This problem has potential industry application in stock cutting (wood, polystyrene, etc. – minimising wastage) and also cargo loading, as well as other applications in areas such as multi-dimensional resource scheduling. In addition to the proposed strategy a number of test results on available literature benchmark problems are presented and analysed. The results of empirical testing of the algorithm show that it out-performs other methods from the literature, consistently in terms of speed and solution quality-producing 28 best known results from 35 test cases.
operations-research  hyperheuristics  metaheuristics  optimization  constraint-satisfaction  nudge-targets  consider:representation  consider:looking-to-see  to-write-about 
5 weeks ago by Vaguery
[1712.08373] Notes on complexity of packing coloring
A packing k-coloring for some integer k of a graph G=(V,E) is a mapping
φ:V→{1,…,k} such that any two vertices u,v of color φ(u)=φ(v) are in distance at least φ(u)+1. This concept is motivated by frequency assignment problems. The \emph{packing chromatic number} of G is the smallest k such that there exists a packing k-coloring of G.
Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is \NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show \NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n1/2−ε for any ε>0.
In addition, we design an \FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
graph-theory  algorithms  combinatorics  proof  approximation  nudge-targets  consider:looking-to-see  consider:feature-discovery 
5 weeks ago by Vaguery
[1711.03532] Co-Optimization Generation and Distribution Planning in Microgrids
This paper proposes a co-optimization generation and distribution planning model in microgrids in which simultaneous investment in generation, i.e., distributed generation (DG) and distributed energy storage (DES), and distribution, i.e., upgrading the existing distribution network, is considered. The objective of the proposed model is to minimize the microgrid total planning cost which comprises the investment cost of installed generation assets and lines, the microgrid operation cost, and the cost of unserved energy. The microgrid planning solution determines the optimal generation size, location, and mix, as well as required network upgrade. To consider line flow and voltage limits, a linearized power flow model is proposed and used, allowing further application of mixed integer linear programming (MILP) in problem modeling. The proposed model is applied to the IEEE 33-bus standard test system to demonstrate the acceptable performance and the effectiveness of the proposed model.
optimization  network-theory  mathematical-programming  multiobjective-optimization  rather-interesting  operations-research  utilities  nudge-targets  consider:looking-to-see 
5 weeks ago by Vaguery
[1801.01922] Vectorization of Line Drawings via PolyVector Fields
Image tracing is a foundational component of the workflow in graphic design, engineering, and computer animation, linking hand-drawn concept images to collections of smooth curves needed for geometry processing and editing. Even for clean line drawings, modern algorithms often fail to faithfully vectorize junctions, or points at which curves meet; this produces vector drawings with incorrect connectivity. This subtle issue undermines the practical application of vectorization tools and accounts for hesitance among artists and engineers to use automatic vectorization software. To address this issue, we propose a novel image vectorization method based on state-of-the-art mathematical algorithms for frame field processing. Our algorithm is tailored specifically to disambiguate junctions without sacrificing quality.
graphics  algorithms  inference  rather-interesting  feature-construction  nudge-targets  consider:representation  consider:looking-to-see  consider:performance-measures 
5 weeks ago by Vaguery
[1709.06217] Deterministic meeting of sniffing agents in the plane
Two mobile agents, starting at arbitrary, possibly different times from arbitrary locations in the plane, have to meet. Agents are modeled as discs of diameter 1, and meeting occurs when these discs touch. Agents have different labels which are integers from the set of 0 to L-1. Each agent knows L and knows its own label, but not the label of the other agent. Agents are equipped with compasses and have synchronized clocks. They make a series of moves. Each move specifies the direction and the duration of moving. This includes a null move which consists in staying inert for some time, or forever. In a non-null move agents travel at the same constant speed, normalized to 1. We assume that agents have sensors enabling them to estimate the distance from the other agent (defined as the distance between centers of discs), but not the direction towards it. We consider two models of estimation. In both models an agent reads its sensor at the moment of its appearance in the plane and then at the end of each move. This reading (together with the previous ones) determines the decision concerning the next move. In both models the reading of the sensor tells the agent if the other agent is already present. Moreover, in the monotone model, each agent can find out, for any two readings in moments t1 and t2, whether the distance from the other agent at time t1 was smaller, equal or larger than at time t2. In the weaker binary model, each agent can find out, at any reading, whether it is at distance less than \r{ho} or at distance at least \r{ho} from the other agent, for some real \r{ho} > 1 unknown to them. Such distance estimation mechanism can be implemented, e.g., using chemical sensors. Each agent emits some chemical substance (scent), and the sensor of the other agent detects it, i.e., sniffs. The intensity of the scent decreases with the distance.
agent-based  rather-interesting  random-processes  sensors  emergent-design  proof  to-write-about  consider:looking-to-see 
5 weeks ago by Vaguery
[1611.05896] Answering Image Riddles using Vision and Reasoning through Probabilistic Soft Logic
In this work, we explore a genre of puzzles ("image riddles") which involves a set of images and a question. Answering these puzzles require both capabilities involving visual detection (including object, activity recognition) and, knowledge-based or commonsense reasoning. We compile a dataset of over 3k riddles where each riddle consists of 4 images and a groundtruth answer. The annotations are validated using crowd-sourced evaluation. We also define an automatic evaluation metric to track future progress. Our task bears similarity with the commonly known IQ tasks such as analogy solving, sequence filling that are often used to test intelligence.
We develop a Probabilistic Reasoning-based approach that utilizes probabilistic commonsense knowledge to answer these riddles with a reasonable accuracy. We demonstrate the results of our approach using both automatic and human evaluations. Our approach achieves some promising results for these riddles and provides a strong baseline for future attempts. We make the entire dataset and related materials publicly available to the community in ImageRiddle Website (this http URL).
machine-learning  image-processing  natural-language-processing  deep-learning  puzzles  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:integrating-NLP 
6 weeks ago by Vaguery
[1710.01802] Automatic Structural Scene Digitalization
In this paper, we present an automatic system for the analysis and labeling of structural scenes, floor plan drawings in Computer-aided Design (CAD) format. The proposed system applies a fusion strategy to detect and recognize various components of CAD floor plans, such as walls, doors, windows and other ambiguous assets. Technically, a general rule-based filter parsing method is fist adopted to extract effective information from the original floor plan. Then, an image-processing based recovery method is employed to correct information extracted in the first step. Our proposed method is fully automatic and real-time. Such analysis system provides high accuracy and is also evaluated on a public website that, on average, archives more than ten thousands effective uses per day and reaches a relatively high satisfaction rate.
rather-interesting  digitization  feature-extraction  CAD  abstraction  machine-learning  to-write-about  consider:looking-to-see 
8 weeks ago by Vaguery
[1802.08535] Can Neural Networks Understand Logical Entailment?
We introduce a new dataset of logical entailments for the purpose of measuring models' ability to capture and exploit the structure of logical expressions against an entailment prediction task. We use this task to compare a series of architectures which are ubiquitous in the sequence-processing literature, in addition to a new model class---PossibleWorldNets---which computes entailment as a "convolution over possible worlds". Results show that convolutional networks present the wrong inductive bias for this class of problems relative to LSTM RNNs, tree-structured neural networks outperform LSTM RNNs due to their enhanced ability to exploit the syntax of logic, and PossibleWorldNets outperform all benchmarks.
Betteridge's-Law  neural-networks  representation  nudge-targets  consider:looking-to-see  low-hanging-fruit  right-tool-for-the-job 
8 weeks ago by Vaguery
[1510.02875] Exploring mod2 n-queens games
We introduce a two player game on an n x n chessboard where queens are placed by alternating turns on a chessboard square whose availability is determined by the number of queens already on the board which can attack that square modulo two. The game is explored along with some variations and its complexity.
mathematical-recreations  chess  enumeration  game-theory  rather-interesting  nudge-targets  consider:looking-to-see 
8 weeks ago by Vaguery
[1801.02262] Magic Polygons and Their Properties
Magic squares are arrangements of natural numbers into square arrays, where the sum of each row, each column, and both diagonals is the same. In this paper, the concept of a magic square with 3 rows and 3 columns is generalized to define magic polygons. Furthermore, this paper will examine the existence of magic polygons, along with several other properties inherent to magic polygons.
mathematical-recreations  magic-squares  combinatorics  number-theory  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see 
8 weeks ago by Vaguery
[1710.00194] Where computer vision can aid physics: dynamic cloud motion forecasting from satellite images
This paper describes a new algorithm for solar energy forecasting from a sequence of Cloud Optical Depth (COD) images. The algorithm is based on the following simple observation: the dynamics of clouds represented by COD images resembles the motion (transport) of a density in a fluid flow. This suggests that, to forecast the motion of COD images, it is sufficient to forecast the flow. The latter, in turn, can be accomplished by fitting a parametric model of the fluid flow to the COD images observed in the past. Namely, the learning phase of the algorithm is composed of the following steps: (i) given a sequence of COD images, the snapshots of the optical flow are estimated from two consecutive COD images; (ii) these snapshots are then assimilated into a Navier-Stokes Equation (NSE), i.e. an initial velocity field for NSE is selected so that the corresponding NSE' solution is as close as possible to the optical flow snapshots. The prediction phase consists of utilizing a linear transport equation, which describes the propagation of COD images in the fluid flow predicted by NSE, to estimate the future motion of the COD images. The algorithm has been tested on COD images provided by two geostationary operational environmental satellites from NOAA serving the west-hemisphere.
image-processing  prediction  nudge-targets  consider:looking-to-see  representation  low-hanging-fruit 
8 weeks ago by Vaguery
[1709.10030] Sparse Hierarchical Regression with Polynomials
We present a novel method for exact hierarchical sparse polynomial regression. Our regressor is that degree r polynomial which depends on at most k inputs, counting at most ℓ monomial terms, which minimizes the sum of the squares of its prediction errors. The previous hierarchical sparse specification aligns well with modern big data settings where many inputs are not relevant for prediction purposes and the functional complexity of the regressor needs to be controlled as to avoid overfitting. We present a two-step approach to this hierarchical sparse regression problem. First, we discard irrelevant inputs using an extremely fast input ranking heuristic. Secondly, we take advantage of modern cutting plane methods for integer optimization to solve our resulting reduced hierarchical (k,ℓ)-sparse problem exactly. The ability of our method to identify all k relevant inputs and all ℓ monomial terms is shown empirically to experience a phase transition. Crucially, the same transition also presents itself in our ability to reject all irrelevant features and monomials as well. In the regime where our method is statistically powerful, its computational complexity is interestingly on par with Lasso based heuristics. The presented work fills a void in terms of a lack of powerful disciplined nonlinear sparse regression methods in high-dimensional settings. Our method is shown empirically to scale to regression problems with n≈10,000 observations for input dimension p≈1,000.
statistics  regression  algorithms  approximation  performance-measure  to-understand  nudge-targets  consider:looking-to-see 
8 weeks ago by Vaguery
[1710.06647] Image Restoration by Iterative Denoising and Backward Projections
Inverse problems appear in many applications such as image deblurring and inpainting. The common approach to address them is to design a specific algorithm for each problem. The Plug-and-Play (P&P) framework, which has been recently introduced, allows solving general inverse problems by leveraging the impressive capabilities of existing denoising algorithms. While this fresh strategy has found many applications, a burdensome parameter tuning is often required in order to obtain high-quality results. In this work, we propose an alternative method for solving inverse problems using denoising algorithms, which requires less parameter tuning. We provide a theoretical analysis of the method, and empirically demonstrate that it is competitive with task-specific techniques and the P&P approach for image inpainting and deblurring.
inverse-problems  image-processing  superresolution  algorithms  performance-measure  to-write-about  nudge-targets  consider:looking-to-see 
8 weeks ago by Vaguery
[1707.06340] On Unlimited Sampling
Shannon's sampling theorem provides a link between the continuous and the discrete realms stating that bandlimited signals are uniquely determined by its values on a discrete set. This theorem is realized in practice using so called analog--to--digital converters (ADCs). Unlike Shannon's sampling theorem, the ADCs are limited in dynamic range. Whenever a signal exceeds some preset threshold, the ADC saturates, resulting in aliasing due to clipping. The goal of this paper is to analyze an alternative approach that does not suffer from these problems. Our work is based on recent developments in ADC design, which allow for ADCs that reset rather than to saturate, thus producing modulo samples. An open problem that remains is: Given such modulo samples of a bandlimited function as well as the dynamic range of the ADC, how can the original signal be recovered and what are the sufficient conditions that guarantee perfect recovery? In this paper, we prove such sufficiency conditions and complement them with a stable recovery algorithm. Our results are not limited to certain amplitude ranges, in fact even the same circuit architecture allows for the recovery of arbitrary large amplitudes as long as some estimate of the signal norm is available when recovering. Numerical experiments that corroborate our theory indeed show that it is possible to perfectly recover function that takes values that are orders of magnitude higher than the ADC's threshold.
information-theory  rather-interesting  signal-processing  the-mangle-in-practice  hardware-changes-models  to-write-about  nudge-targets  consider:looking-to-see 
8 weeks ago by Vaguery
[1710.00709] Synthesising Evolutionarily Stable Normative Systems
Within the area of multi-agent systems, normative systems are a widely used framework for the coordination of interdependent activities. A crucial problem associated with normative systems is that of synthesising norms that effectively accomplish a coordination task and whose compliance forms a rational choice for the agents within the system. In this work, we introduce a framework for the synthesis of normative systems that effectively coordinate a multi-agent system and whose norms are likely to be adopted by rational agents. Our approach roots in evolutionary game theory. Our framework considers multi-agent systems in which evolutionary forces lead successful norms to prosper and spread within the agent population, while unsuccessful norms are discarded. The outputs of this evolutionary norm synthesis process are normative systems whose compliance forms a rational choice for the agents. We empirically show the effectiveness of our approach through empirical evaluation in a simulated traffic domain.
evolutionary-dynamics  game-theory  rather-interesting  meta-simulation  performance-measure  inverse-problems  to-write-about  consider:looking-to-see 
11 weeks ago by Vaguery
[1611.03144] Therapeutic target discovery using Boolean network attractors: improvements of kali
In a previous article, an algorithm for identifying therapeutic targets in Boolean networks modeling pathological mechanisms was introduced. In the present article, the improvements made on this algorithm, named kali, are described. These improvements are i) the possibility to work on asynchronous Boolean networks, ii) a finer assessment of therapeutic targets and iii) the possibility to use multivalued logic. kali assumes that the attractors of a dynamical system, such as a Boolean network, are associated with the phenotypes of the modeled biological system. Given a logic-based model of pathological mechanisms, kali searches for therapeutic targets able to reduce the reachability of the attractors associated with pathological phenotypes, thus reducing their likeliness. kali is illustrated on an example network and used on a biological case study. The case study is a published logic-based model of bladder tumorigenesis from which kali returns consistent results. However, like any computational tool, kali can predict but can not replace human expertise: it is a supporting tool for coping with the complexity of biological systems in the field of drug discovery.
reaction-networks  boolean-networks  Kauffmania  bioinformatics  systems-biology  rather-interesting  nudge-targets  consider:looking-to-see 
11 weeks ago by Vaguery
Maverick Solitaire
An early form of Poker solitaire is actually a puzzle of sorts, one which has been called Maverick solitaire (after its appearance on the 1950's/1960's Western T.V. show Maverick, in the first season episode Rope of Cards).  Twenty five cards are dealt from a shuffled 52-card deck.  The object is to divide the 25 cards into five groups of five cards so that each is a pat hand in draw poker (a hand which does not need to be drawn to).  Maverick Solitaire is well-known as a sucker bet, as the probability of success with a random group of 25 cards would seem low, but is actually quite high: the eponymous author of Maverick's Guide to Poker estimates the odds to be at least 98 percent (he disallows four of a kind).  This is remarkably accurate: Mark Masten's computer solver, allowing four of a kind, solved about 98.1 percent of a random set of 1000 deals.  Deals with unique solutions are even less common than impossible ones: the sample above had 19 impossible deals and only 8 with unique solutions.
mathematical-recreations  cards  nudge-targets  consider:representation  consider:looking-to-see 
11 weeks ago by Vaguery

« earlier    

related tags

`  abstraction  agent-based  algebra  algorithms  anomaly-detection  approximation  arithmetic  asynchronous  automata  benchmarking  betteridge's-law  bioinformatics  boolean-networks  cad  cards  cellular-automata  chess  classification  clustering  code-generation  coding  collective-behavior  combinatorics  community-detection  complexology  computation  computational-complexity  computational-geometry  computer-vision  consider:algorithms  consider:approximation  consider:benchmarking  consider:classification  consider:comparing-to-random  consider:coordination  consider:feature-discovery  consider:generalizing  consider:integrating-nlp  consider:open-questions  consider:performance-measures  consider:planning-versions  consider:prescriptive-algorithm  consider:rediscovery  consider:representation  consider:simulation  consider:stochastic-versions  consider:symbolic-regression  constraint-satisfaction  constructibility  construction  continued-fractions  control-theory  data-mining  data-structures  deep-learning  digitization  distance  distributed-processing  dynamical-systems  easily-checked  economics  emergent-design  engineering-design  enumeration  esoteric  evolutionary-dynamics  experimental-design  extreme-values  feature-construction  feature-extraction  financial-engineering  formal-languages  fun  game-theory  geometry  graph-partitioning  graph-theory  graphics  hardware-changes-models  heuristics  horse-races  hypergraphs  hyperheuristics  image-processing  indistinguishable-from-magic  inference  information-theory  inverse-problems  kauffmania  knot-theory  knuth  library  looking-to-see  lovely-title  lovely  low-hanging-fruit  machine-learning  magic-squares  mathematical-programming  mathematical-recreations  mathematics  matrices  meta-simulation  metaheuristics  metrics  modeling-is-not-mathematics  modeling  multiobjective-optimization  natural-language-processing  network-theory  neural-networks  nonlinear-dynamics  nonstandard-computation  not-quite-far-enough  nudge-targets  number-theory  numerical-methods  online-learning  open-questions  operations-research  optimization  out-of-the-box  pattern-discovery  performance-measure  permutations  plane-geometry  planning  politics  polyominoes  prediction  privacy  probability-theory  proof  purdy-pitchers  puzzles  random-processes  rather-interesting  reaction-networks  regression  representation  right-tool-for-the-job  sensors  signal-processing  simulation  software  stamp-collecting  statistics  strings  superresolution  systems-biology  the-mangle-in-practice  tiling  to-draw  to-simulate  to-understand  to-w  to-write-about  tomography  topology  trading  utilities  variable-selection 

Copy this bookmark:



description:


tags: