In the second lecture of CS231N, we delve deeper into the mechanics of image classification, a core task in computer vision. This lecture builds upon the foundational concepts introduced in the first lecture, where we discussed the history and overview of computer vision. Today, we will explore the details of learning algorithms, starting with the k-nearest neighbor (KNN) classifier and linear classifiers.
Administrative Announcements
Before diving into the content, a few administrative points were addressed:
- Piazza Sign-Up: Students are encouraged to sign up for Piazza, the main communication platform for the course. It is essential for receiving timely responses to questions regarding projects and assignments.
- Assignment One: The first assignment will be released later today, focusing on implementing a k-nearest neighbor classifier, linear classifiers, and a simple two-layer neural network. Students are advised to review last year's assignment for a head start.
- Python and NumPy: All assignments will utilize Python and NumPy. A tutorial is available for those unfamiliar with these tools, as they are crucial for efficient numerical computing.
- Google Cloud Support: The course is officially supported by Google Cloud, allowing students to use cloud resources for assignments and projects. Coupons for Google Cloud credits will be distributed to facilitate this.
Image Classification Overview
Image classification involves assigning a label from a predetermined set of categories to an input image. For instance, given an image of a cat, the system must determine whether it belongs to the category of cats, dogs, trucks, etc. While this task seems straightforward for humans, it poses significant challenges for machines due to the following factors:
The Semantic Gap
- Representation of Images: Computers perceive images as grids of pixel values, lacking the holistic understanding that humans possess. For example, an image of a cat is represented as a large array of numbers, making it difficult for algorithms to recognize the concept of a "cat".
- Variability in Images: Changes in viewpoint, illumination, occlusion, and background clutter can drastically alter the pixel representation of an object while still representing the same semantic concept. Algorithms must be robust to these variations.
Challenges in Image Classification
- Viewpoint Variability: Different angles can change the pixel representation entirely.
- Illumination Changes: Lighting conditions can affect how an object appears.
- Deformation: Objects can change shape or position, complicating recognition.
- Occlusion: Parts of an object may be hidden, yet humans can still recognize it.
- Background Clutter: The background may confuse the algorithm, making it hard to distinguish the object.
- Intraclass Variation: Objects within the same category can look very different (e.g., cats of different breeds).
The Data-Driven Approach
To tackle these challenges, a data-driven approach is employed:
- Data Collection: Large datasets of labeled images are gathered, often using tools like Google Image Search.
- Training a Classifier: A machine learning classifier is trained on this dataset to learn how to recognize different categories.
- Prediction: The trained model is then used to classify new images.
This approach shifts the focus from manually crafting rules for recognition to leveraging data to inform the model.
K-Nearest Neighbors (KNN) Classifier
The KNN classifier is one of the simplest algorithms for image classification:
- Training Phase: The algorithm memorizes the training data without any complex computations.
- Prediction Phase: For a new image, KNN finds the most similar images in the training set and assigns the label based on the majority vote of these neighbors.
Example: CIFAR-10 Dataset
The CIFAR-10 dataset, commonly used in machine learning, consists of 50,000 training images across 10 categories. The KNN algorithm can be applied to this dataset, where the similarity between images is often measured using distance metrics like L1 (Manhattan) or L2 (Euclidean) distances.
Decision Boundaries
Visualizing decision boundaries helps understand how KNN classifies images. For instance, using K=1 may lead to noisy classifications, while increasing K smooths out the decision boundaries, leading to better performance.
Limitations of KNN
While KNN is intuitive, it has significant drawbacks:
- Slow Testing: KNN is computationally expensive during testing, as it requires comparing the test image to all training images.
- Curse of Dimensionality: As the number of dimensions increases, the volume of the space increases, making it harder to find similar neighbors.
- Distance Metrics: Simple distance metrics may not capture perceptual similarity effectively.
Linear Classification
Linear classifiers represent a more structured approach:
- Parametric Model: Unlike KNN, linear classifiers summarize knowledge in parameters (weights) rather than memorizing data.
- Function Form: The classifier computes scores for each category based on a linear combination of input features and learned weights.
Template Matching
Linear classifiers can be viewed as template matching, where each row in the weight matrix corresponds to a template for a class. This allows for a more efficient representation of knowledge compared to KNN.
Challenges with Linear Classifiers
- Single Template Limitation: Linear classifiers learn only one template per category, which can lead to poor performance in cases of variability within classes.
- Multimodal Data: They struggle with datasets where classes appear in multiple regions of the feature space.
Conclusion
In this lecture, we explored the complexities of image classification, the challenges faced by algorithms, and the introduction of KNN and linear classifiers. While KNN provides a simple and intuitive approach, linear classifiers offer a more structured method for classification. As we progress in the course, we will delve deeper into optimization strategies and more advanced models, including neural networks and convolutional networks, to address the limitations of these initial algorithms.
