Category: algorithm

Deep learning

Software libraries

https://en.wikipedia.org/wiki/Comparison_of_deep_learning_software

Main article: Comparison of deep learning software
  • Deeplearning4j — An open-source deep-learning library written for Java/C++ with LSTMs and convolutional networks. It provides parallelization with Spark on CPUs and GPUs.
  • Gensim — A toolkit for natural language processing implemented in the Python programming language.
  • Keras — An open-source deep learning framework for the Python programming language.
  • Microsoft CNTK (Computational Network Toolkit) — Microsoft’s open-source deep-learning toolkit for Windows and Linux. It provides parallelization with CPUs and GPUs across multiple servers.
  • MXNet — An open source deep learning framework that allows you to define, train, and deploy deep neural networks.
  • OpenNN — An open source C++ library which implements deep neural networks and provides parallelization with CPUs.
  • PaddlePaddle — An open source C++ /CUDA library with Python API for scalable deep learning platform with CPUs and GPUs, originally developed by Baidu.
  • TensorFlow — Google’s open source machine learning library in C++ and Python with APIs for both. It provides parallelization with CPUs and GPUs.
  • Theano — An open source machine learning library for Python supported by the University of Montreal and Yoshua Bengio’s team.
  • Torch — An open source software library for machine learning based on the Lua programming language and used by Facebook.
  • Caffe – Caffe is a deep learning framework made with expression, speed, and modularity in mind. It is developed by the Berkeley Vision and Learning Center (BVLC) and by community contributors.
  • DIANNE – A modular open-source deep learning framework in Java / OSGi developed at Ghent University, Belgium. It provides parallelization with CPUs and GPUs across multiple servers.

Go engine

[youtube https://www.youtube.com/watch?v=vU77itJptK0&w=560&h=315]

Mastering the game of Go with deep neural networks and tree search

David Silver, Aja Huang1, Chris J. Maddison, Arthur Guez, Laurent Sifre1, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe,
John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach1, Koray Kavukcuoglu,
Thore Graepel1, Demis Hassabis

The game of Go has long been viewed as the most challenging of classic games for artificial intelligence owing to its enormous search space and the difficulty of evaluating board positions and moves. Here we introduce a new approach to computer Go that uses ‘value networks’ to evaluate board positions and ‘policy networks’ to select moves. These deep neural networks are trained by a novel combination of supervised learning from human expert games, and reinforcement learning from games of self-play. Without any lookahead search, the neural networks play Go at the level of stateof-the-art Monte Carlo tree search programs that simulate thousands of random games of self-play. We also introduce a new search algorithm that combines Monte Carlo simulation with value and policy networks. Using this search algorithm,our program AlphaGo achieved a 99.8% winning rate against other Go programs, and defeated the human European Go champion by 5 games to 0. This is the first time that a computer program has defeated a human professional player in the full-sized game of Go, a feat previously thought to be at least a decade away.
Continue reading “Go engine”

Design and Analysis of Algorithms

Course Features

Course Description

This is an intermediate algorithms course with an emphasis on teaching techniques for the design and analysis of efficient algorithms, emphasizing methods of application. Topics include divide-and-conquer, randomization, dynamic programming, greedy algorithms, incremental improvement, complexity, and cryptography.

Note on Previous Versions:

The Spring 2015 version of 6.046 contains substantially different content than the Spring 2005 version. The 2005 version was an introductory algorithms course assuming minimal previous experience, while the 2015 version is an intermediate course requiring a semester of introductory material found in 6.006.

Other OCW Versions

OCW has published multiple versions of this subject. Question_OVT logo

dancing links

In computer science, dancing links is the technique suggested by Donald Knuth to efficiently implement his Algorithm X.[1] Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku.

The name dancing links stems from the way the algorithm works, as iterations of the algorithm cause the links to “dance” with partner links so as to resemble an “exquisitely choreographed dance.” Knuth credits Hiroshi Hitotsumatsu and Kōhei Noshita with having invented the idea in 1979,[2] but it is his paper which has popularized it.

“Algorithm X” is the name Donald Knuth used in his paper “Dancing Links” to refer to “the most obvious trial-and-error approach” for finding all solutions to the exact coverproblem.[1] Technically, Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm. While Algorithm X is generally useful as a succinct explanation of how theexact cover problem may be solved, Knuth’s intent in presenting it was merely to demonstrate the utility of the dancing links technique via an efficient implementation he called DLX.[1]

The exact cover problem is represented in Algorithm X using a matrix A consisting of 0s and 1s. The goal is to select a subset of the rows so that the digit 1 appears in each column exactly once.

Algorithm X functions as follows:

  1. If the matrix A has no columns, the current partial solution is a valid solution; terminate successfully.
  2. Otherwise choose a column c (deterministically).
  3. Choose a row r such that Ar, c = 1 (nondeterministically).
  4. Include row r in the partial solution.
  5. For each column j such that Ar, j = 1,
    for each row i such that Ai, j = 1,

    delete row i from matrix A.
    delete column j from matrix A.
  6. Repeat this algorithm recursively on the reduced matrix A.

The nondeterministic choice of r means that the algorithm essentially clones itself into independent subalgorithms; each subalgorithm inherits the current matrix A, but reduces it with respect to a different row r. If column c is entirely zero, there are no subalgorithms and the process terminates unsuccessfully.

The subalgorithms form a search tree in a natural way, with the original problem at the root and with level k containing each subalgorithm that corresponds to k chosen rows. Backtracking is the process of traversing the tree in preorder, depth first.

Any systematic rule for choosing column c in this procedure will find all solutions, but some rules work much better than others. To reduce the number of iterations, Knuthsuggests that the column choosing algorithm select a column with the lowest number of 1s in it.