HW3 - (1)

Matmulengine

package hw3.matmulengine

import hw3.ndarray.Matrix

/**
 * Matrix multiplication engine.
 */
trait MatmulEngine {
  /**
   * Matrix multiplication.
   *
   * If the second dimension of the left matrix is not equal to
   * the first dimension of the right matrix, raise `NNException`
   *
   * @param left N x K matrix
   * @param right K x M matrix
   * @return N x M matrix
   */
  def matmul(left: Matrix, right: Matrix): Matrix
}

 

 

아래부터는 내가 짜야되는 코드이다.

1. NaiveEngine.scala

package hw3.matmulengine

import hw3.ndarray.Matrix

/**
 * Naive implementation of matrix multiplication.
 * TIP: Just implement the naive `O(n^3)` algorithm.
 * Any further optimization is not needed.
 */
object NaiveEngine extends MatmulEngine {
  def matmul(left: Matrix, right: Matrix): Matrix = ???
}

https://jeonyeohun.tistory.com/82

Matrix 곱셈을 구현하는 코드이다. 2dim-Array

 

 

 

2. Matrix.scala

package hw3.ndarray


final class Matrix(val values: Array[Vector]) extends NDArray {
  val ndim: Int = 2
  val getShape: Array[Int] = Array(values.length, values(0).getShape(0))

  /**
   * Get the i-th element along the first axis.
   * If the shape of an array `a` is (3, 4, 5), then `a.getArr(2).getShape == Array(4, 5)`.
   */
  def getArr(i: Int): Vector = {
    if(i>=values.length) NNException("OutOfRange") //should raise an `NNException`
    else values(i)
  }

  /**
   * Get the i-th value of this 1-dimensional array (i.e. only applied to a Vector).
   * If this array is not a Vector, raise an `NNException`.
   */
  def get(i: Int): Float = {
    if(values.getShape.length==1) values(i)
    else NNException("Not a Vector") //raise NNException
  }

  /**
   * Reshape this array by the given shape.
   *
   * e.g.) Matrix(((2, 3, 5), (3, 4, 7))).reshape(6).equals(Vector(2, 3, 5, 3, 4, 7)) == true
   *
   * NOTE 1: You can refer to the behavior of the NumPy `reshape` function.
   * https://www.w3schools.com/python/numpy/numpy_array_reshape.asp
   * For simplification, you don't have to implement `-1` dimension.
   *
   * NOTE 2: `Int*` type means that we can pass variable number of parameters.
   * You can treat an `Int*` value like `Seq[Int]` type.
   * e.g.) `arr.reshape(3, 5, 10)` is a valid expression.
   *
   * @param shape target shape
   * @return reshaped
   */
  def reshape(shape: Int*): NDArray = ???

  def reduceLeft[T](f: (Float, Float) => Float): T = ???

  def unaryOp(f: Float => Float): NDArray = ???

  def binOp(f: (Float, Float) => Float, that: NDArray): NDArray = ???

  def equals(that: NDArray): Boolean = ???
}


object Matrix extends NDArrayOps[Matrix] {
  def apply(values: Seq[Vector]): Matrix = ???

  def apply(shape: Seq[Int], values: Seq[Float]): Matrix = ???

  def fill(shape: Seq[Int], value: Float): Matrix = ???

  def stack(values: Seq[NDArray]): Matrix = {
    // TODO: check the every value in the values is Vector and has same shape.

    new Matrix(values.asInstanceOf[Seq[Vector]].toArray)
  }
}

Matrix는 Row-major order로 정의된다.

일단 Matrix 자체가 Array[Vector] 라서 Vector 먼저 정의하고 와야된다.

 

 

3. NDArray.scala

/**
 * Interface of an N-Dimensional array and its companion object.
 */
package hw3.ndarray

class NNException(val reason: String) extends Exception

