The weights or parameters in a machine learning system are underdetermined if there are many different configurations of parameters that all explain the training data. For example, if the system is trying to learn simple arithmatic operations, given an input: (2,2) with expected output (4); both 2+2=4, and 2x2=4; so the operation is underdetermined. While this is obvious in this small case, the hidden layers in a neural network often have millions of weights. Furthermore, of the layers are fully connected, then any reordering of the internal nodes and weights would geberate equivalent outputs. This can also occur in statistical methods such as multilinear regression is there are too many features, any of which can contribute.
Underdetermined models may overlearn from the training data leading to poor generalisation or bias. Typically also they can lead to longer training times as the learning algorithm needs to 'decide' between many competing, but equally good, explanations of the data, and so effectively shifts back and forth between them.
Used on pages 117, 153, 573