In this book the author argues that the basis of what we consider computer intelligence has algorithmic roots, and he presents this with a holistic view, showing examples and explaining approaches that encompass theoretical Computer Science and Machine Learning via engineered algorithmic solutions.
Part I of the book introduces the basics. The author starts with a hands-on programming primer for solving combinatorial problems, with an emphasis on recursive solutions. The other chapters in the first part of the book explain shortest paths, sorting, Deep Learning, and Monte Carlo search.
A key function of computational tools is processing Big Data efficiently, and the chapters in Part II of the book examine traditional graph problems such as finding cliques, colorings, independent sets, vertex covers, and hitting sets, and the subsequent chapters cover multimedia, network, image, and navigation data.
The highly topical research areas detailed in Part III are machine learning, problem solving, action planning, general game playing, multiagent systems, and recommendation and configuration.
Finally, in Part IV the author uses application areas such as model checking, computational biology, logistics, additive manufacturing, robot motion planning, and industrial production to explain how the techniques described may be exploited in modern settings.
In terms of machine learning, the book improves (deep) neural nets, support vector machines, nearest neighbor search, collaborative filtering, and bandit-based search algorithms. With conditional random field and tolerant pattern matching it extends reasoning with ontological background knowledge. From the algorithmic community it borrows recent hashing and priority queue data structures, as well as decision diagrams.
The book is supported with a comprehensive index and references, and it will be of value to researchers, practitioners, and students in the areas of Artificial Intelligence and Computational Intelligence.
Author(s): Stefan Edelkamp
Publisher: Springer
Year: 2023
Preface
Towards a Characterization
History andWorking Groups
Problems with the Term "Artificial Intelligence"
Problems with the Term "Computational Intelligence"
Algorithmic Intelligence: Towards a Trade-off
Organization of the Book
Basics
Big Data
Research Areas
Application Areas
Contents
Part I Basics
Chapter 1 Programming Primer
1.1 Recursion
1.1.1 Divide-and-Conquer
1.1.2 Recursion on Texts
1.1.3 Factorial Numbers
1.1.4 Fibonacci Numbers
1.1.5 Ackermann Numbers
1.1.6 Ulam Numbers
1.2 Calculus
1.2.1 Square Roots
1.2.2 Euclid’s Algorithm
1.2.3 Pascal’s Triangle
1.2.4 Prime Factorization
1.2.5 Gaussian Elimination
1.2.6 Min-Max Problem
1.2.7 Quickselect and Quicksort
1.3 Backtracking
1.3.1 Post’s Correspondence Problem
1.3.2 Towers-of-Hanoi
1.3.3 Mazes
1.3.4 The Queens Problem
1.3.5 Sudoku
1.4 Heuristic Search
1.4.1 Number Partitioning
1.4.2 The 15-Puzzle
1.4.3 Ranking and Unranking
1.4.4 Peg Solitaire
1.4.5 Traveling Salesman Problem
1.5 Randomization
1.5.1 Randomized Prime Number Tests
1.5.2 Mister X
1.5.3 Mastermind
1.5.4 Nim
1.5.5 Snake
1.5.6 PacMan
1.6 Bibliographic Notes
Chapter 2 Shortest Paths
2.1 Introduction
2.2 Dijkstra’s Algorithm
2.3 General Priority Queues
2.3.1 k-ary Heaps
2.3.2 Fibonacci Heaps
2.3.3 Pairing Heaps
2.4 Bucket Priority Queues
2.4.1 Radix Heaps
2.4.2 Bucket Maps
2.4.3 Factorized Heaps
2.5 Cache-Efficient Flood-Filling
2.6 Experiments
2.7 Summary
2.8 Bibliographic Notes
Chapter 3 Sorting
3.1 Introduction
3.2 Heapsort
3.3 Strong Heapsort
3.3.1 Strong Heap Construction
3.3.2 Sorting with Strengthened Heaps
3.4 Improving Quicksort
3.5 Block Quicksort
3.6 Quick Mergesort
QuickXSort
QuickMergesort
3.7 Summary
3.8 Bibliographic Notes
Chapter 4 Deep Learning
4.1 Introduction
4.2 Case Study: TicTacToe
4.3 Case Study: Same Game
4.4 Case Study: Sokoban
4.4.1 Designing Loss Functions
4.4.2 Definition of L*
4.5 Greedy Best-First Search: Optimizing Rank
4.6 Summary
4.7 Bibliographic Notes
Chapter 5 Monte-Carlo Search
5.1 Introduction
5.2 Monte-Carlo Search
5.2.1 Upper Confidence Bounds Applied to Trees
5.2.2 Parallel Monte-Carlo Search
5.2.3 Nested Monte-Carlo
5.2.4 Nested Rollout Policy Adaptation
5.3 Beam NRPA
5.4 Refinements
5.5 Improving the Diversity
5.5.1 Improving Diversity in the NRPA Driver
5.5.2 Improving Diversity in the Policy Adaptation
5.6 Case Study: SameGame
5.7 Case Study: Snake-in-the-Box
5.8 Case Study: Vehicle Routing
5.9 Summary
5.10 Bibliographic Notes
Part II Big Data
Chapter 6 Graph Data
6.1 Introduction
6.2 Mathematical Encoding
6.3 PDDL Encodings
6.4 SAT Encodings
6.5 Game Encodings
6.6 Experiments
6.6.1 Clique
6.6.2 Graph Coloring
6.6.3 Independent and Hitting Sets
6.7 Summary
6.8 Bibliographic Notes
Chapter 7 Multimedia Data
7.1 Introduction
7.2 Problem Formulation
7.3 Feature Extraction
Fingerprints
Event Matrix
Naive Statistics
7.4 Evaluation
7.5 Summary
7.6 Bibliographic Notes
Chapter 8 Network Data
8.1 Introduction
8.2 Security Information and Event Management
8.3 Anomaly Detection
8.4 Tolerant Pattern Matching with Background Knowledge
8.4.1 Preliminaries
8.4.2 Tolerant Pattern Matching
8.4.3 Divide-and-Conquer
8.4.4 Complexity Considerations
8.4.5 Conditional Random Fields with Tolerant Features
8.4.5.1 Tolerant Pattern Matches as Feature Function Values
8.4.5.2 Two Layers of Conditional Random Fields
8.4.5.3 Modeling Incidents
8.4.5.4 Prioritization of Incidents
8.5 Efficiency of Incident Detection
8.5.1 Experiments with ArcSight
8.5.2 Simulation Experiments
8.6 Summary
8.7 Bibliographic Notes
Chapter 9 Image Data
9.1 Introduction
9.2 Nearest Neighbor Computation
9.3 Support Vector Machines
9.3.1 Bitvector Machine
9.3.2 Case Studies
9.4 Experiments
9.5 Summary
9.6 Bibliographic Notes
Chapter 10 Navigation Data
10.1 Introduction
10.2 Map Generation
Pre-processing
I/O and Communication
Observations and Experiments
10.3 Map Administration
10.4 Extraction of Road Surfaces
10.5 Road Skeleton Computation
10.5.1 Skeleton Generation
10.5.2 Skeleton Minimization
10.6 Graph Construction
10.7 Integration to a Traffic Simulator
10.7.1 Post-processing of the SUMO Street Network
10.7.2 Traffic Routes
10.8 Summary
10.9 Bibliographic Notes
Part III Research Areas
Chapter 11 Machine Learning
11.1 Introduction
11.2 Machine Learning
11.3 Neural Networks
11.4 GPGPU Essentials
11.5 Iterative Gradient Descent and Parallelization
11.6 Applications
11.7 Summary
11.8 Bibliographic Notes
Chapter 12 Problem Solving
12.1 Introduction
12.2 Perfect Hashing
12.3 Bitvector State Space Search
12.4 Hashing Permutation Games
Sliding-Tile Puzzle
Top-Spin Puzzle
Pancake Problem
12.5 Hashing Selection Games
Hashing with Binomial Coefficients
Hashing with Multinomial Coefficients
12.6 Parallelization
Multi-Core Computation
GPU Computation
12.7 Experiments Explicit-State Perfect Hashing
Symmetries, Frontier Search, and Generality
Compressed Pattern Databases
Other Games
12.8 Binary Decision Diagrams for Strongly Solving Games
Retrograde Analysis on a Bitvector
Hybrid Classification Algorithm
12.9 Experiments BDD Hashing
12.10 Bibliographic Notes
Chapter 13 Card Game Playing
13.1 Introduction
13.2 Bidding
13.3 Open Game Play
13.4 Skat Bot Architecture
13.5 Knowledge-based Paranoia Search
13.6 Factorized Search
13.6.1 The Power of Suit Partitioning
13.6.2 Miniglassbox Search
13.6.3 Single-Dummy Miniglassbox Solver
13.6.4 Double-Dummy Miniglassbox Solver
13.7 World Search
13.8 Open-Card Solver Voting
13.9 Hope Cards
13.10 Towards an ELO Rating System
13.10.1 Scoring Systems and Hand Strength
13.10.2 ELO System for Zero-Sum Games
13.10.3 ELO System for Games of Chance
13.11 Experiments
13.12 General Imperfect Information MiniMax Search
13.12.1 Perfect-Information Monte Carlo
13.12.2 AlphaMu
13.12.3 Permutation
13.13 Summary
13.14 Bibliographic Notes
Chapter 14 Action Planning
14.1 Introduction
14.2 Symbolic Search
14.3 Heuristic Search Planning
14.3.1 Pattern Database
14.3.2 Merge-and-Shrink
14.4 Symbolic A* Search
14.4.1 Basic Improvements
14.4.2 List BDDA*
14.5 Symbolic Merge-and-Shrink
14.5.1 ADD Complexity
14.5.2 Limits and Possibilities
14.6 Comparison
14.7 Complementary
14.7.1 Configuration Choices
14.7.2 Results
14.8 Symbolic Abduction
14.8.1 Computing Valid Hypotheses
14.8.2 Uniform-Cost Abductive Inference
14.8.3 Cost-Optimal Abductive Inference
14.8.4 Manual Selection Strategies
14.8.5 Finding Critical Query Variables
14.9 Plan Recognition Experiments
14.10 Summary
14.11 Bibilographic Notes
Chapter 15 General Game Playing
15.1 Introduction
15.2 General Game Playing
15.2.1 GDL
15.2.2 GDL-II
15.3 Solving General Two-Player Turn-Taking Games
15.4 Handling Incomplete Information
15.4.1 Full Set of Belief States
15.4.2 Subset of Belief States
15.4.2.1 Depth-First Belief State Search (DFBSS)
15.4.2.2 Monte-Carlo Belief State Search (MCBSS)
15.4.2.3 Weighted MCBSS
15.4.3 Choosing a Move for a Set of Belief States
15.5 Experiments
15.6 Summary
15.7 Bibliographic Notes
Chapter 16 Multiagent Systems
16.1 Introduction
16.2 Multiagent-based Simulation
16.3 Simulation Model
16.4 Shortest Path Search
16.5 Experimental Setup
16.6 Current Status and Findings
16.7 Summary
16.8 Bibliographic Notes
Chapter 17 Recommendation and Configuration
17.1 Introduction
17.2 Recommender Systems
17.3 Binarized Clustering
17.4 Product Configuration
17.5 Recommendations for Product Configuration
17.6 Algorithms
17.6.1 Association Rule Mining
17.6.2 Nearest Neighbor
17.6.3 Integration
17.7 Evaluation
17.8 Summary
17.9 Bibliographic Notes
Part IV Applications
Chapter 18 Adversarial Planning
18.1 Introduction
18.2 Basics in Game Theory
18.2.1 Nash Equilibria
18.2.2 Double-Oracle Algorithm
18.3 Incorporating Planning into the Double Oracle Algorithm
18.4 Cost-Adversarial Planning Games
18.5 Experiments
18.5.1 Temporal Planning Domains
18.5.2 Cost-Adversarial Planning Games
18.6 Summary
18.7 Bibliographic Notes
Chapter 19 Model Checking
19.1 Introduction
19.2 GPU Essentials
19.3 Probabilistic Model Checking
19.4 GPU Breadth-First Search
19.4.1 Preparing the Model
19.4.1.1 Parsing the DVE Language
19.4.2 State Exploration on the GPU
19.4.2.1 Checking Enabledness on the GPU
19.4.2.2 Generating the Successors on the GPU
19.4.2.3 Duplicate Checking on (Multiple Cores of) the CPU
19.5 Experiments
19.6 Summary
19.7 Bibliographic Notes
Chapter 20 Computational Biology
20.1 Introduction
20.2 Monte-Carlo Tree Search for MSA
20.2.1 Construction of all Alignment Columns
20.2.2 Construction of all Alignment Gaps
20.2.3 Construction of an Initial Alignment
20.3 Experimental Results
20.4 Summary
20.5 Bibliographic Notes
Chapter 21 Logistics
21.1 Introduction
21.2 Dispatching in Groupage Traffic
21.2.1 Constraint ATSP Solving
21.2.2 Agent Dispatching and Simulation
21.3 Container Packing with Nested Monte-Carlo Search
21.3.1 Extreme Points
21.3.2 Box Packing
21.4 Experiments
21.4.1 Groupage Traffic
21.4.2 Packing
21.4.2.1 2D Packing
21.4.2.2 3D Packing
21.5 Summary
21.6 Bibliographic Notes
Chapter 22 Additive Manufacturing
22.1 Introduction
22.2 Sphere-Tree Construction
22.3 Robustness Considerations
22.4 Global Optimization
22.5 Experimental Results
22.6 Summary
22.7 Bibliographic Notes
Chapter 23 Robot Motion Planning
23.1 Introduction
23.2 RRT, RRT*, and Deep RRT*
23.3 Physical TSP
23.4 Shortest Paths
23.5 TSP Search
23.5.1 Optimal TSP Solving
23.5.2 Suboptimal TSP Solving
23.6 Inspection Problem
23.7 Method
23.7.1 Generating the Inspection Points
23.7.2 CTSP Solver
23.7.3 Following the CTSP Tour
23.8 Evaluation
23.8.1 PTSP Simulation
23.8.2 Robot Simulation
23.8.3 2D Inspection
23.8.4 3D Inspection
23.9 Summary
23.10 Bibliographic Notes
Chapter 24 Industrial Production
24.1 Introduction
24.2 Preliminaries
24.2.1 Discrete Event Simulation
24.2.2 Flow Manufacturing
24.3 Case Study
24.4 Promela Specification
24.5 Optimized Scheduling
24.5.1 Guarded Branching
24.5.2 Process Synchronization
24.6 Game Encoding
24.7 Evaluation
24.8 Summary
24.9 Bibliographic Notes
Chapter 25 Further Application Areas
25.1 Introduction
25.2 Vacancy Simulation and Temporal Pattern Mining in Smart Homes
25.3 Form Filling
25.4 Demand and Sales Prediction for Retail Trade
25.5 Geo-Location Tagging for Better Goods Assortment
25.6 Automated Inventory List Creation with Vision and Speech
25.7 Temporal Task-Motion Planning for Robots with Resources
25.8 Optimizing Integrated Production and Route-Planning
25.9 Safe Travel Recommendation with Movement Data
25.10 Improved Static Code Analysis with Machine Learning
25.11 Contract Prediction on Account Transaction Series
25.12 Recommender Systems for eCommerce
25.13 Predictive Maintenance to Produce Assemblies
25.14 Knowledge for Retail
25.15 Industrial Inspection
25.16 Skill Recommendation
25.17 Bibliographic Notes
Index and References
Index
References
