001/*
002 * Copyright (c) 2015-2020, Oracle and/or its affiliates. All rights reserved.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package org.tribuo.classification.sgd;
018
019import org.tribuo.math.la.SGDVector;
020import org.tribuo.math.la.SparseVector;
021
022import java.util.SplittableRandom;
023
024/**
025 * SGD utilities. Currently stores methods for shuffling examples and their associated labels and weights.
026 */
027public class Util {
028    /**
029     * In place shuffle of the features, labels and weights.
030     * @deprecated In favour of {@link org.tribuo.common.sgd.AbstractLinearSGDTrainer#shuffleInPlace}.
031     * @param features Input features.
032     * @param labels Input labels.
033     * @param weights Input weights.
034     * @param rng SplittableRandom number generator.
035     */
036    @Deprecated
037    public static void shuffleInPlace(SparseVector[] features, int[] labels, double[] weights, SplittableRandom rng) {
038        int size = features.length;
039        // Shuffle array
040        for (int i = size; i > 1; i--) {
041            int j = rng.nextInt(i);
042            //swap features
043            SparseVector tmpFeature = features[i-1];
044            features[i-1] = features[j];
045            features[j] = tmpFeature;
046            //swap labels
047            int tmpLabel = labels[i-1];
048            labels[i-1] = labels[j];
049            labels[j] = tmpLabel;
050            //swap weights
051            double tmpWeight = weights[i-1];
052            weights[i-1] = weights[j];
053            weights[j] = tmpWeight;
054        }
055    }
056
057    /**
058     * In place shuffle of the features, labels, weights and indices.
059     * @param features Input features.
060     * @param labels Input labels.
061     * @param weights Input weights.
062     * @param indices Input indices.
063     * @param rng SplittableRandom number generator.
064     */
065    public static void shuffleInPlace(SparseVector[] features, int[] labels, double[] weights, int[] indices, SplittableRandom rng) {
066        int size = features.length;
067        // Shuffle array
068        for (int i = size; i > 1; i--) {
069            int j = rng.nextInt(i);
070            //swap features
071            SparseVector tmpFeature = features[i-1];
072            features[i-1] = features[j];
073            features[j] = tmpFeature;
074            //swap labels
075            int tmpLabel = labels[i-1];
076            labels[i-1] = labels[j];
077            labels[j] = tmpLabel;
078            //swap weights
079            double tmpWeight = weights[i-1];
080            weights[i-1] = weights[j];
081            weights[j] = tmpWeight;
082            //swap indices
083            int tmpIndex = indices[i-1];
084            indices[i-1] = indices[j];
085            indices[j] = tmpIndex;
086        }
087    }
088
089    /**
090     * Shuffles the features, labels and weights returning a tuple of the shuffled inputs.
091     * @param features Input features.
092     * @param labels Input labels.
093     * @param weights Input weights.
094     * @param rng SplittableRandom number generator.
095     * @return A tuple of shuffled features, labels and weights.
096     */
097    public static ExampleArray shuffle(SparseVector[] features, int[] labels, double[] weights, SplittableRandom rng) {
098        int size = features.length;
099        SparseVector[] newFeatures = new SparseVector[size];
100        int[] newLabels = new int[size];
101        double[] newWeights = new double[size];
102        for (int i = 0; i < newFeatures.length; i++) {
103            newFeatures[i] = features[i];
104            newLabels[i] = labels[i];
105            newWeights[i] = weights[i];
106        }
107        // Shuffle array
108        for (int i = size; i > 1; i--) {
109            int j = rng.nextInt(i);
110            //swap features
111            SparseVector tmpFeature = newFeatures[i-1];
112            newFeatures[i-1] = newFeatures[j];
113            newFeatures[j] = tmpFeature;
114            //swap labels
115            int tmpLabel = newLabels[i-1];
116            newLabels[i-1] = newLabels[j];
117            newLabels[j] = tmpLabel;
118            //swap weights
119            double tmpWeight = newWeights[i-1];
120            newWeights[i-1] = newWeights[j];
121            newWeights[j] = tmpWeight;
122        }
123        return new ExampleArray(newFeatures,newLabels,newWeights);
124    }
125
126    /**
127     * A nominal tuple. One day it'll be a record, but not today.
128     */
129    public static class ExampleArray {
130        /**
131         * The examples encoded as sparse vectors.
132         */
133        public final SparseVector[] features;
134        /**
135         * The label indices.
136         */
137        public final int[] labels;
138        /**
139         * The example weights.
140         */
141        public final double[] weights;
142
143        /**
144         * Constructs an example array.
145         * @param features The examples' features.
146         * @param labels The label indices.
147         * @param weights The example weights.
148         */
149        public ExampleArray(SparseVector[] features, int[] labels, double[] weights) {
150            this.features = features;
151            this.labels = labels;
152            this.weights = weights;
153        }
154    }
155
156    /**
157     * In place shuffle used for sequence problems.
158     * @param features Input features.
159     * @param labels Input labels.
160     * @param weights Input weights.
161     * @param rng SplittableRandom number generator.
162     */
163    public static void shuffleInPlace(SGDVector[][] features, int[][] labels, double[] weights, SplittableRandom rng) {
164        int size = features.length;
165        // Shuffle array
166        for (int i = size; i > 1; i--) {
167            int j = rng.nextInt(i);
168            //swap features
169            SGDVector[] tmpFeature = features[i-1];
170            features[i-1] = features[j];
171            features[j] = tmpFeature;
172            //swap labels
173            int[] tmpLabel = labels[i-1];
174            labels[i-1] = labels[j];
175            labels[j] = tmpLabel;
176            //swap weights
177            double tmpWeight = weights[i-1];
178            weights[i-1] = weights[j];
179            weights[j] = tmpWeight;
180        }
181    }
182
183    /**
184     * Shuffles a sequence of features, labels and weights, returning a tuple of the shuffled values.
185     * @param features Input features.
186     * @param labels Input labels.
187     * @param weights Input weights.
188     * @param rng SplittableRandom number generator.
189     * @return A tuple of shuffled features, labels and weights.
190     */
191    public static SequenceExampleArray shuffle(SGDVector[][] features, int[][] labels, double[] weights, SplittableRandom rng) {
192        int size = features.length;
193        SGDVector[][] newFeatures = new SGDVector[size][];
194        int[][] newLabels = new int[size][];
195        double[] newWeights = new double[size];
196        for (int i = 0; i < newFeatures.length; i++) {
197            newFeatures[i] = features[i];
198            newLabels[i] = labels[i];
199            newWeights[i] = weights[i];
200        }
201        // Shuffle array
202        for (int i = size; i > 1; i--) {
203            int j = rng.nextInt(i);
204            //swap features
205            SGDVector[] tmpFeature = newFeatures[i-1];
206            newFeatures[i-1] = newFeatures[j];
207            newFeatures[j] = tmpFeature;
208            //swap labels
209            int[] tmpLabel = newLabels[i-1];
210            newLabels[i-1] = newLabels[j];
211            newLabels[j] = tmpLabel;
212            //swap weights
213            double tmpWeight = newWeights[i-1];
214            newWeights[i-1] = newWeights[j];
215            newWeights[j] = tmpWeight;
216        }
217        return new SequenceExampleArray(newFeatures,newLabels,newWeights);
218    }
219
220    /**
221     * A nominal tuple. One day it'll be a record, but not today.
222     */
223    public static class SequenceExampleArray {
224        /**
225         * The array of sequence example features.
226         */
227        public final SGDVector[][] features;
228        /**
229         * The sequence example label indices.
230         */
231        public final int[][] labels;
232        /**
233         * The sequence example weights.
234         */
235        public final double[] weights;
236
237        SequenceExampleArray(SGDVector[][] features, int[][] labels, double[] weights) {
238            this.features = features;
239            this.labels = labels;
240            this.weights = weights;
241        }
242    }
243}