liveBook · Manning

Unsupervised learning

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

Unsupervised learning is a machine-learning paradigm in which a model discovers structure or patterns in data without labeled target outputs.

Unsupervised learning finds structure in data without labeled target outputs. Common approaches include clustering and dimensionality reduction. Clustering groups objects by similarity, so objects within a group have a natural relationship and differ from those in other groups. section 11.2

Grouping driving scenarios

A self-driving vehicle could cluster observations of driving environments to distinguish types of intersections or roundabouts without being given those categories as labels. section 11.2

Methods include k-means, DBSCAN, principal component analysis, autoencoders, and self-organizing maps (SOMs). A SOM is a neural network that uses competitive learning rather than error-correction learning such as backpropagation with gradient descent. section 11.2 section 11.10

Finding a traveling salesperson route

A SOM can also help tackle a combinatorial optimization problem. For a traveling salesperson instance, normalize the city coordinates, initialize a network of neurons, and repeatedly sample a city. Find the closest neuron and move it and its neighbors toward the city, then track the resulting route length. For the Qatar instance qa194.tsp, one run produced a route length of 9,816, compared with the optimal 9,352. A MiniSom implementation produced 11,844.47; experiment with neuron count, sigma, learning rate, and iterations to improve the result. section 11.8

route_lengths = []                                                        #1
paths_x = []                                                              #2
paths_y = []                                                              #2
  
for i in tqdm(range(iterations)):                                         #3
    if not i % 100:
        print('\t> Iteration {}/{}'.format(i, iterations), end="\r")      #4
  
    city = cities.sample(1)[['x', 'y']].values                            #5
    winner_idx = select_closest(network, city)                            #6
   
    gaussian = get_neighborhood(winner_idx, number_of_neurons // 10, 
  network.shape[0])                                                      #7
  
    network += gaussian[:, np.newaxis] * learning_rate * (city - network) #8
  
    paths_x.append(network[:, 0].copy())                                  #9
    paths_y.append(network[:, 1].copy())                                  #9
  
    learning_rate = learning_rate * 0.99997                               #10
    number_of_neurons = number_of_neurons * 0.9997                        #10
  
    if not i % 1000:                                                      #11
        plot_network(cities, network, name='diagrams/{:05d}.png'.format(i))
  
    if number_of_neurons < 1:                                             #12
        print('Radius has completely decayed, finishing execution',
               'at {} iterations'.format(i))
        break
    if learning_rate < 0.001:
        print('Learning rate has completely decayed, finishing execution',
               'at {} iterations'.format(i))
        break
    
    route = get_route(cities, network)                                    #13
    problem = problem.reindex(route)                                      #13
    distance = route_distance(problem)                                    #13
    route_lengths.append(distance)                                        #13
  
else:
    print('Completed {} iterations.'.format(iterations))                  #14
#1 Store the lengths of the TSP routes during the SOM training iterations.
#2 Store the x and y coordinates of the neurons in the network during the training iterations.
#3 Training loop
#4 Print only if the current iteration index is a multiple of 100.
#5 Choose a random city.
#6 Find the index of the neuron (winner) in the SOM network that is closest to the randomly chosen city.
#7 Generate a filter that applies changes to the winner’s gaussian.
#8 Update the network’s weights.
#9 Append the current coordinates to the paths.
#10 Decay the learning rate and the neighborhood radius n at each iteration to gradually reduce the influence of the Gaussian filter over time.
#11 Check for the plotting interval.
#12 Check if any parameter has completely decayed.
#13 Calculate distance, and store it in the route_lengths list.
#14 Indicate that the specified number of training iterations has been completed.

Inspect the training loop that selects a city, finds the winning neuron, and updates its neighborhood. section 11.8

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Defines clustering and names several methods, then works through SOM training and parameter tuning for a routing problem.
Examples
Illustrates unlabeled driving-scenario clusters and a SOM route for the Qatar traveling salesperson instance.
What you can do after
Apply it via a SOM implementation to construct a traveling salesperson route and experiment with training parameters.
How it connects
Connects clustering and dimensionality reduction with competitive learning and combinatorial optimization.

Also explained in

Compare how 20 books explain unsupervised learning →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.