2. Challenging Applications
As for addressing challenging applications of machine learning, we've had the following activities. The first three are classified as discovery of hidden structures from data.
L-system Grammar Induction:
The induction of L-system grammar is an open problem little explored so far. We have invented two learning algorithms. LGIN (L-system Grammar Induction based on Number theory) [C88] can find the original grammar from a noiseless sentence of thousands of characters within one second. LGIC2 (L-system Grammar Induction with error Correction, ver. 2) [C93] can find the original grammar using emergent induction from a noisy sentence of thausands of characters within minites or 30 minites depending on noise level.
Numeric Law Discovery using Neural Networks:
Discovering understandable numeric relations such as polynomials from data is one of the key issues of data mining. We invented a couple of methods each of which performs multivariate polynomial regression using MLP and BPQ. First, we invented RF5 (rule extraction from facts, ver. 5) [C32, C34] which discovers the adequate polynomial from numeric data. As one example, RF5 discovered Kepler's third law. Next, we investigated extracting laws from data including numeric and nominal variables. And we invented RF6 [C47] which learns the whole data using a single MLP and then decomposes into a set of rules, where a rule means a nominally conditioned polynomial. RF6 was applied to real data to find interesting results. Finally, we invented RN2 (rule extraction from neural nets, ver. 2) [J37], which extracts regression rules from trained neural networks. RN2 uses VQ (vector quantizer) and decision trees for rule extraction. RN2 found interesting regression rules from financial or automobile data sets.
Behavioral Rules Learning using Classifier Systems:
Thrown into an unknown environment, an intelligent agent acts by trial and error and gradually learns behavioral rules through experiences. For this learning we adopt a learning classifier system (LCS) framework as a brain of the agent. Although LCS usually uses GA, we introduced new neural learning called bidirectional competitive learning and built NCS (neural classifier system) [C50]. NCS can find behavioral rules through experiences; for example, could solve quite hard 70-multiplexer problem completely after 10 million cycles. We believe NCS has the good potential.
Job Shop Scheduling using Genetic Algorithms:
We got interested in the evolutionary framework, and wanted to develop excellent algorithms using genetic algorithm (GA) to solve job shop scheduling problems (JSSPs) known as hard combinatorial problems. We invented many smart algorithms. First, we invented forcing GA [C05] by introducing forcing into GA, where forcing means replacing illegal genotype with the closest legal one. Forcing GA showed for the first time in the world that GA can solve rather hard JSSPs. Next, we invented GA/GT [C07] using Giffler & Thompson (GT) representation, which could solve larger scale of JSSPs. Then, we introduced MSXF (multi-step crossover and local search) to have GA/MSXF [C28], which stably showed the best performance at that time. Finally, we invented CBSA+SB [C17] by enhancing CBSA (critical block simulated annealing) with SB (shifting bottleneck). CBSA+SB showed the best performance for ten tough JSSPs.
On this topic we've got more than 1,800 citations according to
Social Network Analysis:
Global human activities through the Internet have evolved to form complex networks called social networks. We investigate methods [C73, J45] which extract influential nodes in social networks using machine learning frameworks.
L-system grammar induction
LGIC2 can find the original grammar
from a sentence having
rather heavy transmutation like this.
numerical law (multivariate polynomials) discovery
by neural networks
NCS completely learns 70-MPX problem
after ten million cycles.
an optimal schedule for mt10x10 problem
obtained by GA/GT