Editing Transduction (machine learning) (section)

==Transduction algorithms==
Transduction algorithms can be broadly divided into two categories: those that seek to assign discrete labels to unlabeled points, and those that seek to regress continuous labels for unlabeled points. Algorithms that seek to predict discrete labels tend to be derived by adding partial supervision to a [[Cluster analysis|clustering]] algorithm. Two classes of algorithms can be used: [[flat clustering]] and [[hierarchical clustering]]. The latter can be further subdivided into two categories: those that cluster by partitioning, and those that cluster by agglomerating. Algorithms that seek to predict continuous labels tend to be derived by adding partial supervision to a [[manifold learning]] algorithm.

===Partitioning transduction===

Partitioning transduction can be thought of as top-down transduction. It is a semi-supervised extension of partition-based clustering. It is typically performed as follows:

 Consider the set of all points to be one large partition.
 While any partition P contains two points with conflicting labels:
   Partition P into smaller partitions.
 For each partition P:
   Assign the same label to all of the points in P.

Of course, any reasonable partitioning technique could be used with this algorithm. [[Max flow min cut]] partitioning schemes are very popular for this purpose.

===Agglomerative transduction===

Agglomerative transduction can be thought of as bottom-up transduction. It is a semi-supervised extension of agglomerative clustering. It is typically performed as follows:

 Compute the pair-wise distances, D, between all the points.
 Sort D in ascending order.
 Consider each point to be a cluster of size 1.
 For each pair of points {a,b} in D:
   If (a is unlabeled) or (b is unlabeled) or (a and b have the same label)
     Merge the two clusters that contain a and b.
     Label all points in the merged cluster with the same label.

=== Continuous Label Transduction ===
These methods seek to regress continuous labels, often via '''manifold learning''' techniques. The idea is to learn a low-dimensional representation of the data and infer values smoothly across the manifold.