Issues of Multimedia Mining and Back Propagation in Classification

Part 1: Issues of Multimedia Mining

Multimedia database is a collection of interrelated multimedia data that includes text, sketches, drawings, images, animations, video, audio, and hypertext. Multimedia data mining is an interdisciplinary field that integrates image processing and understanding, computer vision, data mining, and pattern recognition.

The key issues in multimedia data mining are as follows:

1. Content-Based Retrieval and Similarity Search

• Retrieving multimedia data based on its actual content (e.g., color, texture, shape in images) rather than metadata or keywords is extremely challenging.
• Defining meaningful similarity measures across different media types (audio, video, image) is non-trivial.

2. High Dimensionality

• Multimedia data such as images and video are represented by high-dimensional feature vectors.
• Mining in high-dimensional spaces suffers from the "curse of dimensionality," making distance-based methods less effective.

3. Large Data Volume and Scalability

• Multimedia files (video, audio) are very large in size.
• Storing, indexing, and mining such large volumes of data efficiently is a major challenge.

4. Heterogeneity of Data Types

• Multimedia data combines multiple modalities (text, image, audio, video).
• Integrating and mining across these heterogeneous data types requires specialized techniques for each modality.

5. Feature Extraction and Representation

• Raw multimedia data must be converted into meaningful features before mining.
• Extracting relevant low-level features (color histograms, MFCC for audio, motion vectors for video) that capture high-level semantics is difficult.

6. Semantic Gap

• There is a significant gap between low-level features automatically extracted from multimedia data and the high-level semantic meaning perceived by humans.
• Bridging this gap remains an open research problem.

7. Uncertainty and Noise

• Multimedia data often contains noise (blurry images, background noise in audio).
• Handling uncertainty and incompleteness in such data during mining is challenging.

8. Mining Methodology

• It includes issues in mining various and new kinds of knowledge, mining knowledge in multidimensional space, and handling uncertainty, noise, or incompleteness of data (Under Issues in Data Mining).

Part 2: Back Propagation Used in Classification

Background

Back Propagation (Backprop) is a supervised learning algorithm used to train Artificial Neural Networks (ANNs). It is widely used for classification tasks where the goal is to assign input data to one of several predefined classes.

Architecture of a Neural Network for Classification

A typical neural network used for classification consists of:

How Back Propagation Works in Classification

The back propagation algorithm works in two phases:

Phase 1: Forward Pass

1. Input features are fed into the network.
2. Each neuron computes a weighted sum of its inputs:

$$net_j = \sum_{i} w_{ij} \cdot x_i + b_j$$

3. An activation function (e.g., sigmoid, ReLU, softmax) is applied:

$$o_j = f(net_j)$$

4. The output layer produces predicted class probabilities.
5. For classification, softmax is commonly used at the output layer:

$$P(class_k) = \frac{e^{net_k}}{\sum_{j} e^{net_j}}$$

Phase 2: Backward Pass (Error Propagation)

1. Compute the Error (Loss):
   • The difference between the predicted output and the actual class label is computed using a loss function.
   • For classification, Cross-Entropy Loss is commonly used:

$$E = -\sum_{k} y_k \cdot \log(\hat{y}_k)$$

where yₖ is the true label (1 or 0) and ŷₖ is the predicted probability.

2. Compute Error at Output Layer:
   • The error signal (delta) at the output neuron k is:

$$\delta_k = (y_k - o_k) \cdot f'(net_k)$$

where f'(net_k) is the derivative of the activation function.

3. Propagate Error to Hidden Layers:
   • The error is propagated backward through the network:

$$\delta_j = f'(net_j) \cdot \sum_{k} \delta_k \cdot w_{jk}$$

4. Update Weights:
   • Weights are updated using gradient descent to minimize the error:

$$w_{ij} \leftarrow w_{ij} + \Delta w_{ij}$$

$$\Delta w_{ij} = \eta \cdot \delta_j \cdot o_i$$

where:

• η = learning rate
• δⱼ = error signal at neuron j
• oᵢ = output of the previous neuron i

5. Update Biases similarly:

$$b_j \leftarrow b_j + \eta \cdot \delta_j$$

Iterative Training for Classification

• The forward pass and backward pass are repeated for all training samples over multiple epochs.
• The network gradually adjusts its weights to correctly classify training examples.
• Training stops when:
  • The error falls below a threshold, OR
  • A maximum number of epochs is reached.

Summary of Back Propagation Steps for Classification

1. Initialize weights randomly
2. For each training sample:
   a. Forward pass: compute output
   b. Compute classification error (loss)
   c. Backward pass: compute deltas at output and hidden layers
   d. Update all weights and biases
3. Repeat until convergence
4. Use trained network to classify new/unseen data

Example

Consider a network trained to classify a scanned handwritten digit into one of the ten classes 0 to 9. The input layer holds one neuron for each pixel of the 28 by 28 image, a single hidden layer holds a smaller number of sigmoid neurons, and the output layer holds ten softmax neurons, one per class.

During the forward pass each hidden neuron computes $net_j = \sum_i w_{ij} x_i + b_j$ and applies the sigmoid, and the output layer turns the ten net values into class probabilities with the softmax formula given above. Suppose the image is really a 7 but the network gives the highest probability to class 1: the cross-entropy loss is large because the probability assigned to the true class is small.

The backward pass then repairs that. The output deltas $\delta_k = (y_k - o_k) f'(net_k)$ are positive for the neuron of class 7, whose target is 1, and negative for the neuron of class 1, whose target is 0. Each hidden neuron receives its share of the blame through $\delta_j = f'(net_j) \sum_k \delta_k w_{jk}$, and every weight is then nudged by $\Delta w_{ij} = \eta \delta_j o_i$, so the pixels that actually distinguish a 7 gain influence on the class 7 output and lose influence on the class 1 output.

Repeating this over the whole training set for many epochs drives the loss down until the network assigns the highest probability to the correct digit, and the trained weights can then classify digits it has never seen.

Conclusion

Multimedia mining is difficult because the data is large, high dimensional, heterogeneous, noisy, and separated from human meaning by the semantic gap. Back propagation is one of the standard answers to that difficulty: it learns the mapping from raw features to class labels automatically by alternating a forward pass that produces a prediction with a backward pass that distributes the error over every weight, and it repeats the pair until the network classifies unseen data correctly.