trait NDArray {
  val ndim: Int
  val getShape: Array[Int]
  def getArr(i: Int): NDArray
  def get(i: Int): Float
  def reshape(shape: Int*): NDArray
  def reduceLeft[T](f: (Float, Float) => Float): T
  def unaryOp(f: Float => Float): NDArray
  def binOp(f: (Float, Float) => Float, that: NDArray): NDArray
  def add(that: NDArray): NDArray = ???
  def mul(that: NDArray): NDArray = ???
  def equals(that: NDArray): Boolean
}


trait NDArrayOps[+T <: NDArray] {
  def apply(shape: Seq[Int], values: Seq[Float]): T
  def fill(shape: Seq[Int], value: Float): T
  def stack(values: Seq[NDArray]): T
}

 

NDArray라는 trait를 바탕으로 나중에 Vector랑 Matrix를 만든다. 따라서 가장 뼈대가 되는 단계. trait 특성상 추상화된 형태로 둬도 괜찮고, 구체화해도 되는데 여기에서는 add 랑 mul만 구체화하고 나머지는 그대로 둔다. 따라서 일단 각 메소드의 역할에 대해서 알아보자.

 

먼저

1. val ndin:Int

   * Number of dimensions of this N-dimensional array. (returns N)
몇차원 Array인지 return 하면 된다. Vector면 1차원, Matrix면 2차원 배열.

 

 

2.  val getShape: Array[Int]
  : Shape of this N-dimensional array.

벡터의 경우는 단순히 길이가 반환되고, 매트릭스의 경우는 2행 3열, 이런식으로 Array(2,3) 이렇게 반환된다.
   *
   * e.g.) Let `a` is `[[0,1,2,3],[4,5,6,7]]`, then `a.getShape == Array(2, 3)`.
   */ 이 예시는 왜 2,3 을 반환하는거지 ..?? (2,4) 아닌가? 오타인지 내가 이해를 잘못했는지 모르겠지만 일단 패스

 

 

3. def getArr(i:Int):NDArray
   * Get the i-th element along the first axis.
   * If the shape of an array `a` is (3, 4, 5), then `a.getArr(2).getShape == Array(4, 5)`.
   * If the given `i` is not in the range of the first axis (e.g. `a.getArr(3)`), it should raise an `NNException`.
   *
   * @param i index along the first axis (starting from 0)
   * @return i-th NDArray
   */
 

--> the first axis가 무슨 말인지 잘 이해를 못했었는데 , 예를 들어 shape이 (2,3,4)인 NDArray가 있으면 Array 안에는 기본적으로 2개의 NDArray가 있고 ->> 그 각각의 NDArray의 shape이 (3,4)인 것이다. 

 

--> 그냥 Array라고 생각했을 때, array.tail을 리턴하면 되긴한다. (두번째 element 부터가 그 다음 차원에 대한 정보이기 때문)

 

 

4. def get(i:Int):Float
  /**
   * Get the i-th value of this 1-dimensional array (i.e. only applied to a Vector).
   * If this array is not a Vector, raise an `NNException`.
   *
   * @param i index (starting from 0)
   * @return i-th value
   */
이거는 1차원일때만 작동하는 메소드이고, 그냥 그 인덱스에 해당하는 값을 리턴한다. values(i) 하면 끝

 

 

5.   def reshape(shape: Int*): NDArray

Matrix(((2, 3, 5), (3, 4, 7)))가 있다고 해보자. 해당 매트릭스의 shape (2,3)

Matrix(((2, 3, 5), (3, 4, 7))).reshape(6)을 적용하면 Vector(2, 3, 5, 3, 4, 7)가 리턴된다.
   *
   * NOTE 1: You can refer to the behavior of the NumPy `reshape` function.
   * https://www.w3schools.com/python/numpy/numpy_array_reshape.asp
   * For simplification, you don't have to implement `-1` dimension.
   *
   * NOTE 2: `Int*` type means that we can pass variable number of parameters.
   * You can treat an `Int*` value like `Seq[Int]` type.
   * e.g.) `arr.reshape(3, 5, 10)` is a valid expression.

