Applying deep learning to right whale photo identification.

Photo identification is an important tool for estimating abundance and monitoring population trends over time. However, manually matching photographs to known individuals is time-consuming. Motivated by recent developments in image recognition, we hosted a data science challenge on the crowdsourcing platform Kaggle to automate the identification of endangered North Atlantic right whales (Eubalaena glacialis). The winning solution automatically identified individual whales with 87% accuracy with a series of convolutional neural networks to identify the region of interest on an image, rotate, crop, and create standardized photographs of uniform size and orientation and then identify the correct individual whale from these passport-like photographs. Recent advances in deep learning coupled with this fully automated workflow have yielded impressive results and have the potential to revolutionize traditional methods for the collection of data on the abundance and distribution of wild populations. Presenting these results to a broad audience should further bridge the gap between the data science and conservation science communities.

Aplicación del Aprendizaje Profundo a la Identificación Fotográfica de la Ballena Franca Resumen La identificación fotográfica es una herramienta importante para la estimación de la abundancia y el monitoreo de las tendencias poblacionales en el tiempo. Sin embargo, corresponder las fotografías con los individuos conocidos requiere de mucho tiempo. Motivados por los avances recientes en el reconocimiento de imágenes, decidimos acoger un reto de datos científicos en la plataforma de colaboración masiva Kaggle para automatizar la identificación de ballenas francas del Atlántico norte (Eubalaena glacialis), especie que se encuentra en peligro de extinción. La solución ganadora identificó automáticamente a las ballenas individuales con una certeza del 87% y con una serie de redes neurales convolucionales para identificar la región de interés en una imagen, rotar, recortar, y crear fotografías estandarizadas de tamaño y orientación uniforme y después identificar al individuo correcto a partir de estas fotografías tamaño pasaporte. Los avances recientes en el aprendizaje profundo acoplados a este flujo de trabajo completamente automatizado han producido resultados impresionantes y tienen el potencial para revolucionar los métodos tradicionales de recolección de datos de abundancia y distribución de las poblaciones silvestres. La presentación de estos resultados ante un público amplio debería reducir aún más el vacío que existe entre los datos científicos y las comunidades científicas para la conservación.

Sitting Closer to Friends than Enemies, Revisited.

Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves (2011) initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space [Formula: see text] in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into [Formula: see text] can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this case, answering several questions posed by Kermarrec and Thraves. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP-complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the Exponential Time Hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.

Parameterized Complexity of Eulerian Deletion Problems.

We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity of various versions: undirected or directed graphs, vertex or edge deletions, with or without the requirement of connectivity, etc. The collection of results shows an interesting contrast: while the node-deletion variants remain intractable, i.e., W[1]-hard for all the studied cases, edge-deletion problems are either fixed-parameter tractable or polynomial-time solvable. Of particular interest is a randomized FPT algorithm for making an undirected graph Eulerian by deleting the minimum number of edges, based on a novel application of the color coding technique. For versions that remain NP-complete but fixed-parameter tractable we consider also possibilities of polynomial kernelization; unfortunately, we prove that this is not possible unless NP⊆coNP/poly.