dwave-examples / feature-selection-notebook

Feature selection for machine learning using mutual information.

Feature Selection

This notebook develops a QPU programming model for an optimization problem that selects a subset and demonstrates it using Ocean software's dwave-hybrid on an example of feature selection for machine learning.

The notebook has the following sections:

1. What is Feature Selection? defines and explains the feature-selection problem.
2. Feature Selection by Mutual Information describes a particular method of feature selection that is demonstrated in this notebook.
3. Solving Feature Selection on a Quantum Computer shows how such optimization problems can be formulated for solution on a D-Wave quantum computer.
4. Example Application: Predicting Survival of Titanic Passengers demonstrates the use of Kerberos, an out-of-the-box classical-quantum hybrid sampler, to select optimal features for a public-domain dataset.

What is Feature Selection?

Statistical and machine-learning models use sets of input variables ("features") to predict output variables of interest. Feature selection can be part of the model design process: selecting from a large set of potential features a highly informative subset simplifies the model and reduces dimensionality.

For systems with large numbers of potential input information—for example, weather forecasting or image recognition—model complexity and required compute resources can be daunting. Feature selection can help make such models tractable.

However, optimal feature selection can itself be a hard problem. This example introduces a powerful method of optimizing feature selection based on a complex probability calculation. This calculation is submitted for solution to a quantum computer.

Installation

You can run this example without installation in cloud-based IDEs that support the Development Containers specification (aka "devcontainers").

For development environments that do not support devcontainers, install requirements:

pip install -r requirements.txt

If you are cloning the repo to your local system, working in a virtual environment is recommended.

Usage

Your development environment should be configured to access Leap’s Solvers. You can see information about supported IDEs and authorizing access to your Leap account here.

The notebook can be opened by clicking on the 01-feature-selection.ipynb file in VS Code-based IDEs.

To run a locally installed notebook:

jupyter notebook

License

See LICENSE file.

feature-selection-notebook's Issues

Extend qpu_working_graph for Zephyr

Description
Attempting to run this notebook with a Zephyr-structured solver fails on cell 23. Right now, helper function qpu_working_graph does not support dnx.zephyr_graph

To Reproduce
Run the notebook, specifically cell 23 with a Zephyr-structured solver.

from helpers.qpu import qpu_working_graph 
from dwave.system import DWaveSampler, FixedEmbeddingComposite
from minorminer.busclique import find_clique_embedding

qpu = DWaveSampler(solver=dict(topology__type='zephyr'))

qpu_working_graph = qpu_working_graph(qpu)

Error

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Input In [46], in <module>
      3 from minorminer.busclique import find_clique_embedding
      5 qpu = DWaveSampler()
----> 7 qpu_working_graph = qpu_working_graph(qpu)
      8 embedding = find_clique_embedding(bqm.variables, qpu_working_graph)
     10 qpu_sampler = FixedEmbeddingComposite(qpu, embedding)

File ~/Library/CloudStorage/OneDrive-D-WaveSystemsInc/OneDrive - Documents/JN/feature-selection-notebook/helpers/qpu.py:25, in qpu_working_graph(qpu)
     21 "Return a dwave_networkx graph representing the working graph of a given QPU."
     23 dnx_graphs = {'chimera': dnx.chimera_graph, 'pegasus': dnx.pegasus_graph}
---> 25 dnx_graph = dnx_graphs[qpu.properties["topology"]["type"].lower()]
     27 return dnx_graph(qpu.properties["topology"]["shape"][0],
     28                  node_list=qpu.nodelist,
     29                  edge_list=qpu.edgelist)

KeyError: 'zephyr'

remove "Jupyter Notebook" from title of README

remove "Jupyter Notebook" from the title of the README for consistency with other notebooks

It's redundant given tagging

Cell 25 of the notebook fails as its problem exceeds the max runtime and gets rejected

Now that problems exceeding 1s in duration get rejected, the last cell of this notebook fails to run as it tries to submit a problem with 10K reads.

Cell 25:

from helpers.draw import plot_feature_selection 

selected_features = np.zeros((len(features), len(features)))
for k in range(1, len(features) + 1):
    print("Submitting for k={}".format(k))
    kbqm = dimod.generators.combinations(features, k, strength=6)
    kbqm.update(bqm)
    kbqm.normalize()
    
    best = kerberos_sampler.sample(kbqm, 
                                   qpu_sampler=qpu_sampler, 
                                   qpu_reads=10000, 
                                   max_iter=1,
                                   qpu_params={'label': 'Notebook - Feature Selection'}
                                  ).first.sample
    
    for fi, f in enumerate(features):
        selected_features[k-1, fi] = best[f]

plot_feature_selection(features, selected_features)

Possible solutions: Lower the number of reads or use spin-reversal transforms.