5

깃허브에 올라온 관련 질문. 나도 궁금했었는데 마침 누군가 물어봤다.

 

 

 

6.  def reduceLeft[T](f: (Float, Float) => Float): T
  /**
   * Apply an element-wise binary operator to all elements along the first axis.
   * Note that f can be non-associative.
   *
   * e.g) [[2, 3, 5], [3, 1, 0]].reduceLeft(_ + _) = [5, 4, 5]
   *  [[1, 2, 3]].reduceLeft(_ + _) = [1, 2, 3]
   *  [2, 3, 4].reduceLeft(_ - _) = ((2 - 3) - 4) = -5
   *
   * @param f binary operator
   * @tparam T type of the inner element: NDArray (if this is Matrix or StackedArray) or Float (if this is Vector)
   * @return see Seq.reduceLeft
   */
  def reduceLeft[T](f: (Float, Float) => Float): T

 

 

 

 

7.   def unaryOp(f: Float => Float): NDArray
  /**
   * Element-wise unary operation.
   *
   * @param f unary operator (e.g. neg, exp)
   * @return the result of the element-wise operation
   */
  def unaryOp(f: Float => Float): NDArray

 

 

 

8.  def binOp(f: (Float, Float) => Float, that: NDArray): NDArray

  /**
   * Element-wise binary operation.
   * If the `ndim` of this and that are not same, then raise an `NNException`.
   *
   * @param f binary operator (e.g. add, mul)
   * @param that NDArray with a same size
   * @return the result of the element-wise operation
   */
  def binOp(f: (Float, Float) => Float, that: NDArray): NDArray

 

 

9.   def add(that: NDArray): NDArray =???
  /**
   * Element-wise addition.
   * @param that NDArray with a same size
   * @return the result of the element-wise addition
   */

  def add(that: NDArray): NDArray = {
      def plus(n1:Vector, n2:Vector, idx:Int=0, arr:Array[Float] = Array()):Array[Float] = {
      	if(idx == n1.values.length) arr
        else {
        	val nrr:Array[Float] = Array(n1.values(idx) + n2.values(idx))
        	plus(n1,n2,idx+1, arr+nrr)}
      }
      if(that.ndim == 1) {
      	val result = new Vector(plus(this,that))
      	result}
      else if(that.ndim == 2) {
      
      
      }
      else {
      val result = new StackedArray()
      result
      }

  
  
  
  
  
  }

  def add(that: NDArray): NDArray = {
    def func(idx:Int,res:Vector):Vector={
      if (idx==that.getShape(0)) res
      else {
        res(i) = values(i) + that(i)
        func(idx+1, res)
      }
    }
    //벡터에 덧셈 연산
    if(that.ndim ==1) {}
    else
  }

 

 

10.   def mul(that: NDArray): NDArray = ???
  /**
   * Element-wise multiplication.
   *
   * @param that NDArray with a same size
   * @return the result of the element-wise multiplication
   */
  def mul(that: NDArray): NDArray = ???

 

 

 

11.   def equals(that: NDArray): Boolean
  /**
   * Check the two arrays have the same values.
   *
   * @param that NDArray to compare
   * @return `true` if the two arrays have the same values
   */
  def equals(that: NDArray): Boolean

 

 

 

 

 

4.StackedArray.scala

package hw3.ndarray

/**
 * Implementation of the N-dimensional matrix with N >= 3.
 * HINT: You should first implement Matrix and Vector.
 *
 * @param values values of this matrix (row-major)
 */
final class StackedArray(val values: Array[NDArray]) extends NDArray {
  val ndim: Int = ???

  val getShape: Array[Int] = ???

  def getArr(i: Int): NDArray = ???

  def get(i: Int): Float = ???

  def reshape(shape: Int*): NDArray = ???

  def reduceLeft[T](f: (Float, Float) => Float): T = ???

  def unaryOp(f: Float => Float): NDArray = ???

  def binOp(f: (Float, Float) => Float, that: NDArray): NDArray = ???

  def equals(that: NDArray): Boolean = ???
}

object StackedArray extends NDArrayOps[StackedArray] {
  def apply(shape: Seq[Int], values: Seq[Float]): StackedArray = ???

  def fill(shape: Seq[Int], value: Float): StackedArray = ???

  def stack(values: Seq[NDArray]): StackedArray = ???
}

 

 

 

5.Vector.scala

/**
 * You should fill every ??? and TODOs before the compilation
 */
package hw3.ndarray

/**
 * Implementation of mathematical vector (i.e. 1-dim array).
 *
 * @param values values of this array
 */
final class Vector(val values: Array[Float]) extends NDArray {
  val ndim: Int = 1
  val getShape: Array[Int] = Array(values.length)
  def getArr(i: Int): NDArray = throw new NNException("getArr cannot be applied to a Vector.")
  def get(i: Int): Float = values(i)
  def reshape(shape: Int*): NDArray = ???

  def reduceLeft[T](f: (Float, Float) => Float): T = ???

  def unaryOp(f: Float => Float): NDArray = ???

  def binOp(f: (Float, Float) => Float, that: NDArray): NDArray = ???

  def equals(that: NDArray): Boolean = {
    def check(idx:Int):Boolean ={
      if(idx==values.length) true
      else {
        if (values(idx) != that.get(idx)) false
        else check(idx+1)
      }
    }
    check(0)
  }
}

object Vector extends NDArrayOps[Vector] {
  def apply(values: Seq[Float]): Vector = new Vector(values.toArray)

  def apply(shape: Seq[Int], values: Seq[Float]): Vector = {
    if (shape.length != 1) {
      throw new NNException("the length of the given shape is not 1.")
    } else if (shape.head != values.length) {
      throw new NNException("the given shape does not equal to the number of values.")
    } else {
      new Vector(values.toArray)
    }
  }

  def fill(shape: Seq[Int], value: Float): Vector = {
    if (shape.length != 1) {
      throw new NNException("the length of the given shape is not 1.")
    } else {
      new Vector(Array.fill(shape.head)(value))
    }
  }

  def stack(values: Seq[NDArray]): Vector =
    throw new NNException("There is not an implementation of 0-dim array.")
}

 

 

 

 

 

6. Linear.scala

package hw3.nnmodule

import hw3.matmulengine.{MatmulEngine, NaiveEngine}
import hw3.ndarray.{Matrix, NDArray, StackedArray}

/**
 * Linear transformation
 */
class Linear(val weight: Matrix) extends NNModule {
  protected val me: MatmulEngine = NaiveEngine

  def apply(input: NDArray): NDArray = {
    if (input.ndim == 1) {
      // TODO: return (weight * input) matrix x vector multiplication using `me`
      ???
    } else if (input.ndim == 2) {
      // TODO: return (weight * input) matrix x matrix multiplication using `me`
      ???
    } else {
      // Batched matmul
      val length = input.getShape(0)
      val mapped = (0 until length).map(i => this(input.getArr(i)))
      StackedArray.stack(mapped)
    }
  }
}

 

 

 

 

 

7. ReLU.scala

package hw3.nnmodule

import hw3.ndarray.NDArray

/**
 * Rectified Linear Unit.
 *
 * Return `if (x >= 0) x else 0`
 */
object ReLU extends NNModule {
  def apply(input: NDArray): NDArray = ???
}

 

 

 

 

 

 

8. Sequential.scala

package hw3.nnmodule

import hw3.ndarray.NDArray

/**
 * Sequence of submodules.
 *
 * @param submodules sequence of submodules. must not be empty
 */
class Sequential(val submodules: Array[NNModule]) extends NNModule {
  def apply(input: NDArray): NDArray = ???
}

object Sequential {
  def apply(submodules: NNModule*) = new Sequential(submodules.toArray)
}